Issue # 13: IT training - current issues and challenges from leading companies

    We selected the questions and tasks encountered by job seekers at interviews with leading IT companies in the world.

    KDPV

    The selection included the tasks asked at the interviews as a design engineer. Tasks of various difficulty levels, ranging from simple ones. We suggest you try your hand and try to solve the problems yourself - then the questions at the interview are unlikely to take you by surprise.

    Questions


    1. 2 kind of pills
      A man has a medical condition that requires him to take two kinds of pills, call them A and B. The man must take exactly one A pill and exactly one B pill each day. The pills are taken by first dissolving them in water.

      The man has a jar of A pills and a jar of B pills. One day, as he is about to take his pills, he takes out one A pill from the A jar and puts it in a glass of water. Then he accidentally takes out two B pills from the B jar and puts them in the water. Now, he is in the situation of having a glass of water with three dissolved pills, one A pill and two B pills. Unfortunately, the pills are very expensive, so the thought of throwing out the water with the 3 pills and starting over is out of the question. How should the man proceed in order to get the right quantity of A and B while not wasting any pills?

      Transfer
      According to medical indications, one patient needs to take two medicines, A and B, and exactly 1 tablet A and 1 tablet B must be taken daily. Tablets are taken in dissolved form.

      The patient has a flask with A and a flask with B. Once, having dissolved tablet A in a glass, he threw 2 tablets from a flask with B there and received a glass with a solution of 1 A and 2 B. Unfortunately, the drugs are expensive, so he rejected the idea pour this solution and prepare a new one. How can this patient continue taking the prescribed medications without losing a pill?

    2. Avg salary
      Three Employees want to know average of their salaries. They are not allowed to share their individual salaries. How can they calcalate average salary?

      Transfer
      Three employees want to know the average salary (among them three), despite the fact that they are forbidden to voice an individual salary. How do they calculate the average salary?


    Tasks


    1. Find possible compositions of a natural number

      Given a natural number n, write a program to find the number of ways in which n can be expressed as a sum of natural numbers when order is taken into consideration. Two sequences that differ in the order of their terms define different compositions of their sum.

      Examples:

      Input: 4
      Output: 8
      Explanation
      All 8 position composition are:
      4, 1 + 3, 3 + 1, 2 + 2, 1 + 1 + 2, 1 + 2 + 1, 2 + 1 + 1 and 1 + 1 + 1 + 1

      Input: 8
      Output: 128

      Transfer
      Given a natural number n, write a program to search for the number of combinations of numbers, the sum of which gives as a result n, taking into account the order. Two sequences that differ in order are considered different combinations.

      Examples:

      Input: 4
      Output: 8
      Explanation: 4, 1 + 3, 3 + 1, 2 + 2, 1 + 1 + 2, 1 + 2 + 1, 2 + 1 + 1 and 1 + 1 + 1 + 1

    2. Count numbers that don't contain 3
      Given a number n, write a function that returns count of numbers from 1 to n that don't contain digit 3 in their decimal representation.

      Examples:

      Input: n = 10
      Output: 9

      Input: n = 45
      Output: 31
      // Numbers 3, 13, 23, 30, 31, 32, 33, 34,
      // 35, 36, 37, 38, 39, 43 contain digit 3.

      Input: n = 578
      Ouput: 385


      Transfer
      Given the number n. Write a program that will count the number of numbers not containing 3 in decimal notation from 1 to n.

      Examples:

      Input: n = 10
      Output: 9

      Input: n = 45
      Output: 31
      // Numbers 3, 13, 23, 30, 31, 32, 33, 34,
      // 35, 36, 37, 38, 39, 43 contain 3.

      Input: n = 578
      Output: 385

    3. Boolean array puzzle
      Write a program according with the following specifications:

      Input: A array arr [] of two elements having value 0 and 1
      Output: Make both elements 0.

      Requirements: Following are the specifications to follow.

      1) It is guaranteed that one element is 0 but we do not know its position.
      2) We can't say about another element it can be 0 or 1.
      3) We can only complement array elements, no other operation like and, or, multi, division, .... etc.
      4) We can't use if, else and loop constructs.
      5) Obviously, we can't directly assign 0 to array elements.

      Transfer
      Write a program that satisfies the following requirements:

      Input: arr [] array of 2 elements having possible values ​​1 or 0
      Output: Make both elements equal 0

      Requirements:
      1) It is known that one element is 0, but its position is unknown
      2) We cannot say this about the second element, it can be 0 or 1.
      3) We can only complement the elements of the array, no other operations, such as or, and, multiplication, division, etc. are not allowed.
      4) It is impossible to use conditional constructions, cycles.
      5) You cannot explicitly write 0 to array elements.


    Answers will be given within the next week - have time to decide. Good luck

    Solutions


    1. Question 1
      The correct answer was given in the comments:
      You need to add another tablet A to a glass, mix and drink half a glass, leaving half the next day.


    2. Question 2
      Many solutions were suggested, one, for example, in this comment .

    3. Task 1
      The correct solution was also found in the comments.
      Through a little analysis, we can find out and prove that the number of combinations is 2 n-1 .

      #include
      using namespace std;
      #define ull unsigned long long
      ull countCompositions(ull n)
      {
      	// Return 2 raised to power (n-1)
      	return (1L) << (n-1);
      }
      // Driver Code
      int main()
      {
      	ull n = 4;
      	cout << countCompositions(n) << "\n";
      	return 0;
      }
      


    4. Task 2
      Recursive solution option:
      #include 
      /* returns count of numbers which are in range from 1 to n and don't contain 3 
         as a digit */
      int count(int n)
      {
          // Base cases (Assuming n is not negative)
          if (n < 3)
              return n;
          if (n >= 3 && n < 10)
             return n-1;
          // Calculate 10^(d-1) (10 raise to the power d-1) where d is
          // number of digits in n. po will be 100 for n = 578
          int po = 1;
          while (n/po > 9)
              po = po*10;
          // find the most significant digit (msd is 5 for 578)
          int msd = n/po;
          if (msd != 3)
            // For 578, total will be 4*count(10^2 - 1) + 4 + count(78)
            return count(msd)*count(po - 1) + count(msd) + count(n%po);
          else
            // For 35, total will be equal to count(29)
            return count(msd*po - 1);
      }
      // Driver program to test above function
      int main()
      {
          printf ("%d ", count(578));
          return 0;
      }
      


    5. Task 3
      The correct answer is suggested in the comment.


    Also popular now: