Предлагаю Вашему вниманию подборку интересных задач, встречающихся на собеседованиях в IT-компании — их регулярное решение позволит немного подготовиться к предстоящему собеседованию и просто держать себя в тонусе.
Ниже приведены вопросы и задачи для соискателей в Google, с различным уровнем сложности.
Вопросы
- Прямоугольный торт
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 равные части, если от торта уже отрезан прямоугольный кусок. Отрезанный кусок может быть любого размера и ориентирован горизонтально или вертикально. Разрешено сделать только один прямой разрез в любом направлении.
- Крепкое яйцо
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-этажным зданием, Вы прикидываете, какой самый высокий этаж, при падании с которого яйцо не разобьется. За какое минимальное количество попыток Вы сможете это определить?
Задачи
- Подстрока с анаграммой
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
- Минимум автобусов (пересадок)
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).
Найти минимальное количество автобусов, необходимое, чтобы попасть на заданную станцию. Разрешено использовать любые структуры данных.
- Подмассив максимальной суммой
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
ПереводДан массив целых чисел (могут быть и отрицательные) упорядоченных произвольно. Найти подмассив с максимальной суммой.
Ответы будут даны в течение следующей недели — успейте решить. Удачи!
Комментарии (59)
BotanDorin
22.12.2017 15:17Вопрос 1. — Прямоугольный торт
Прямоугольный кусок отрезали от края торта (как нормальные люди), или в произвольном месте(как я)?
reci Автор
22.12.2017 15:18Отрезали от края. Но можно попробовать и в произвольном месте вырезать :)
alexeykuzmin0
22.12.2017 18:58Тогда уж можно и повернуть, а не горизонтально/вертикально резать.
А еще можно сделать сам торт или дырку круглыми.
TregRom
23.12.2017 06:46+1Резать нужно через центр торта и центр отверстия, тогда получим две равные части и не важно где отверстие в середине или скраю
ptyrss
22.12.2017 15:24Честно говоря, ожидал больше от задач.
1 вопрос — задача о бутерброде. Численно решить легко. В общем виде тоже знакомая (там 2 прямоугольника было и надо было через центры проводить).
2 вопрос — классика. Понятно что 2 яйцо кидаем по 1 этажу вверх. Ответы и дальше не пишу (под спойлер загнать не могу).
1 задача — скользящее окно. Сложность O(n+m) дополнительная память O(n)
2 задача — ориентированный граф, кратчайший путь и всё просто.
3 задача — шаблонная задача в 1 проход по массиву.reci Автор
22.12.2017 15:31Можете подавать резюме в Google :)
1 вопрос — в комментарии выше предложили усложнение.
2 вопрос — перебором с первого этажа? А первое яйцо тогда зачем?
Задачи — я думаю, интервьюеры будут смотреть на лаконичность/оригинальность решения в том числе.
tereznikov
22.12.2017 16:57Могу сказать, что вторая задача далеко не так проста как кажется. Цель задачи — «За какое минимальное количество попыток Вы сможете это определить?». Как я понял ваш алгоритм, вы предлагаете бросать яйцо через этаж, то есть кинули яйцо на n'ом этаже, и если оно не разбилось, идете на n + 2 этаж. А если разбилось, спускаетесь на n-1 этаж, и проверяете, если не разбилось, то последний этаж n, если разбилось, то n-2. Если максимальный этаж, с которого яйцо не разобьется это 100, то вам потребуется 51 попыток. Вы через один этаж поднимаетесь до 100 этажа — это 50 попыток, плюс вернетесь на этаж ниже и сбросите яйцо, на 99 этаже, что бы убедиться, что максимальный этаж это не 90. Итого 51 попытка. То есть ответ на вопрос этой задачи, используя ваш алгоритм это — 51. Но на самом деле есть другой алгоритм, который позволяет за максимум 14 ходов узнать на каком этаже разобьется яйцо)
bfDeveloper
22.12.2017 17:39Само упоминание цифры 14 — уже спойлер. Найти оптимальную стратегию не так сложно, и я думаю, что уважаемый ptyrss её знает. Потому как второе яйцо действительно кидается по одному этажу, не смотря на то, что стратегия первого сложнее. А вот доказать оптимальность и придти именно к 14, имхо, сложнее. Мне давали эту задачку, правда не в гугле, и к оптимуму пришлось придти перебором, хотя конечно же можно проще.
tereznikov
22.12.2017 17:57Не правильно понял комментарий ptyrss, и согласен, не следовало писать число.
masterspline
22.12.2017 16:57+1В первой задаче находим «центр масс» исходного торта на пересечении двух диагоналей. Затем так же находим «центр масс» вырезанного куска. Проводим разрез по линии через эти «центры масс». Легкотня (но в стрессе на собеседовании, скорее всего не нашел бы решения, как бы рекрутеры не пытались сделать собеседование максимально расслабленным).
StjarnornasFred
23.12.2017 13:13Способ проще: любой торт с отрезанным куском есть 2 или 3 лежащих рядом прямоугольник. Если особо умные вырезали кусок из середины, то 4. Разрезаем торт на них, а потом каждый из них делим по диагонали.
masterspline
23.12.2017 14:16По условию задачи, вырезанный кусок прямоугольный, но с любым соотношением сторон и ориентацией. Он может быть как угодно повернут относительно исходного торта. Остаток торта на прямоугольники не разрежешь. К тому же разрез нужно сделать единственный.
alexeykuzmin0
25.12.2017 12:12То есть, сделать 7 разрезов вместо одного — это способ проще?
А что вы будете делать, если дырка будет повернута? А если дырка или торт имеют форму круга?
vesper-bot
22.12.2017 17:55ОтветыВопрос 1 — разрезать надо по толщине, поскольку «одинаковые» здесь не означает «по площади»
Вопрос 2 — недавно пробегала, вроде 14. Нужно кидать первое яйцо так, чтобы если оно разбивается в этом броске, оставшихся бросков хватит, чтобы проверить все этажи подряд между текущим и этажом, с которого бросали яйцо предыдущий раз (и оно не разбилось).
Задача 1 — нужно использовать скользящее окно (подстроку) в строке 2 длиной в строку 1, и считать количество конкретных символов в ней. Как совпадет с количествами для строки 1, возвращаем true, иначе false.
Задача 2 — вроде как обычный поиск на графе, только граф надо собрать правильно. Т.е. вершины будут пары станция-автобус, станция-null будут выходы, дальше орграф строим из любой (х, а) в (у, а) дистанция 0, если а не ноль, из (х, а) в (х,0) дистанция 1, из (х,0) в (х, а) дистанция 0, если а не ноль. Дальше ищем кратчайший путь от (х,0) в (у,0). Вообще эта задача на оптимизацию, и вот это решение довольно тупое — просит О(m*n) памяти, может, можно и покороче.
Задача 3 — эту у нас на олимпиаде в 1996м решали, по программированию, кстати. Я тогда был дуб, но решение запомнил — считаем скользящую сумму, пока больше нуля, и отслеживаем максимум, как меньше нуля стала, обнуляем и переносим начало. Решение получается в один проход по массиву чисел.novrm
22.12.2017 18:00В торте ничего считать не нужно.
Нужно резать горизонтально пополам…kardan2
22.12.2017 18:41Ага, а если торт внизу тестовые коржи, а сверху крем? Тогда что? Одному корешки, а другому горшки?
vesper-bot
23.12.2017 08:20А если на торте вишенки стоят, их тоже поровну делить, причем их было 20, а в вырезанный прямоугольник попало три? Нет в задаче — нет в «а если».
kardan2
23.12.2017 08:40Извините, что цепляюсь, но… В задаче сказано про прямоугольный торт, и прямоугольный вырез. Именно прямоугольник, а не параллелепипед. Поэтому задача исключительно двухмерная. Если торт распределен неравномерно по ширине-длине, то задача впринципе некорректна. Поэтому такое равномерное распределение обязано быть. А вот насчет гарантии равномерного распределения по высоте нет ну никак, тем более, что в обычных тортах это распределение более чем неравномерное.
novrm
23.12.2017 20:22Вы специалист по обычным тортам?
Я вот люблю обычный торт-Наполеон.
… и как раз НЕ обычные торты — неоднородны.
alexeykuzmin0
25.12.2017 12:15Торт на фото как раз неоднородный — верхний слой толще, чем любые внутренние слои того же цвета.
novrm
25.12.2017 18:18Если вы еще не поняли — в природе не существует однородных тортов.
Задачка в принципе поставлена некорректно для нестандартного мышления.alexeykuzmin0
25.12.2017 19:07Уверены, что некорректно? В задаче сказано «торт прямоугольный», то есть, двумерный.
novrm
26.12.2017 01:57Вы видели когда нибудь нечто подобное — двумерный торт?
Если объект двумерный — то есть абстракция — то его неприемлемо обзывать трехмерным объектом, каким есть торт…
Даже у листа бумаги есть толщина. А тем более у торта.
Только извращенцы думают об двумерной абстракции и обзывают ее тортом…
Задачка о двумерном торте, который всегда трехмерный — однозначно не для логического, а для творческого мышления.
xryaks
22.12.2017 18:01Вы уж извините, но либо я не понял первый вопрос, либо он тривиальнее.
Зачем какие-то там находить линии и прочее: просто поставьте торт ребром и разрежьте его пополам. Вот и всё:) По-другому объясняя: сделайте разрез в горизонтальной плоскости торта. Не имеет значение что там и как вырезали — куски будут одинаковы.
Как решить второй вопрос «правильно» я не знаю, но знаю, что яйца разбиваются, если их просто так уронить, с рук, не надо высчитывать этажи))reci Автор
22.12.2017 18:14Предположим, что яйцо было обработано известной зубной пастой, не разбивается, если выронить из рук, и даже выдерживает падение с n-ного этажа :)
Скрытый текст
kardan2
22.12.2017 18:39Ваши задачи решаются за три минуты.
1) Есть изначальный прямоугольник, и есть вырезанный прямоугольник. Разрез нужно провести через центры обоих. Причем положение вырезанного куска не важно, если он полностью содержится в первоначальном прямоугольнике.
2) Задача с яйцами стандартна. В общем случае нужно разбить весь диапазон этажей N на карманы (M), так чтобы М*М=N. Если яиц у нас три, тогда M*M*M=N. В нашем случае N=100, значит M=10. Первым делом проверяем 10 этаж, если яйцо не разбилось, тогда 20, если не разбилось, тогда 30… Т.е. первое яйцо тратим на выявление правильного десятка. А уже вторым яйцом узнаем конкретный этаж внутри этого десятка. Итого за 20 бросков мы гарантировано узнаем нужный этаж. Но этот алгоритм можно оптимизировать, если разбить этажи так, чтобы в первый карман попало больше этажей, чем в последний. Например так: 15-14-13-12-11-9-8-7-6-5. Тогда мы гарантировано узнаем нужный этаж за 16 бросков.
Задачи:
1) Переводим символы в числа. Т.е. А-1, B-2, C-3…
Создаем массив длинной равный количеству букв в алфавите. Записываем в него по индексу букв из первого слова количества раз, которое оно там встречается. Если букв нет, ставим 0. За первый проход по второму слову метим позиции, которые содержат буквы, которых нет в нашем первом слове(в первом примере это буква О). Этим бы быстро исключили заведомо неправильные проверки. По оставшимся позициям делаем так: предварительно создаем ещё один массив такой же длины(1 раз). Обнуляем его. И считаем сколько раз каждая буква попалась. Сверяем его с эталонным массивом (по имеющимся буквам). Если получили совпадение, то оно и есть искомый результат. Сложность O(n*m), где n-длина первого слова, m- длина второго слова. Зачему, что если требуется применить поиск несколько раз к разным словам и разным эталонам, то выделенные массивы нужно всего ли обнулять, т.е. сэкономить на процессе выделении памяти.
2) Я здесь вижу немного измененный волновой алгоритм поиска пути в лабиринте. Создаем массив с длиной равной количеству остановок. Забиваем их все очень большим числом. Начальную ячейку (стартовую остановку) делаем равной нулю. Теперь в цикле проигрываем каждый из автобусов. Автобус стартует с первой остановки, запоминая число в ней (K). Если на следующей остановке хранимое число больше, чем K +1, то ложим в него значение k+1.
Если же это число меньше чем K, то заменяем запомненное число вместо K. И так до бесконечности, тока ячейка массива финальной остановки не станет равной какому-то числу меньшему изначального. Значение этого числа и будет равно количеству автобусов. Для надежности (может быть найден не самый оптимальный путь), надо прогнать цикл ещё количество раз, которое равно количеству автобусов.
Хотя только счас дошло, что это не гарантирует оптимальности в случае, когда приходится пересаживаться между одними и теме же автобусами. Но можно обрабатывать только те ячейки, число в которых не больше чем номер цикла (итерации). Мне кажется, что находить оптимальный алгоритм есть смысл зная количество остановок, количество автобусов, среднее число остановок и разряженность остановок (сколько автобусов проходит через одну остановку). Алгоритмы, которые работают хорошо на плотных массивах могут работать не оптимально на разряженных.
Также надо ставить флаг, что за каждый цикл было изменена хоть 1 ячейка. Если флаг не сработал, то задача не имеет решения.
3) За один проход. Достаточно знать максимальную сумму массива, которых заканчивался предыдущей (при проходе) ячейкой. Если она больше 0, то плюсуем её со значением текущей ячейки массива, иначе оставляем только текущее значение. Решение очевидно.alexeykuzmin0
22.12.2017 19:33Вопрос 2. Можно за меньшее число бросаний.
Ключевая идеяОбозначим dp(i, j) ответ на вопрос «какое минимальное количество бросаний требуется для здания высотой i этажей и j яиц?» Очевидно, что dp(i, 1) == i (если яйцо одно, нет выбора, кроме как кидать с каждого этажа). Точно так же dp(0, i) == 0 (если этажей нет, то яйцо не бьется ни с какого этажа).
А дальше переход: dp(i, j) = 1 + min_k{max[dp(k-1, j-1), dp(i-k, j)]}. Почему именно так? Ну, во-первых, нам нужно будет кинуть яйцо 1 раз. Мы будем кидать его с этажа k, и это k выберем таким образом, чтобы максимальное число бросаний, которые нам оставались бы в будущем, было бы минимальным. А сколько бросаний нам останется сделать в будущем? Если яйцо разбилось при падении с этажа k, то у нас осталось для проверки k-1 этаж и j-1 яйцо. А если нет, то, соответственно, i-k этажей и j яиц. Ну и, поскольку нам может не повезти, берем максимум.
Вся задача заключается в подсчете dp(100, 2).kardan2
22.12.2017 20:16Задача 1.
Итак, нам нужно проверить вхождение слова «АБ» в слове из 10 букв. Для этого нам придется сделать цикл из (10-2) итераций, и в каждом проверить на нулевые значения 2 ячейки(потому что первое слово состоит из 2-х букв). Всего 8*2 действий. Теперь нужно найти скажем слово «АБВГ». Оно потребует (10-4) итерации, в каждой из которых нужно проверить 4 элемента массива. Всего действий 6*4=24.
Теперь ищем слово из 4-х букв в слове из 20 букв, т.е. увеличивает в 2 раза оба слова. В результате получаем (20-4)*4 = 64 проверки, а это увеличение в 4 раза, а не в 2!
И где здесь O(n + m)? Тут явная O(n * m).
И именно из-за этого я не стал дальше оптимизировать свой алгоритм, хотя приведение к нулю — просто само бросается в глаза.
Задача с яйцами ваше решение почти не убежало от моего.kardan2
23.12.2017 06:40Всё, дошло. Вместо того, чтобы проверять массив на нули каждый раз, мы можем вести счетчик нулевых (или не нулевых) элементов, фиксируя каждое изменение массива.
Итого, нам нужно сделать n операций для первоначального заполнения отрицательными значениями первого слова, затем посчитать n первых букв во втором слове (первое положение окна), а дальше сделать (m-n-1) сдвигов окна убирая из массива старую букву и прибавляя новую букву. Итого n+n+2*(m-n-1)=2m-2 действий. Но тогда почему O(m+n), а не O(m)? По моим выкладкам получается, что от длины первого слова ничего не зависит.alexeykuzmin0
23.12.2017 11:36Но тогда почему O(m+n), а не O(m)? По моим выкладкам получается, что от длины первого слова ничего не зависит.
Ваша правда
kardan2
22.12.2017 22:04Насчет задачи с автобусами. По всей видимости я не правильно понял условия: если автобус двигается abcd, то он идет из a в b, из b в c, из с в d, а после d он уже никуда не идет. Т.е. его движение однонаправлено. Т.е. он может из a приехать в d, но не может из d приехать в a. Наверное меня сбил с толку пример, где все движение показано в одном направлении. И в таком случае это совсем иная задача.
IBAH_II
23.12.2017 11:16БАЯН! задачу 2 еще в институте разбирали в рамках темы «АЦП половинного деления-последовательного приближения».
Решение в лоб — последовательное приближение, но тут надо использовать комбинированный метод.
Сначала нужно идти половинным приближением (1,2,4,8,16,32,64, бац!), когда первое яйцо разобьется, откатить на предыдущий цикл и продолжить последовательным приближением (33,34,35...)
итого при разбитии яйца на N этаже
методом последовательного приближения = N попыток
методом половинного последовательного приближения = floor(log2(N))+(N-2^(floor(log2(N))))
Вопрос в задаче, как и в большинстве подобных задач, поставлен некорректно. Отвечая формально на вопрос «За какое минимальное количество попыток Вы сможете это определить?» можно смело отвечать «За одну попытку! Кинули со первого этажа оно и разбилось.» Может это трудности перевода?alexeykuzmin0
23.12.2017 11:38методом половинного последовательного приближения = floor(log2(N))+(N-2^(floor(log2(N))))
При N=100 по этой формуле получается 42 попытки, при оптимальном решении в 14.
kardan2
23.12.2017 11:43Вас не смущает, что по вашему алгоритму этаж 63 будет найден за 7+30=37 попыток?
«За одну попытку! Кинули со первого этажа оно и разбилось.» Может это трудности перевода?
Имеется ввиду за какое минимальное количество попыток вы найдете гарантированно ответ. Т.е. рассматривается наихудший вариант при известном количестве этажей. Рациональней оставлять большие промежутки как раз в начале (нижние этаже), а вот на верхних наоборот уплотнять.
В случае же бесконечного количества этаже, мне кажется что надо делать шаг не 2^n, а n^2.
MagnetonBora
23.12.2017 20:10Вопрос #2 — баян, решается либо с помощью динамического программирования, либо аналитически. Разбиралась на типичном программисте, а так же в видео уроках Игоря Клейнера (уроки по динамическому программированию и интеревью для программистов).
reci Автор
23.12.2017 20:12Да, про яйцо задача, пожалуй, классическая, как и про автобус с шариками, например. Но баян это для отдельных разработчиков, и такие вопросы ещё задают на собеседованиях, как показывает практика.
stkr
23.12.2017 20:11С яйцами решить «бинарным поиском» не лучший вариант?
stkr
23.12.2017 20:25И последний, это алгоритм кадана или что-то есть лучше?
MagnetonBora
23.12.2017 20:31Насколько мне известно для такой постановки ничего лучшего не придумали.
kardan2
24.12.2017 08:15Какой блин бинарный поиск? При дихотомическом делении у вас на любом шаге может быть либо больше, либо меньше, либо равно. А в данной задаче у вас «меньше» ДОЛЖНО выпадать не больше 2-х раз, причем второй раз на последней попытке.
MagnetonBora
24.12.2017 14:06Скорее всего автор имел в виду имея 1 яйцо максимально приблизить к промежутку этажей (т.е. бросаем с этажа N/2, если разбилось, то искомый этаж находится в промежутке от 1 до N/2-1, если нет — то в промежутке от N/2+1 до N, далее рекурсивно), в котором имеется такой, начиная с которого яйца начинают разбиваться. Дальше имея оставшееся яйцо найти сам этаж последовательным перебором. Это неоптимальное решение, но одно из первых наивных, которые обычно приходят в голову.
kardan2
25.12.2017 00:51В случае, если правильный этаж попадает в первую половину (первое яйцо сразу разбивается), то вторым яйцом придется проходить аж половину пути. Т.е. при полном значении 100 этажей, 49 этаж будет найден за 50! попыток. Это не то что не оптимальное, это одно из худших решений. Хуже только полный перебор.
MagnetonBora
25.12.2017 14:50Ну да, поэтому от кандидата, ожидают другое решение. Оно ИМХО не очень очевидное, если нет опыта решения подобных задач.
Повторюсь, бинарный поиск — это одно из наивных решений, которые, обычно первыми приходят в голову (вместе с полным перебором).kardan2
25.12.2017 17:06+1Даже если есть опыт решения, то не всегда понятно что делать? Не всегда догадываешься, что вообще яйца можно бросать с этажей (и какие действия вообще можно делать). Мне кажется, что правильней показать человеку вариант полного перебора, и попросить его оптимизировать решение.
stkr
25.12.2017 22:56Предлагал самый настоящий бинарный, с делением каждый раз на 2 :)
Просто невнимательно прочитал условия задачи и пропустил самое главное — что яиц всего два.
Тут получается первое яйцо кидаем каждые 10 этажей, как разбилось то второе кидаем через этаж с последнего «целого» десятка.
Медленнее бинарного поиска, но целее будут яйца.
MagnetonBora
23.12.2017 20:16Задача #3 — одна из классических задач на динамическое программирование. Есть куча способов как ее решить. Например алгоритм Кадана (Kadane's algorithm) или с помощью техники «разделяй и властвуй». На образовательном канале Игоря Клейнера имеется несколько разделов, посвященных динамическому программированию. Там подробно разбирается эта задача, а так же задача про 2 яйца (правда там были даны 2 сферы).
asi81
В 3й задаче некорректный перевод — там только один массив. Кроме того, как я понимаю, нужно найти неразрывный подмассив, а не подмножество, как указано в заголовке.
reci Автор
Исправлено.