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

( "Other").

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

Мы публикуем самые интересные примеры таких задач, для решения которых требуется знание математики на школьном уровне или просто смекалка. Некоторые из них приводят сами компании, некоторые - публикуют пользователи, которые ходили на собеседование, некоторые - собраны на популярных сайтах задач.
Что спрашивают в Apple.
1. задача на логику. Шелдон Купер (тот самый гениальный физик из популярного сериала) дошел в игровом квесте в погоне за сокровищами до последнего рубежа. Перед ним - две двери, одна ведет к сокровищу, вторая - к смертельно опасному лабиринту. У каждой двери стоит стражник, каждый из них знает, какая дверь ведет к сокровищу. Один из стражников никогда не врет, другой - врет всегда. Шелдон не знает, кто из них врун, а кто нет. Прежде чем выбрать дверь, задать можно только один вопрос и только одному стражнику.
Вопрос: что спросить Шелдону у стражника, чтобы попасть к сокровищу?
2. землю захватили инопланетяне. Они планируют уничтожить всю планету, но решили дать человечеству шанс. Они выбрали десяток самых умных людей и поместили их в абсолютно темную комнату, посадив в ряд, один за другим. На каждого из людей надели по шляпе, шляпы всего двух цветов - розовые и зеленые. После того, как все шляпы оказываются на головах, свет включается.
Инопланетянин начинает с последнего человека в ряду и спрашивает о том, какого цвета шляпа у него на голове. Других слов, кроме цвета шляпы, произносить нельзя. Отмалчиваться - тоже. Таким образом, если он отвечает верно, остается в живых, ошибается - его убивают.
Нельзя посмотреть, какого цвета ваша шляпа, но можно договориться о некоем принципе, по которому отвечать всем. Расположение шляп - случайное, комбинации могут быть любыми, вам видны все шляпы, которые расположены перед вами.
Вопрос: что нужно отвечать, чтобы выжило как можно больше людей?
Что спрашивают в Adobe.
3. у вас 50 мотоциклов, с заполненным топливом баком, которого хватает на 100 км езды.
Вопрос: используя эти 50 мотоциклов, как далеко вы сможете заехать (учитывая, что изначально они находятся в условно одной точке пространства?
Что спрашивают в Microsoft.
4. у вас бесконечный запас воды и два ведра - на 5 литров и 3 литра.
Вопрос: как вы отмерите 4 литра?
5. у вас два отрезка веревки. Каждый таков, что если поджечь его с одного конца, он будет гореть ровно 60 минут.
Вопрос: имея только коробку спичек, как отмерить с помощью двух отрезков такой веревки 45 минут (рвать веревки нельзя?
Что спрашивают в Google.
6. у вас имеется 8 шариков одинакового вида и размера.
Вопрос: как найти более тяжелый шарик, используя весы и всего два взвешивания?
Что спрашивают в Qualcomm.
7. эту задачку описал пользователь, которого собеседовали на позицию Senior Systems Engineer. Он отметил в описании задачи, что у него был свой ответ, по поводу которого он долго спорил с человеком, проводившим собеседование.
Предположим, у нас происходит 10 пакетных передач данных по беспроводной сети. Канал не очень качественный, так что есть вероятность 1/10, что пакет данных не будет передан. Трансмиттер всегда знает, удачно или неудачно был передан пакет данных. Когда передача неудачная, трансмиттер будет передавать пакет до тех пор, пока не преуспеет.
Вопрос: какую пропускную способность канала получаем?
Что спрашивают в "Яндексе".
8. эту задачу предлагали решить для вступления в школу анализа данных в феврале 2014 года. Ответа на задачи из "Яндекса" у нас, к сожалению, нет.
Игра состоит из одинаковых и независимых конов, в каждом из которых выигрыш происходит с вероятностью p. когда игрок выигрывает, он получает 1 доллар, а когда проигрывает - платит 1 доллар. Как только его капитал достигает величины N долларов, он объявляется победителем и удаляется из казино.
Вопрос: найдите вероятность того, что игрок рано или поздно проиграет все деньги, в зависимости от его стартового капитала K.
9. эту задачу предлагали решить разработчикам на собеседовании, и она больше связана непосредственно с программированием, чем предыдущие примеры.
Имеется морфологический словарь объемом примерно 100 000 входов, в котором глаголы совершенного и несовершенного вида помещены в отдельные статьи (то есть "Делать" и "сделать" считаются разными словарными входами. Вам требуется найти в словаре такие видовые пары и "Склеить" статьи в одну.
Вопрос: опишите общий сценарий решения такой задачи и примерный алгоритм поиска видовых пар.
Ответы:
1. можно спросить любого, при этом задать вопрос так: "какая дверь, по мнению другого стражника, правильная? Таким образом, если он спросит у правдивого, то получит данные о том, какая дверь ведет к лабиринту, ведь врущий стражник всегда врет. В том случае, если же он спросит у врущего стражника, опять же, узнает, какая дверь ведет к лабиринту, ведь тот соврет о двери, на которую укажет правдивый стражник.
2. первый отвечающий считает количество зеленых шляп перед собой, если это нечетное число, он называет "Зеленый", если четное - "розовый". Следующий, видя количество и цвет шляп перед собой, может таким образом вычислить, какого цвета шляпа у него на голове (к примеру, если зеленых все еще нечетное количество, то очевидно, что на нем - розовая), и так далее. Таким образом гарантированно выживают 9 из 10, а у первого отвечавшего шанс 1 к 1.
3. самый простой ответ: завести их все одновременно и проехать 100 км. Но есть и другое решение. Сначала переместите все мотоциклы на 50 км. Затем, перелейте топливо из половины мотоциклов в другую половину. У вас таким образом - 25 мотоциклов с полным баком. Проезжайте еще 50 км и повторите процедуру. Так можно забраться на 350 км (не учитывая того топлива, которое останется от "Лишнего" мотоцикла при разделе 25 надвое.
4. наполните водой пятилитровое ведро и вылейте часть воды в трехлитровое. У вас сейчас 3 литра в маленьком ведре и 2 - в большом. Опустошите маленькое ведро и перелейте туда оставшиеся 2 литра из большого. Снова наполните большое ведро и перелейте из него воду в малое. Там уже есть 2 литра воды, так что долить придется литр, а в большом останется 4 литра.
5. один из отрезков поджигается с двух концов, одновременно с этим поджигается второй отрезок, но с одного конца. Когда первый отрезок догорит полностью, пройдет 30 минут, от первого также останется 30-минутный отрезок. Поджигая его с двух концов, получим 15 минут.
6. отберите 6 шариков, разделите их на группы по 3 шарика и положите на весы. Группа с более тяжелым шариком чашу перетянет. Выберите любые 2 шарика из этой тройки и взвесьте. Таким образом, если тяжелый шарик среди них, вы это узнаете, если они весят одинаково - тяжелый тот, что остался. В том случае, если же более тяжелого шарика в группах по 3 шарика не оказалось, он - среди 2 оставшихся.
7. по версии пользователя, ответ должен был быть 9 пакетов в секунду. Но человек, проводивший интервью, с ним не согласился, правда, ответа не назвал, но повторял, что "из-за ретрансмиссии пропускная способность должна быть уменьшена больше, чем на 1/10". Other@sci.