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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Что спрашивают в «Яндексе»

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

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

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

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

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

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

И бонус

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

На улице стоят пять домов.

Англичанин живет в красном доме.

У испанца есть собака.

В зеленом доме пьют кофе.

Украинец пьет чай.

Зеленый дом стоит сразу справа от белого дома.

Тот, кто курит Old Gold, разводит улиток.

В желтом доме курят Kool.

В центральном доме пьют молоко.

Норвежец живет в первом доме.

Сосед того, кто курит Chesterfield, держит лису.

В доме по соседству с тем, в котором держат лошадь, курят Kool.

Тот, кто курит Lucky Strike, пьет апельсиновый сок.

Японец курит Parliament.

Норвежец живет рядом с синим домом.

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

Вопрос: Кто пьет воду? Кто держит зебру?

Ответ:Японец держит зебру, норвежец пьет воду.

Это сообщение отредактировал diginborn - 26.02.2015 - 09:29

А что если шляпы 4 зеленые и 6 розовые, тогда эта схема не работает, а Adobe?

Это сообщение отредактировал sнADow - 26.02.2015 - 09:30

бля, так всю жизнь и буду реактором на работе управлять

Это сообщение отредактировал НоскиВуглу - 26.02.2015 - 09:37

Блин, пойду дальше улицы подметать.

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

4 Раза прочел - ни хуя не понял( вроде IQ не низкий

я такие задачи решал на собеседовании в кружок программирования в 96ом году. нихера не изменилось.

ответил только на Microsoft ....
Так что, лучше Винды вы ничо не увидите ближайшие 10 лет

я б не стал такое постить на япе, а то скоро такие задачки начнут давать на собеседовании на кладовщика или грузчика
и так эйчары не отличаются адекватность

Это сообщение отредактировал Cyberik - 26.02.2015 - 09:33

все просто. две двери 1(сокровища) 2(смерть)
Спрашиваешь у стражника про мнение второго, варианты :
1. Если стражник честный, то он честно отвечает что второй стражник полюбому тебе покажет на неправильную дверь (2).
2. Если стражник врун, то он тебе соврет про то, как ответил бы честный стражник(дверь 1), и тоже скажет про дверь (2).

Соотвесно ты в любом случае выбираешь дверь (1).

как я понял и правдивый и врущий охранник укажут на неправильную дверь, поэтому ее не надо выбирать

Пиздец мозгам. Я после вчерашних наркоманских анекдотов знаю только как определить сорт яблок.

Тут тоже забавные http://nazva.net/logic_test1/

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

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

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

Мой ответ проще: Наливаем в 5л ведро 3литра потом еще 2-ва , в трех литровом ведре остается 1 л. Опустошаем 5л. ведро и наливаем сначала 1литр и потом 3литра. Вот так быстрее будет.

5. Поджигаешь с одного конца, как догорит до середины поджигаешь второй конец.
6. Взвешиваешь по 3 шарика на весах. Если равны значит взвешиваешь 2 последних. Если неравны взвешиваешь 2 из трех тяжелых., при равенстве ответ невзвешанный.

"среди 2 оставшихся" не есть тот ответ, что требует условие. К такому же ответу можно прийти, делая взвешивания групп 4+4, потом 2+2.

раньше проще вопросы были:
- родственники за границей имеются?
- судимость была?

Это сообщение отредактировал PSBS - 26.02.2015 - 09:49

проехать на 50-ти мотоциклах одновременно? че там курите?

Вот наверное поэтому порой компьютерные программы бывают такие замороченные раз там такие креативные люди сидят!

Про ведра с водой сразу сообразил, задачка с детства. 5ти литровую заполняем, выливаем до краев в 3-х литровое, в 5-ти литровом остается 2 литра. выливаем 3 литра на землю, сливаем оставшиеся 2 с 5-ти литрового, заполняем снова 5-ти литровое полностью и сливаем в 3-х литровое, где уже есть 2 литра, итого в 5-ти литровом осталось 4 литра.

По описанному ответу шарик, в любом случае, находится в паре с другим. Где, блять, ответ какой все-таки шарик самый тяжелый из оставшихся двух? И как это узнать без третьего взвешивания?

Ответ тупой.
Так я могу сказать, что привяжу 49 мотоциклов к своему и протащу их буксиром. Затем пересяду на 49-й и протащу 48 мотоциклов. Таким образом я смогу проехать - 5000 км.

Нихера не понял ответа. Где в задаче сказано, что шляп по 5 штук каждого цвета?

ну дык и это будет второе взвешивание :)

в гуглу вас не возьмут

Это сообщение отредактировал nipioleg - 26.02.2015 - 09:57

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

По "правильному" ответу на первую задачу.
Рассуждаем логически.
Допустим:
1-я дверь - сокровище, 2-я - смерть.
1-й охранник врёт, 2-й - правдив.
По условию задачи этого всего мы НЕ знаем.
Теперь возможные варианты:

I-й.
Спрашиваем у 1-го охранника мол "спроси у второго, за какой дверью сокровище?"
Тот спрашивает, 2-й(правдивый) ему отвечает "за первой".
Охранник(врущий) нам отвечает "за второй"
Слыша диалог между охранниками, мы решаем, что первый охранник нам врёт, входим в первую дверь и получаем сокровище.

II-й.
Спрашиваем у 2-го охранника мол "спроси у первого, за какой дверью сокровище?"
Тот спрашивает, 1-й(врущий) ему отвечает "за второй".
Охранник(правдивый) нам отвечает "за первой" (напомню: оба охранника знают правильную дверь, а правдивый не может солгать и указать на неправильную)
Слыша диалог между охранниками, мы решаем, что теперь уже ВТОРОЙ охранник нам врёт, входим во вторую дверь и получаем топором по башке.

Чёт несостыковочка выходит...

Это сообщение отредактировал idubasov - 26.02.2015 - 11:01

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

Короче лоханулся

Это сообщение отредактировал Мормышник - 26.02.2015 - 10:20