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

Questions

1. Total distance traveled by bee
   

   Two trains are on the same track and they are coming toward each other. The speed of first train is 50 KMs / h and the speed of second train is 70 KMs / h. A bee starts flying between the trains when the distance between two trains is 100 KMs. The bee first flies from first train to second train. Once it reaches the second train, it immediately flies back to the second train ... and so on until trains collide. Calculate the total distance traveled by the bee. Speed ​​of bee is 40 KMs / h.

   
   
   Transfer

   Two trains on one track go towards each other. The speed of the first train is 50 km / h, the speed of the second is 70 km / h. A bee starts flying between trains when the distance between them is 100 km. A bee flies from the first train to the second. When it reaches the second, it immediately flies back to the first ... and continues to fly like that until the trains collide.
   Count the distance a bee has traveled if its speed is 40 km / h.
   
   
   
2. Poisoned wine
   

   The King of a small country invites 240 senators to his annual party. As a tradition, each senator brings the King a bottle of wine. Soon after, the Queen discovers that one of the senators is trying to assassinate the King by giving him a bottle of poisoned wine. Unfortunately, they do not know which senator, nor which bottle of wine is poisoned, and the poison is completely indiscernible. However, the King has 5 prisoners he plans to execute. He decides to use them as taste testers to determine which bottle of wine contains the poison. After drinking the poisoned wine, one dies within 24 hours. The King needs to determine which bottle of wine is poisoned in 2 days so that the festivities can continue as planned.
   

   
   
   Transfer

   The king of a small country invited 240 senators to an annual celebration. According to tradition, each senator presents the king with a bottle of wine. However, the queen soon learned that one of the senators was trying to poison the king by giving him a poisoned bottle of wine. Unfortunately, they don’t know who the senator is or what kind of bottle has been poisoned; moreover, the poison cannot be detected. There are 5 prisoners in the royal prison sentenced to death soon. The king decides with their help to figure out a poisoned bottle of wine. The poison will work only after 24 hours - the drinker dies. The king needs to identify which bottle has been poisoned in 2 days in order to continue the planned activities. How can he distribute wine among prisoners in order to guarantee a poisoned bottle in 48 hours?
   

Tasks

1. Largest subarray with equal number of 0s and 1s
   

   Given an array containing only 0s and 1s, find the largest subarray which contain equal number of 0s and 1s.
   
   Examples:
   Input: arr [] = {1, 0, 1, 1, 1, 0, 0}
   Output: 1 to 6 (Starting and Ending indexes of output subarray)
   
   Input: arr [] = {1, 1, 1, 1}
   Output: No such subarray
   
   Input: arr [] = {0, 0, 1, 1, 0}
   Output: 0 to 3 Or 1 to 4
   

   
   
   Transfer

   An array containing zeros and ones is given. You need to find the largest subarray containing the same number of 0 and 1.
   
   Examples:
   Input: arr [] = {1, 0, 1, 1, 1, 0, 0}
   Output: 1 to 6 (Indices of the input array)
   
   Input: arr [] = {1, 1, 1, 1}
   Output: No such subarray
   
   Input: arr [] = {0, 0, 1, 1, 0}
   Output: 0 to 3 Or 1 to 4
   
   
   
2. Count total set bits
   

   Given a positive integer n, count the total number of set bits in binary representation of all numbers from 1 to n.
   
   Examples:
   
   Input: n = 3
   Output: 4
   
   Input: n = 6
   Output: 9
   
   Input: n = 7
   Output: 12
   
   Input: n = 8
   Output: 13
   

   
   
   Transfer

   Given a positive integer n, it is necessary to calculate the sum of the bits of all numbers from 1 to n in binary representation.
   
   Examples:
   Input: n = 3
   Output: 4
   
   Input: n = 6
   Output: 9
   
   Input: n = 7
   Output: 12
   
   Input: n = 8
   Output: 13
   
   
   
3. Find the repeating and the missing
   

   Given an unsorted n-sized array of integers. Array elements are in range from 1 to n. One number from set {1, 2, ... n} is missing and one number occurs twice in array. Find these two numbers.
   
   Examples:
   
   arr [] = {3, 1, 3}
   Output: 2, 3 // 2 is missing and 3 occurs twice
   
   arr [] = {4, 3, 6, 2, 1, 1}
   Output: 1, 5 / / 5 is missing and 1 occurs twice
   
   

   
   
   Transfer

   An unsorted array of integers of dimension n is given. Elements of the array - a sequence of numbers from 1 to n. One number in the sequence is skipped and one is repeated. You need to find these numbers.
   
   Examples:
   
   arr [] = {3, 1, 3}
   Output: 2, 3 // 2 skipped, 3 repeats
   
   arr [] = {4, 3, 6, 2, 1, 1}
   Output: 1, 5 // 5 skipped, 1 is repeated
   
   
   
   

Solutions

1. Question 1

   The correct answer was found - 33.3 km.
   
   
   
2. Question 2

   The solution is to number the bottles in the ternary system, where each category corresponds to the action of each prisoner in relation to the bottle:
   0 - did not drink,
   1 - drank on the first day
   2 - drank on the second day.
   So, for example, a bottle with code 11201 will mean that prisoners drank 1,2 and 5 on the first day, the third prisoner drank on the second day, and the fourth did not drink - respectively, if 1,2 and 5 died on the first day, and the third on - the second day, then this bottle is poisoned.
   In total, unique combinations are 3 ^ 5 = 243, i.e. as concluded in 48 hours, it will be possible to unambiguously determine which bottle is poisoned.
   
   A solution was also proposed in the comments.
   
   
   
3. Task 1

   The solution involves the sequential summation of values, moreover, 0 are considered as "-1". One of the options was proposed here.
   
   
   
4. Task 2

   Variant of the correct solution was the proposal in the comment.
   
   
   
5. Task 3

   One solution is to walk through the array using the absolute value of the element as an index and changing the sign of the element under this index. Then the index of an element that has already been marked negative is a duplicate value.
   
   For the second pass, you need to find a positive value:
   
   

   #include
   #include
   void printTwoElements(int arr[], int size)
   {
       int i;
       printf("\n The repeating element is");
       for(i = 0; i < size; i++)
       {
           if(arr[abs(arr[i])-1] > 0)
               arr[abs(arr[i])-1] = -arr[abs(arr[i])-1];
           else
               printf(" %d ", abs(arr[i]));
       }
       printf("\nand the missing element is ");
       for(i=0; i0)
               printf("%d",i+1);
       }
   }
   /* Driver program to test above function */
   int main()
   {
       int arr[] = {7, 3, 4, 5, 5, 6, 2};
       int  n = sizeof(arr)/sizeof(arr[0]);
       printTwoElements(arr, n);
       return 0;
   }

   
   
   The complexity of the algorithm is O (n).