Любите решать задачи на интервью?
Я люблю решать задачки, особенно если они не на потерю this или какие-нибудь штуки в классах, а больше про логику и структуры данных. Так что в целом я почти всегда рада лайв-кодингу, особенно когда попадаются интересные задачи.
Поэтому когда я увидела афишу лекции «Красивые математические задачи с айтишных собеседований» с преподавателем математики Бориса Трушина (известен своим youtube-каналом, где доходчиво объясняет математику), собралась и пошла.
Было интересно, разобрали 7 задач (парочка из них никогда не была замечена на собеседованиях, но и пусть). Записываю задачи и то, что может помочь найти решение в других задачах будущей мне :)
Красные и белые колпаки
Царь решил сыграть в игру со своими мудрецами: собрал 30 мудрецов, на каждого надел красный или белый колпак. Каждый мудрец видит все остальные колпаки, но не знает цвета своего колпака. Мудрецы не могут никак подавать сигналы другим о цвете их колпаков. Они сидят в комнате, и каждую минуту туда заходит проверяющий: как только хоть один мудрец правильно назовет цвет своего колпака — все будут свободны. Если называешь неправильно — казнь. Если ни один мудрец не назовет правильно цвет своего колпака в течение дня — все будут казнены.
Пока мудрецы сидели, мимо двери проходил человек и сказал: “О, среди вас как минимум 1 белый колпак!”. Через какое-то время все люди в белых колпаках встали и правильно назвали свой цвет.
Как так получилось?
Подход
Попробовать решить задачу для простейшего случая (1 белый и все остальные красные колпаки). Затем чуть сложнее (2 белых и все остальные красные), так доходим до решения.
Обращаем внимание на то, что поменяло общее знание (когда проходящий сказал, что есть как минимум 1 белый колпак).
Когда разобьётся яйцо?
У нас есть 100-этажное здание и 2 яйца. Вам нужно определить наивысший этаж, с которого можно уронить яйцо и не разбить его — причем сделать это нужно, конечно же, за минимальное количество бросков.
(если яйцо не разбилось — его можно продолжать использовать; если разбилось — нельзя использовать, естественно)
Подход
Когда одно яйцо разбилось, вторым мы можем только перебирать подряд этажи. Можно попробовать разделить более-менее равномерно этажи на одинаковые диапазоны, и так проверять.
Но при одинаковом диапазоне (проверили сначала n, затем 2n, затем 3n) — для второго яйца количество попыток не сокращается (n - 1). Это хотелось бы оптимизировать.
Опять пробуем представить идеальный вариант: в последней попытке нам нужно проверить 1 этаж, и дальше уже от этого думаем.
Как доехать с пустым баком?
Есть круговая трасса с односторонним движением, по периметру этой трассы как-то рандомно расставлены канистры с бензином. Расстояние между канистрами может быть какое угодно, в каждой канистре может быть сколько угодно бензина, но известно, что во всех канистрах суммарно — бензина ровно на то, чтобы машина проехала круг по этой трассе. Считаем, что машина тратит бензин равномерно.
Машина с пустым баком на старте. Мы можем заглянуть во все канистры.
Нам надо доказать, что как бы ни стояли канистры и сколько бы бензина в них не было, мы можем найти канистру, стартуя с которой мы сможем проехать весь круг.
(очевидно, заливая бензин из всех встреченных по пути канистр)
Подход
Рекомендуется рисовать. Я в такие задачки не очень умею, если что, объяснение вот здесь.
Бесконечный поезд
По кольцевой железной дороге едет поезд, последний вагон которого сцеплен с первым так, что внутри можно свободно перемещаться между вагонами. Вы оказались в одном случайном вагоне и ваша задача — подсчитать их общее количество. В каждом вагоне можно включать и выключать свет, но начальное положение переключателей случайное и заранее неизвестно.
Подход
Объяснение, а вообще снова решаем для одного вагона, потом для двух, трех и тд. Надо придумать, что станет для нас маркером посещенности вагона.
Тюрьма и лампочка
В тюрьме 100 заключённых сидят по одиночным камерам. Начальник тюрьмы решил организовать такую игру. Их по одному иногда будут приводить в комнату, где нет ничего, кроме одной лампочки, которую заключённому разрешается включить или выключить. Гарантируется, что рано или поздно каждый из заключенных побывает в комнате с лампочкой сколько угодно раз. В любой момент заключённый, приведённый в комнату с лампочкой, может объявить, что все заключенные уже побывали в комнате хотя бы по одному разу. Если он прав, то всех отпустят, если нет — казнят. Заключенных собрали вместе в этой комнате, объявили правила, разрешили договориться, придумать стратегию, и, уходя, оставить выключатель в том положении, в котором захотят. Придумайте стратегию, которая позволит им освободиться
Подход
Объяснение, две вещи над которым надо подумать:
- нам нужен человек-счетчик
- добиться того, чтобы каждый заключенный был посчитан счётчиком только один раз