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

Questions

1. Bacterium in vitro
   

   Logical task of increasing. How long does it take for bacteria? Each bacteria divides into 2 same size bacteria each second.

   
   
   Transfer

   Logical problem - 1 bacterium by dividing fills the tube per minute. How long will it take to fill the tube, if at the start of 4 bacteria? Each bacterium is divided into 2 bacteria of the same size every second.
   
2. 25 horses
   

   You can find the top number of 3.
   

   
   
   Transfer

   It is necessary to determine the minimum number of races for which you can identify the top three winners among 25 horses. In one race, you can start a maximum of 5 horses, the stopwatch is not provided.
   

Tasks

1. Build a string with subsets
   

   Two strings s1 and s2 are given. You have both s1 and s2 as the s3 is minimum.
   
   Example: apple pear => applear
   

   
   
   Transfer

   From the two lines s1 and s2 assemble a new line s3, containing s1 and s2 as sub-sets. s3 must be the minimum length.
   Example: apple pear => applear
   
2. Dictionary sorting of numbers
   

   How will you dictionary sort integers without converting them to strings?
   For ex: 1 2 10 20 100 110 => 1 10 100 110 2 20.

   
   
   Transfer

   How would you sort the integers in a dictionary order without casting them to a string?
   Example: 1 2 10 20 100 110 => 1 10 100 110 2 20.
   
3. Find additional elements in the array
   

   Given two integer arrays A and B.
   B contains exactly the same number as A except two additional numbers. Find the two elements with minimum time and space complexity.
   for ex: A = {1, 4, 2, 6, 3}
   B = {4, 0.7, 6, 3, 2, 1}
   ans: 0 7

   
   
   Transfer

   Given arrays of numbers A and B. Array B contains all the numbers from A + 2 more numbers. Suggest an algorithm for finding these 2 numbers, optimal in terms of speed and amount of memory.
   Example:
   A = {1, 4, 2, 6, 3}
   B = {4, 0.7, 6, 3, 2, 1}
   Result: 0 7
   

Solutions

1. Question 1

   Many commentators answered correctly - 58 seconds. It was possible to come to the answer in a logical way, but someone decided logarithmically :)
   
   
   
2. Question 2

   Many also found the right solution. The answer is 7 runs.
   
   Let us number the horses. The first five races:
   1. 1 2 3 4 5
   2. 6 7 8 9 10
   3. 11 12 13 14 15
   4. 16 17 18 19 20
   5. 21 22 23 24 25
   10 horses were eliminated because they cannot claim a place in the top three.
   
   In the sixth race we will reveal the absolute leader:
   6. 1 6 11 16 21
   
   Now the picture is as follows:
   1 2 3 4 5
   6 7 8 9 10
   11 12 13 14 15
   16 17 18 19 20
   21 22 23 24 25
   
   Another 10 horses dropped out - all the horses of the races, whose leaders came 4 and 5, because they cannot claim prizes, horses of the third group (since their leader took third place and they can count on 4+), and the third horse of the second group, because it can also count only on the 4+ place, as well as the horse who won the 1st place as the absolute leader.
   
   In the seventh race, we identify the first pair of the strongest - they will take pride of place in the top three:
   
   7. 2 3 6 7 11
   
   I considered the case when all the strong horses are in the same group, but rearranging their overall picture does not change.
   
   
   
3. Task 1

   Original solution for Java subsequences:
   

   public class GFG_1 { String a , b; // Prints super sequence of a[0..m-1] and b[0..n-1] static void printSuperSeq(String a, String b) { int m = a.length(), n = b.length(); int[][] dp = new int[m+1][n+1]; // Fill table in bottom up manner for (int i = 0; i <= m; i++) { for (int j = 0; j <= n; j++) { // Below steps follow above recurrence if (i == 0) dp[i][j] = j; else if (j == 0 ) dp[i][j] = i; else if (a.charAt(i-1) == b.charAt(j-1)) dp[i][j] = 1 + dp[i-1][j-1]; else dp[i][j] = 1 + Math.min(dp[i-1][j], dp[i][j-1]); } } // Create a string of size index+1 to store the result String res = ""; // Start from the right-most-bottom-most corner and // one by one store characters in res[] int i = m, j = n; while (i > 0 && j > 0) { // If current character in a[] and b are same, // then current character is part of LCS if (a.charAt(i-1) == b.charAt(j-1)) { // Put current character in result res = a.charAt(i-1) + res; // reduce values of i, j and indexs i--; j--; } // If not same, then find the larger of two and // go in the direction of larger value else if (dp[i-1][j] < dp[i][j-1]) { res = a.charAt(i-1) + res; i--; } else { res = b.charAt(j-1) + res; j--; } } // Copy remaining characters of string 'a' while (i > 0) { res = a.charAt(i-1) + res; i--; } // Copy remaining characters of string 'b' while (j > 0) { res = b.charAt(j-1) + res; j--; } // Print the result System.out.println(res); } /* Driver program to test above function */ public static void main(String args[]) { String a = "apple"; String b = "pear"; printSuperSeq(a, b); } } 

   
   
   
   
4. Task 2

   The original solution was to write a comparator and compare the numbers by quotient and the remainder of the division:
   

    Algorithm: Compare quotients and reminders import java.util.Arrays; import java.util.Comparator; public class DictionarySort { public static void main(String[] args) { Integer[] array = new Integer[] { 1, 2, 10, 20, 100, 110 }; Arrays.sort(array, new Comparator<Integer>() { @Override public int compare(Integer o1, Integer o2) { // TODO Auto-generated method stub int quotient1 = o1 / 10; int reminder1 = o1 % 10; int quotient2 = o2 / 10; int reminder2 = o2 % 10; if (quotient1 != 0 && quotient2 != 0) { if (quotient1 == quotient2) return 0; int msd1 = 0; int msd2 = 0; if (quotient1 >= 10) msd1 = quotient1 / 10; else msd1 = quotient1; if (quotient2 >= 10) msd2 = quotient2 / 10; else msd2 = quotient2; if (msd1 == msd2) return quotient1 - quotient2; if (msd1 != msd2) return msd1 - msd2; } if (quotient1 == 0 && quotient2 == 0) return reminder1 - reminder2; if (quotient2 != 0 && quotient1 == 0) { while (quotient2 >= 10) quotient2 /= 10; return reminder1 - quotient2; } if (quotient1 != 0 && quotient2 == 0) { while (quotient1 >= 10) quotient1 /= 10; return quotient1 - reminder2; } return 1; } }); System.out.println(Arrays.toString(array)); } } 

   
   
   
   
5. Task 3

   Initial solution:
   
   

    public int[] findTwo(int[] a, int[] b) { int sumA = 0, squareSumA = 0; for (int i = 0; i < a.length; i++) { sumA += a[i]; squareSumA += a[i] * a[i]; } int sumB = 0, squareSumB = 0; for (int i = 0; i < b.length; i++) { sumB += b[i]; squareSumB += b[i] * b[i]; } int twosum = sumB - sumA; int squareSum = squareSumB - squareSumA; int param1 = 2; int param2 = 2 * twosum; int param3 = twosum * twosum - squareSum; int[] res = new int[2]; int sqrtdiff = (int) Math.sqrt(param2 * param2 - 4 * param1 * param3); res[0] = (param2 - sqrtdiff) / (2 * param1); res[1] = (param2 + sqrtdiff) / (2 * param1); return res; }