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

    This week, we selected the questions and tasks that job applicants face in interviews for the position of development engineer at Ebay.

    KDPV

    When applying for a job on Ebay, you can be asked not only technical questions, but also logical tasks. Below are some of these questions and challenges, with varying degrees of difficulty, from simple to complex.


    Questions


    1. Days of month using 2 dice
      How can you represent days of month using two 6 sided dice? You can write one number on each face of the dice from 0 to 9 and you have to represent days from 1 to 31, for example for 1, one dice should show 0 and another should show 1, similarly for 29 one dice should show 2 and another should show 9.

      Transfer
      How would you imagine the days of the month using 2 hex cubes? You can write numbers from 0 to 9 on each face of the cube, and you need to designate numbers from 1 to 31. For example, for the 1st number, one cube can be rotated by a face with “0” and the other with “1”; similarly for the number 29 - one dice with "2", the second - with "9".

    2. Blindfolded and coins
      You are blindfolded and 10 coins are place in front of you on table. You are allowed to touch the coins, but can't tell which way up they are by feel. You are told that there are 5 coins head up, and 5 coins tails up but not which ones are which.

      Can you make two piles of coins each with the same number of heads up? You can flip the coins any number of times.


      Transfer
      You are blindfolded, and on the table in front of you are 10 coins. You are allowed to touch them, but to the touch you cannot tell which side they are turned. It is also claimed that 5 coins lie eagle up, 5 - tails.

      How to make 2 stacks with an equal number of coins turned by an eagle up? You can flip coins an unlimited number of times.


    Tasks


    1. Tug of war
      Given a set of n integers, divide the set in two subsets of n / 2 sizes each such that the difference of the sum of two subsets is as minimum as possible. If n is even, then sizes of two subsets must be strictly n / 2 and if n is odd, then size of one subset must be (n-1) / 2 and size of other subset must be (n + 1) / 2 .

      For example, let given set be {3, 4, 5, -3, 100, 1, 89, 54, 23, 20}, the size of set is 10. Output for this set should be {4, 100, 1, 23, 20} and {3, 5, -3, 89, 54}. Both output subsets are of size 5 and sum of elements in both subsets is same (148 and 148).
      Let us consider another example where n is odd. Let given set be {23, 45, -34, 12, 0, 98, -99, 4, 189, -1, 4}. The output subsets should be {45, -34, 12, 98, -1} and {23, 0, -99, 4, 189, 4}. The sums of elements in two subsets are 120 and 121 respectively.

      Transfer
      Given a set of n integers, it is necessary to divide it into 2 subsets, dimension n / 2 each, so that the difference between the sums of these subsets is minimal. If n is even, then the sizes of the subsets must be exactly n / 2, if n is odd, then the size of one subset must be (n-1) / 2, the second - (n + 1) / 2.

      For example:
      Input: {3, 4, 5, -3, 100, 1, 89, 54, 23, 20}
      Output: {4, 100, 1, 23, 20} and {3, 5, -3, 89, 54}. The sizes of both subsets are 5, and the sums are 148.

      Input: {23, 45, -34, 12, 0, 98, -99, 4, 189, -1, 4}
      Output: {45, -34, 12, 98 , -1} and {23, 0, -99, 4, 189, 4}. The sums of the subsets 120 and 121, respectively.

    2. Maximum sum such that no two elements are adjacent
      Given an array of positive numbers, find the maximum sum of a subsequence with the constraint that no 2 numbers in the sequence should be adjacent in the array. So 3 2 7 10 should return 13 (sum of 3 and 10) or 3 2 5 10 7 should return 15 (sum of 3, 5 and 7) .Answer the question in most efficient way.

      Examples:

      Input: arr [] = {5, 5, 10, 100, 10, 5}
      Output: 110

      Input: arr [] = {1, 2, 3}
      Output: 4

      Input: arr [] = {1, 20 , 3}
      Output: 20

      Transfer
      Given an array of positive numbers, find the maximum sum of the subsequence with the condition that no 2 elements of the subsequence are in neighboring cells of the array. So, 3 2 7 10 should return 13 (the sum of 3 and 10), and 3 2 5 10 7 should return 15 (the sum of 3 5 7). The code should be as efficient as possible.

      Examples:

      Input: arr [] = {5, 5, 10, 100, 10, 5}
      Output: 110

      Input: arr [] = {1, 2, 3}
      Output: 4

      Input: arr [] = {1, 20 , 3}
      Output: 20


    3. Program to find amount of water in a given glass
      There are some glasses with equal capacity as 1 liter. The glasses are kept as follows:
                         1
                       2 3
                    4 5 6
                  7 8 9 10
      

      You can put water to only top glass. If you put more than 1 liter water to 1st glass, water overflows and fills equally in both 2nd and 3rd glasses. Glass 5 will get water from both 2nd glass and 3rd glass and so on.
      If you have X liter of water and you put that water in top glass, how much water will be contained by jth glass? Write a program to find it.

      Example. If you will put 2 liter on top.
      1st - 1 liter
      2nd - 1/2 liter
      3rd - 1/2 liter

      Transfer
      Several cans with a capacity of 1 liter are built by a pyramid like this:
                         1
                       2 3
                    4 5 6
                  7 8 9 10
      

      You can only pour water into the topmost can. When the can overflows, the water will begin to flow evenly into the lower ones (2 and 3). Bank 5 will receive water from 2 and 3 cans, etc.
      If you have X liters of water that you pour into the top jar, how much water will go into j? Write a program to resolve this issue.

      Example. If you pour 2 liters, then:
      1st - 1 liter
      2nd - 1/2 liters
      3rd - 1/2 liters

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

    Solutions


    1. Question 1
      The answer was quickly found .

    2. Question 2
      Rsa97 proposed the right solution .

    3. Task 1
      Initial solution:
      #include 
      #include 
      #include 
      using namespace std;
      // function that tries every possible solution by calling itself recursively
      void TOWUtil(int* arr, int n, bool* curr_elements, int no_of_selected_elements,
                   bool* soln, int* min_diff, int sum, int curr_sum, int curr_position)
      {
          // checks whether the it is going out of bound
          if (curr_position == n)
              return;
          // checks that the numbers of elements left are not less than the
          // number of elements required to form the solution
          if ((n/2 - no_of_selected_elements) > (n - curr_position))
              return;
          // consider the cases when current element is not included in the solution
          TOWUtil(arr, n, curr_elements, no_of_selected_elements,
                    soln, min_diff, sum, curr_sum, curr_position+1);
          // add the current element to the solution
          no_of_selected_elements++;
          curr_sum = curr_sum + arr[curr_position];
          curr_elements[curr_position] = true;
          // checks if a solution is formed
          if (no_of_selected_elements == n/2)
          {
              // checks if the solution formed is better than the best solution so far
              if (abs(sum/2 - curr_sum) < *min_diff)
              {
                  *min_diff = abs(sum/2 - curr_sum);
                  for (int i = 0; i


    4. Задача 2
      Вариант решения:
      #include
      /*Function to return max sum such that no two elements
       are adjacent */
      int FindMaxSum(int arr[], int n)
      {
        int incl = arr[0];
        int excl = 0;
        int excl_new;
        int i;
        for (i = 1; i < n; i++)
        {
           /* current max excluding i */
           excl_new = (incl > excl)? incl: excl;
           /* current max including i */
           incl = excl + arr[i];
           excl = excl_new;
        }
         /* return max of incl and excl */
         return ((incl > excl)? incl : excl);
      }
      /* Driver program to test above function */
      int main()
      {
        int arr[] = {5, 5, 10, 100, 10, 5};
        int n = sizeof(arr) / sizeof(arr[0]);
        printf("%d n", FindMaxSum(arr, n));
        return 0;
      }
      


    5. Задача 3
      Вариант решения:
      // Program to find the amount of water in j-th glass
      // of i-th row
      #include 
      #include 
      #include 
      // Returns the amount of water in jth glass of ith row
      float findWater(int i, int j, float X)
      {
          // A row number i has maximum i columns. So input
          // column number must be less than i
          if (j > i)
          {
              printf("Incorrect Inputn");
              exit(0);
          }
          // There will be i*(i+1)/2 glasses till ith row 
          // (including ith row)
          float glass[i * (i + 1) / 2];
          // Initialize all glasses as empty
          memset(glass, 0, sizeof(glass));
          // Put all water in first glass
          int index = 0;
          glass[index] = X;
          // Now let the water flow to the downward glasses 
          // till the row number is less than or/ equal to i (given row) 
          // correction : X can be zero for side glasses as they have lower rate to fill
          for (int row = 1; row <= i ; ++row)
          {
              // Fill glasses in a given row. Number of 
              // columns in a row is equal to row number
              for (int col = 1; col <= row; ++col, ++index)
              {
                  // Get the water from current glass
                  X = glass[index];
                  // Keep the amount less than or equal to
                  // capacity in current glass
                  glass[index] = (X >= 1.0f) ? 1.0f : X;
                  // Get the remaining amount
                  X = (X >= 1.0f) ? (X - 1) : 0.0f;
                  // Distribute the remaining amount to 
                  // the down two glasses
                  glass[index + row] += X / 2;
                  glass[index + row + 1] += X / 2;
              }
          }
          // The index of jth glass in ith row will 
          // be i*(i-1)/2 + j - 1
          return glass[i*(i-1)/2 + j - 1];
      }
      // Driver program to test above function
      int main()
      {
          int i = 2, j = 2;
          float X = 2.0; // Total amount of water
          printf("Amount of water in jth glass of ith row is: %f",
                  findWater(i, j, X));
          return 0;
      }
      



    Also popular now: