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

Published on December 22, 2017

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

    After a break, we are resuming the release of IT training.

    KDPV

    I bring to your attention a selection of interesting tasks encountered during interviews in IT companies - their regular solution will allow you to prepare a little for the upcoming interview and just keep yourself in good shape.

    Below are questions and tasks for job seekers on Google, with varying difficulty levels.

    Questions


    1. Rectangular cake
      Question: How would you cut a rectangular cake into two equal pieces when a rectangular piece has already been cut out of it? The cut piece can be of any size and orientation. You are only allowed to make one straight cut.

      Transfer
      Как бы Вы разрезали прямоугольный торт на 2 равные части, если от торта уже отрезан прямоугольный кусок. Отрезанный кусок может быть любого размера и ориентирован горизонтально или вертикально. Разрешено сделать только один прямой разрез в любом направлении.

    2. Strong egg
      How Strong is an Egg?

      You have two identical eggs. Standing in front of a 100 floor building, you wonder what is the maximum number of floors from which the egg can be dropped without breaking it. What is the minimum number of tries needed to find out the solution?

      Transfer
      Вам выданы два одинаковых яйца. Стоя перед 100-этажным зданием, Вы прикидываете, какой самый высокий этаж, при падании с которого яйцо не разобьется. За какое минимальное количество попыток Вы сможете это определить?


    Tasks


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

      Transfer
      Дано 2 слова. Найти, имеет ли второе слово вхождение подстроки, которая является анаграммой первого слова:
      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. Then ad you only need to take No. 1, thus return 1, ag is 2, because you need to transfer at station c,
      Ask for a minimum bus you need to take to reach to another station. You can design any data structures.

      Transfer
      Расписание остановок маршрутов автобусов дано в следующем виде: маршрут №1 — следует по остановкам abcd, маршрут №2 — по cefg. Тогда, чтобы проехать a-d потребуется 1 автобус, а-g — потребуется 2 автобуса (пересадка на станции c).
      Найти минимальное количество автобусов, необходимое, чтобы попасть на заданную станцию. Разрешено использовать любые структуры данных.

    3. Subarray maximum amount
      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
      Дан массив целых чисел (могут быть и отрицательные) упорядоченных произвольно. Найти подмассив с максимальной суммой.


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

    Solutions


    1. Question 1
      В комментариях верно нашли решение:
      В первой задаче находим «центр масс» исходного торта на пересечении двух диагоналей. Затем так же находим «центр масс» вырезанного куска. Проводим разрез по линии через эти «центры масс»


    2. Question 2
      Первое, что приходит в голову — простой перебор; перебор с шагом 2 этажа; с фиксированным интервалом побольше. Но оптимальным является подход с уменьшением количества этажей к верхушке здания, тогда можно уложиться за максимум 14 попыток:
      Instead of taking equal intervals, we can increase the number of floors by one 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 floor 27 (14 + 13). If it breaks, we need 12 more tries to find the solution. So the initial 2 tries plus the additional 12 tries would still be 14 tries in 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 100 floors, 14 tries is sufficient to find the solution.

      Для интересующихся более развернутым ответом — MagnetonBora в комментарии предлагает посмотреть уроки Игоря Клейнера.

    3. Task 1
      В комментариях были предложены верные методы:
      скользящее окно. Сложность O(n+m) дополнительная память O(n)

      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 предложил верное решение использовать BFS01:
      Использовать BFS0-1 вместо алгоритма Форда-Беллмана, описанного в вашем решении. Вершины графа — маршруты, ребра — пересечения маршрутов. Изначально инициализируем 0 все маршруты, которые включают в себя начальную остановку. Ответ — минимум из расстояний до всех маршрутов, включающих в себя конечную остановку.


    5. Task 3
      The best way to solve this puzzle is to use Kadane’s algorithm which runs in O(n) time. The idea is to keep scanning through the array and calculating the maximum sub-array that ends at every position. The sub-array will either contain a range of numbers if the array has intermixed positive and negative values, or it will contain the least negative value if the array has only negative values.

      И пример на 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;
      }