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

After a break, we resume the training sessions.



I bring to your attention a selection of interesting problems encountered at interviews in an IT-company - their regular solution will allow a little to prepare for the upcoming interview and just keep yourself in good shape.
')
The following are questions and tasks for applicants on Google, with varying levels of difficulty.

Questions

1. Rectangular Cake
   

   Question: Have you already been a cut out of it? The cut piece can be of any size and orientation. You are only allowed to make one straight cut.

   
   
   Transfer

   How would you cut a rectangular cake into 2 equal parts, if a rectangular piece is already cut from the cake? The cut piece can be of any size and is oriented horizontally or vertically. Only one straight cut is allowed in any direction.
   
   
   
2. Strong egg
   

   How Strong is an Egg?
   
   You have two identical eggs. The number of floors has been reached. It is necessary to find out the solution?

   
   
   Transfer

   You are given two identical eggs. Standing in front of a 100-story building, you estimate which is the highest floor, when falling from which the egg does not break. What is the minimum number of attempts you can determine?
   
   
   

Tasks

1. Anagram substring
   

   Given 2 words, return true if it has a substring that is also an anagram of word 1.
   LGE, GOOGLE => True
   GEO, GOOGLE => False
   

   
   
   Transfer

   Given 2 words. Find whether the second word has a substring entry that is an anagram of the first word:
   LGE, GOOGLE => True
   GEO, GOOGLE => False
   
   
   
2. Minimum buses (transfers)
   

   A city bus station information, example, bus No. 1 stops at abcd station, bus no. 2 stops at cefg station. No. 1, thus return 1, ag is 2, because you need to transfer at station c,
   Ask for a bus. You can design any data structures.

   
   
   Transfer

   The schedule of bus routes stops is given as follows: route number 1 - follows the abcd stops, route number 2 - according to cefg. Then, to go through ad you need 1 bus, a-g - you will need 2 buses (changing at station c).
   Find the minimum number of buses needed to get to a given station. Allowed to use any data structure.
   
   
   
3. Maximum amount of subarray
   

   Sub-Array with the Largest Sum
   
   You are given an array with integers (both positive and negative) in any random order. Find the sub-array with the largest sum

   
   
   Transfer

   Given an array of integers (may be negative) ordered arbitrarily. Find the subarray with the maximum amount.
   
   
   

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

Solutions

1. Question 1

   In the comments correctly found a solution:
   

   In the first task, we find the “center of mass” of the original cake at the intersection of two diagonals. Then we also find the "center of mass" of the cut piece. We make a cut along the line through these "centers of mass"

   
   
   
   
2. Question 2

   The first thing that comes to mind is a simple bust; bust with step 2 floors; with a fixed interval more. But the best approach is to reduce the number of floors to the top of the building, then you can meet the maximum of 14 attempts:
   

   You can make it less than the previous increment. For example, let's first try at floor 14. If it breaks, then we need 13 more tries to find the solution. If it doesn't break, then we should try the floor 27 (14 + 13). If it breaks, we need 12 more to find the solution. So the initial 2 tries plus the additional 12 tries in the total. If it doesn't break, we can try 39 (27 + 12) and so on. Using 14 as the initial floor, we can reach up to floor 105 (14 + 13 + 12 + ... + 1) before we need more than 14 tries. Since we only need to cover the floors.
   

   
   For those interested in a more detailed answer - MagnetonBora in the comment offers to see the lessons of Igor Kleiner.
   
   
   
3. Task 1

   The comments suggested the correct methods:
   

   sliding window. O (n + m) Complexity O (n) Additional Memory

   
   

   bool findSubstrAnagram(string s1, string s2){ if(s1.size() > s2.size()) return false; if(s1 == s2) return true; vector<char> mark_s1(256, 0); vector<char> mark_s2(256, 0); for(char c : s1){ mark_s1[c]++; } int count = 0; for(char c : s2){ if(mark_s2[c] < mark_s1[c]){ count++; mark_s2[c]++; } else{ count = 0; fill(mark_s2.begin(), mark_s2.end(), 0); } if(count == s1.size()) return true; } return false; } 

   
   
   
   
4. Task 2

   alexeykuzmin0 offered the right solution to use BFS01:
   

   Use BFS0-1 instead of the Ford-Bellman algorithm described in your solution. The vertices of the graph - routes, edges - the intersection of routes. Initially, we initialize 0 all routes, which include the initial stop. The answer is the minimum of the distances to all routes that include the terminus.
   

   
   
   
   
5. Task 3

   Kadane's algorithm runs in O (n) time. The calculator is not the one that keeps the bottom of the array. If you have an array of
   

   
   And an example on js:
   

    function getMaxSubSum(arr) { var maxSum = arr[0], partialSum = 0; for (var i = 0; i < arr.length; i++) { partialSum += arr[i]; maxSum = Math.max(maxSum, partialSum); if (partialSum < 0) partialSum = 0; } return maxSum; }