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

Questions

1. Total distance traveled by bee
   

   Two trains are going along each track. The speed of the first train is 50 KMs / h and the speed of the second train is 70 KMs / h. A distance between two trains is 100 KMs. The first flies from the first train to the second train. Once it reaches the second train ... Calculate the total distance traveled by the bee. Speed ​​of bee is 40 KMs / h.

   
   
   Transfer

   Two trains in the same way go towards each other. The speed of the first train is 50 km / h, the speed of the second one is 70 km / h. A bee begins to fly between trains when the distance between them is 100 km. The 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.
   Calculate the distance covered by the bee, 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 a bottle of wine. Soon after they’re trying to get a bottle of poisoned wine. Unfortunately, it’s not a rule. However, the King has 5 prisoners. It doesn’t help you. After drinking the poisoned wine, one dies within 24 hours. The King needs to continue to plan. It is a quest to ensure that it has reached the level of the poisoned wine bottle.
   

   
   
   Transfer

   The king of a small country invited 240 senators for the annual celebration. By tradition, each senator presents a bottle of wine to the king. 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 do not know who this senator is, is not poisoned by the bottle, besides, it is impossible to detect the poison. In the royal prison there are 5 prisoners sentenced to speedy death. The king decides with their help to calculate the poisoned bottle of wine. The poison will act only after 24 hours - the drunkard dies. The king needs to find out which bottle is poisoned in 2 days in order to continue the planned activities. How can he distribute the wine among the prisoners to ensure that he finds the poisoned bottle in 48 hours?
   

Tasks

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

   Given the number of 0s and 1s, it contains the 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. It is necessary 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 (Input array indices)
   
   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
   

   Number of 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 the 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 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. The elements of the array are a sequence of numbers from 1 to n. One number in the sequence is missing and one is repeated. It is necessary to find these numbers.
   
   Examples:
   
   arr [] = {3, 1, 3}
   Output: 2, 3 // 2 skipped, 3 repeated
   
   arr [] = {4, 3, 6, 2, 1, 1}
   Output: 1, 5 // 5 skipped, 1 repeated
   
   
   
   

Solutions

1. Question 1

   The correct answer was found - 33, 3 km.
   
   
   
2. Question 2

   The solution is to number the bottles with a number in the ternary system, where each discharge 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.
   For example, a bottle with the code 11201 will mean that prisoners drank 1,2 and 5 on the first day, drank the third prisoner on the second day, and did not drink the fourth one, respectively, if 1,2 and 5 died on the first day, and the third - the second day, this bottle is poisoned.
   Total unique combinations 3 ^ 5 = 243, i.e. As a prisoner, by the expiration of 48 hours, it will be possible to unambiguously determine which bottle is poisoned.
   
   The solution was also proposed in the comments.
   
   
   
3. Task 1

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

   The right decision option was a sentence in the comments.
   
   
   
5. Task 3

   One solution is to go 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<stdio.h> #include<stdlib.h> 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; i<size; i++) { if(arr[i]>0) 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).