Выпуск#4: ITренировка — актуальные вопросы и задачи от ведущих компаний

После некоторого перерыва, мы возобновляем выпуски ITренировки.



Предлагаю Вашему вниманию подборку интересных задач, встречающихся на собеседованиях в IT-компании — их регулярное решение позволит немного подготовиться к предстоящему собеседованию и просто держать себя в тонусе.

Ниже приведены вопросы и задачи для соискателей в Google, с различным уровнем сложности.

Вопросы

1. Прямоугольный торт
   

   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.

   
   
   Перевод

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

   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?

   
   
   Перевод

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

Задачи

1. Подстрока с анаграммой
   

   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
   

   
   
   Перевод

   Дано 2 слова. Найти, имеет ли второе слово вхождение подстроки, которая является анаграммой первого слова:
   LGE, GOOGLE => True
   GEO, GOOGLE => False
   
   
   
2. Минимум автобусов (пересадок)
   

   A city bus station information, example, bus No. 1 stops at abcd station, bus No. 2 stops at cefg station. Then a-d you only need to take No. 1, thus return 1, a-g 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.

   
   
   Перевод

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

   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

   
   
   Перевод

   Дан массив целых чисел (могут быть и отрицательные) упорядоченных произвольно. Найти подмассив с максимальной суммой.
   
   
   

Ответы будут даны в течение следующей недели — успейте решить. Удачи!

Решения

1. Вопрос 1

   В комментариях верно нашли решение:
   

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

   
   
   
   
2. Вопрос 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. Задача 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. Задача 2

   alexeykuzmin0 предложил верное решение использовать BFS01:
   

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

   
   
   
   
5. Задача 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;
   }