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

Questions

1. Black and white balls
   

   You have 20 white and 13 black balls in a bag. You pull out 2 balls one after another. If you are a ball of light, then you can replace it with a black ball. Once you take out the balls, keep reducing. What would be the ball in the bag?

   
   
   Transfer

   You have in your bag 20 white and 13 black balls. You consistently pull 2 ​​balls. If they are of the same color, then you replace them with a white ball, if they are of different colors, you replace them with a black ball. The balls are not returned to the bag, so their number decreases there. What will be the color of the last ball left in the bag?
   
   
   
2. Count the eggs
   

   I wouldn’t turn up one day. So when he came next I demanded explanation from him. He told me the following story:
   It is a carrot that has been banged up. However, a careful gentleman has been given to him for damages. The number of eggs was not reduced between 50 and 100. It was also a rule. , but if it counted by 5's at a time, it remained 3 eggs at 10 cent a piece. The gentleman made some quick calculations and paid peddler adequately.
   How much did the gentleman pay for eggs?

   
   
   Transfer

   Once a peddler, who brings me fresh eggs daily, did not come. He appeared the next day and I asked him to explain the reason for the absence. He told the following story:
   On the eve of the morning, he left the house with a basket full of eggs to make a daily round of the street. Next to him, the car sped at full speed and touched the basket, so that all the eggs broke. The driver, however, turned out to be a gentleman and offered to pay for the damage. The pedlar could not remember the exact number of eggs in the basket, only that there were from 50 to 100. He also remembered that if you chose 2 or 3 eggs, then there would be no eggs in the basket, and if 5, then it should there were 3 eggs left. He sold eggs for 10 cents apiece. The motorist quickly figured in his mind and gave the hawker the exact amount for the broken eggs. How much did he pay?
   
   
   

Tasks

1. Find median in row wise sorted matrix
   

   The pattern is given. It is assumed that r * c is always odd.
   ')
   Examples:
   
   Input:
   1 3 5
   2 6 9
   3 6 9
   Output: Median is 5
   If we put the array A [] = 1 2 3 3 5 6 6 9 9
   
   Input:
   1 3 4
   2 5 6
   7 8 9
   Output: Median is 5
   

   
   
   Transfer

   Given a matrix with elements sorted line by line, of size r * c. We need to find the median of the matrix. It is assumed that r * c is always odd.
   Examples
   
   Entrance:
   1 3 5
   2 6 9
   3 6 9
   Output: Median - 5
   In the form of a sorted array: A [] = 1 2 3 3 5 6 6 9 9
   
   Input:
   1 3 4
   2 5 6
   7 8 9
   Output: Median - 5
   
   
   
2. Smallest single digit expression
   

   We give you your opinion. It can be seen that it has reached the maximum 10 (limit) times.
   
   Examples:
   
   Input: N = 7, D = 3
   Output: 3/3 + 3 + 3
   Explanation: 3/3 = 1, and 1 + 3 + 3 = 7
   This is the minimum expression.
   
   Input: N = 7, D = 4
   Output: (4 + 4 + 4) / 4 + 4
   Explanation: (4 + 4 + 4) = 12, and 12/4 = 3 and 3 + 4 = 7
   Also this is the minimum expression. Although
   you may find another expression but that
   expression can have only five 4's
   
   Input: N = 200, D = 9
   Output: Expression not found!
   Explanation: Not possible within 10 digits.
   

   
   
   Transfer

   Given the number N and the digit D. It is necessary to make an expression that results in N and contains only D. The operations +, -, *, / are admissible. It is necessary to find an expression of minimum length satisfying the conditions, taking into account that D can occur in the expression no more than 10 times.
   
   Input: N = 7, D = 3
   Output: 3/3 + 3 + 3
   Explanation: 3/3 = 1, and 1 + 3 + 3 = 7
   
   Input: N = 7, D = 4
   Conclusion: (4 + 4 + 4) / 4 + 4
   Explanation: (4 + 4 + 4) = 12, and 12/4 = 3 and 3 + 4 = 7
   
   Input: N = 200, D = 9
   Conclusion: Expression not found!
   Explanation: Cannot be executed with a 10-digit limit.
   
   Note: the third example looks like a challenge
   
   
   
3. Minimum swaps to bring them all together
   

   Given an array of n positive integers and a number k. It is required to bring together the minimum number of swaps.
   
   Input: arr [] = {2, 1, 5, 6, 3}, k = 3
   Output: 1
   
   Explanation:
   To bring elements 2, 1, 3 together, swap element '5' with '3' such that final array will be:
   arr [] = {2, 1, 3, 6, 5}
   
   Input: arr [] = {2, 7, 9, 5, 8, 7, 4}, k = 5
   Output: 2
   

   
   
   Transfer

   Given an array of n positive integers and the number k. Find the number of permutations needed to collect all the elements, less than or equal to k, alongside.
   
   Input: arr [] = {2, 1, 5, 6, 3}, k = 3
   Output: 1
   
   Explanation:
   It is enough to change 5 and 3 places:
   arr [] = {2, 1, 3, 6, 5}
   
   Input: arr [] = {2, 7, 9, 5, 8, 7, 4}, k = 5
   Output: 2
   
   
   

Solutions

1. Question 1

   There must be a black ball, the answer was found right.
   
   
   
2. Question 2

   Motorist paid for 78 eggs, in the comments was found the right solution.
   
   
   
3. Task 1

   A simple approach is to place all matrix elements in a sorted array and find the median. The complexity of the time and place - O (r * c).
   
   An effective solution is to use binary search. The idea is that before the median there should be exactly n / 2 numbers that are smaller, the solution was proposed in the comment .
   
   Initial solution:
   
   

   // C++ program to find median of a matrix // sorted row wise #include<bits/stdc++.h> using namespace std; const int MAX = 100; // function to find median in the matrix int binaryMedian(int m[][MAX], int r ,int c) { int min = INT_MAX, max = INT_MIN; for (int i=0; i<r; i++) { // Finding the minimum element if (m[i][0] < min) min = m[i][0]; // Finding the maximum element if (m[i][c-1] > max) max = m[i][c-1]; } int desired = (r * c + 1) / 2; while (min < max) { int mid = min + (max - min) / 2; int place = 0; // Find count of elements smaller than mid for (int i = 0; i < r; ++i) place += upper_bound(m[i], m[i]+c, mid) - m[i]; if (place < desired) min = mid + 1; else max = mid; } return min; } // driver program to check above functions int main() { int r = 3, c = 3; int m[][MAX]= { {1,3,5}, {2,6,9}, {3,6,9} }; cout << "Median is " << binaryMedian(m, r, c) << endl; return 0; } 

   
   
   
   
4. Task 2

   Solution option in the comments
   
   
   
5. Task 3

   Solution option in the comments