Выпуск#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

   Перевод

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

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

Автор: reci

Источник