10 математических и логических задач с собеседований в Apple, Google, Adobe и Microsoft

Кто не хотел бы попасть на работу в Google, Intel, Amazon или Apple? Многие IT-компании известны тем, что на собеседовании задают претендентам каверзные задачи на математику, логику и общую смекалку. Наверное, один из самых известных примеров – вопрос о том, почему канализационные люки круглые. Редакция AIN.UA постаралась найти самые интересные примеры таких задач, для решения которых нужны знания по математике на школьном уровне или просто смекалка. Некоторые из них приводят сами компании, некоторые публикуют пользователи, которые ходили на собеседование, некоторые собраны на популярных сайтах с задачами.

Почти под каждым заданием приведен правильный ответ (или хотя бы один из возможных правильных ответов), набранный шрифтом белого цвета. Увидеть его можно, выделив соответствующую область.

Что спрашивают в Apple

Задача на логику. Шелдон Купер (этот гениальный физик из популярного сериала) дошел в игровом квесте по поиску сокровищ до последнего рубежа. Перед ним две двери, одна ведет к сокровищу, вторая – к смертельно опасному лабиринту. Возле каждой двери стоит часовой, каждый из них знает, какая дверь ведет к сокровищу. Один из часовых никогда не врет, другой – врет всегда. Шелдон не знает, кто из них лжец, а кто нет. Прежде чем выбрать дверь, можно задать только один вопрос и только одному часовому.

Вопрос: что Шелдон должен спросить у часового, чтобы добраться до сокровища?

Ответ: можно спросить любого, при этом сформулировать вопрос так: «Какие двери, по мнению другого стража, правильные?». Если он спросит у правдивого, его ответ укажет, какая дверь ведет в лабиринт, ведь лживый часовой всегда лжет. Если же он спросит у лживого часового – опять-таки, узнает, какие двери ведут в лабиринт, ведь тот солжет о двери, на которую укажет правдивый охранник.

Землю захватили инопланетяне. Они планируют уничтожить всю планету, но решили дать человечеству шанс. Они выбрали десяток самых умных людей и поместили их в абсолютно темную комнату, посадив в ряд, один за другим. На каждого человека надели шляпу, шляпы только двух цветов – розовые и зеленые. После того, как все шляпы оказываются на головах, свет включается.

Инопланетянин начинает с последнего человека в ряду и спрашивает его о том, какого цвета шляпа у него на голове. Других слов, кроме цвета шляпы, произносить нельзя. Отмалчиваться тоже. Если человек отвечает правильно, остается живым, ошибается – его убивают.

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

Вопрос: Что нужно отвечать, чтобы выжило как можно больше людей?

Ответ: Первый, кто отвечает, считает количество зеленых шляп перед собой: если это нечетное число, он называет «зеленый», если четное – «розовый». Следующий, видя количество и цвет шляп перед собой, может таким образом понять, какого цвета шляпа у него на голове (например, если зеленых все еще нечетное количество, то очевидно, что на нем – розовая), и так далее. Таким образом гарантированно выживают 9 из 10, а у того, кто отвечал первым, шанс 1 к 1.

Что спрашивают в Adobe

У вас 50 мотоциклов, каждый с заполненным топливом баком, которого хватает на 100 км езды.

Вопрос: используя эти 50 мотоциклов, насколько далеко вы сможете заехать (учитывая, что изначально они находятся в условно одной точке пространства)?

Ответ: самый простой ответ: завести их все одновременно и проехать 100 км. Но есть и другое решение. Сначала переместите все мотоциклы на 50 км. Затем перелейте топливо из половины мотоциклов в другую половину. У вас таким образом – 25 мотоциклов с полным баком. Проедьте еще 50 км и повторите процедуру. Так можно преодолеть 350 км (не учитывая того топлива, которое останется от «лишнего» мотоцикла после деления 25 надвое).

Что спрашивают в Microsoft

У вас есть бесконечный запас воды и два ведра – на 5 литров и 3 литра.

Вопрос: Как вы отмеряете 4 литра?

Ответ: Наполните водой пятилитровое ведро и вылейте часть воды в трехлитровое. У вас сейчас 3 литра в маленьком ведре и 2 – в большом. Освободите маленькое ведро и перелейте туда 2 литра из большого. Снова наполните большое ведро и перелейте воду в малое. Там уже есть 2 литра воды, поэтому долить придется литр, а в большом останутся 4 литра.

У вас есть два отрезка веревки. Каждый такой, что если поджечь его с одного конца, он будет гореть ровно 60 минут.

Вопрос: Имея только коробку спичек, как отмерить с помощью двух отрезков такой веревки 45 минут (рвать веревки нельзя)?

Ответ: Один из отрезков поджигается с двух концов, одновременно с этим поджигается второй отрезок, но с одного конца. Когда первый отрезок полностью догорит, пройдет 30 минут, от второй веревки также останется 30-минутный отрезок. Подпалив его с двух концов, получим 15 минут.

Задачи в Google

У вас есть 8 шариков одинакового вида и размера.

Вопрос: как найти более тяжелый шарик, используя весы и только два взвешивания?

Ответ: отберите 6 шариков, разделите их на группы по 3 шарика и положите на разные чаши весов. Группа с более тяжелым шариком перетянет. Выберите любые 2 шарика из этой тройки и сравните их вес на разных чашах весов. Если тяжелый шарик среди них, вы это узнаете, если они весят одинаково – тяжелее третий из этой группы. Если же более тяжелого шарика в группах по 3 шарика не оказалось, он – среди оставшихся двух.

Задачи в Qualcomm

Эту задачку описал пользователь, с которым было собеседование на позицию senior systems ENGINEer. В описании он отметил, что у него был свой ответ, о котором он долго спорил с человеком, который проводил собеседование.

Предположим, у нас есть 10 пакетных передач данных по беспроводной сети. Канал не очень качественный, поэтому есть вероятность 1/10, что пакет данных не будет передан. Передатчик всегда знает, успешно или неудачно был передан пакет данных. Когда передача неудачная, трансмиттер будет передавать пакет до тех пор, пока не достигнет успеха.

Вопрос: какую пропускную способность канала мы получаем?

Ответ: по версии пользователя, ответ должен был быть 9 пакетов в секунду. Но человек, проводивший интервью, с ним не согласился, правда, ответ не назвал, но повторял, что «из-за ретрансмиссии пропускная способность должна уменьшиться больше, чем на 1/10».

Задачи в «Яндекс»

Эту задачу предлагали решить для поступления в Школу анализа данных в феврале 2014 года. Ответов на задачи из «Яндекса» у нас, к сожалению, нет.

Игра состоит из одинаковых и независимых конов, в каждом из которых выигрыш происходит с вероятностью p. Когда игрок выигрывает, он получает 1 доллар, а когда проигрывает – платит 1 доллар. Как только его капитал достигает величины N долларов, он объявляется победителем и покидает казино.

Вопрос: найдите вероятность того, что игрок рано или поздно проиграет все деньги, в зависимости от его стартового капитала K.

Эту задачу предлагалось решить разработчикам на собеседовании, и она больше связана непосредственно с программированием, чем предыдущие примеры.

Есть морфологический словарь объемом примерно 100 000 входов, в котором глаголы совершенного и несовершенного вида помещены в отдельные статьи (то есть «делать» и «сделать» считаются разными словарными входами). Вам нужно найти в словаре такие видовые пары и «склеить» статьи в одну.

Вопрос: опишите общий сценарий решения такой задачи и примерный алгоритм поиска видовых пар.

И бонус

Эту задачу приписывают Альберту Эйнштейну – якобы с ее помощью он выбирал себе помощников. Другая почти легендарная история приписывает авторство Льюису Кэрролу. Отметим, что она очень просто решается на бумаге, но если хотите хардкора – попробуйте решить в голове.

На улице стоят пять домов.
Англичанин живет в красном доме.
Испанец имеет собаку.
В зеленом доме пьют кофе.
Украинец пьет чай.
Зеленый дом стоит сразу справа от белого дома.
Тот, кто курит Old Gold, разводит улиток.
В желтом доме курят Kool.
В центральном доме пьют молоко.
Норвежец живет в первом доме.
Сосед того, кто курит Chesterfield, держит лису.
В доме по соседству с тем, где держат лошадь, курят Kool.
Тот, кто курит Lucky Strike, пьет апельсиновый сок.
Японец курит Parliament.
Норвежец живет рядом с синим домом.
Каждый из домов окрашен в отдельный цвет, в каждом доме живет представитель отдельной национальности, у каждого – свой питомец, своя любимая марка сигарет и напиток.