10 логических задач с собеседований, которые заставят задуматься

Аватарка пользователя Рафаил Агазода

Составили подборку из 10 логико-математических задач, которые загадывают на рабочих интервью в Microsoft, Google, Amazon, Yahoo и Infosys.

Составили подборку из 10 логико-математических задач, которые загадывают соискателям во время рабочих интервью в Microsoft, Google, Amazon, Yahoo и Infosys. Мы нашли их на сайте Crazy for Code и адаптировали для вас.

Попробуйте решить их самостоятельно, не подглядывая под спойлеры.

Отмеряем нужное количество воды

Эту задачу могут дать на собеседовании в Amazon. Представьте, что у вас есть две пустых бутыли для воды объемом в 3 и 5 галлонов. Как отмерить ровно 4 галлона воды? Запас воды для решения не ограничен.

Решение

Шаг 1. Наполните 3-галлоновую бутыль водой.

Шаг 2. Перелейте всю воду в 5-галлоновую бутыль.

Шаг 3. Снова наполните 3-галлоновую бутыль.

Шаг 4. Перелейте воду в 5-галлоновую бутыль, пока она не заполнится полностью. В 3-галлонной банке останется ровно 1 галлон воды.

Шаг 5. Опустошите 5-галловую бутыль, перелейте в нее 1 галлон воды из 3-галловой бутылки. Теперь у вас есть 1 галлон воды.

Шаг 6. Снова наполните 3-галлонную бутыль и перелейте всю воду в 5-галлонную бутылку. Вы получите ровно 4 галлона воды.

Самая быстрая лошадь на скачках

Задачку дают на собеседованиях Microsoft. У вас есть 25 лошадей и 5 беговых дорожек. Вы не знаете, какая лошадь быстрее другой.

Найдите за минимально возможное количество забегов тройку самых быстрых лошадей.

Решение

Проведем 5 заездов с участием всех 25 лошадей. На каждой дорожке мы получим рейтинг самых быстрых лошадей.

			u1,u2,u3,u4,u5
v1,v2,v3,v4,v5
x1,x2,x3,x4,x5
y1,y2,y3,y4,y5
z1,z2,z3,z4,z5
		

Выходит, что u1 быстрее всех на своей дорожке, как и v1, x1, y1, и так далее.

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

			u1,u2,u3
v1,v2,v3
x1,x2,x3
y1,y2,y3
z1,z2,z3
		

Проведём шестую гонку с участием первых лошадей из каждого заезда: u1, v1, x1, y1, z1.

Получаем условный результат, где скорость(u1) > скорость(v1) > скорость(x1) > скорость(y1) > скорость(z1).

Выходит, что u1 ­— самая быстрая лошадь в шестом заезде.

Теперь исключим y1, y2, y3, z1, z2 и z3, так как y1 и z1 оказались самыми слабыми в шестом заезде, а остальные лошадки выбыли ранее.

Осталось рассмотреть этих лошадей:

			u2,u3,
v1,v2,v3,
x1,x2,x3,
		

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

Таким образом, для определения трех самых быстрых лошадей нам нужно провести как минимум 7 заездов.

Делим золотой слиток

Это задача с собеседований Amazon. Представьте, что у вас есть сотрудник, который работает на вас в течение семи дней. За всю работу вы должны заплатить ему одним золотым слитком.

В конце каждого дня вы должны отдавать ему по кусочку золота, то есть 1/7 слитка.

Как поделить золотой слиток минимальным количеством отрезов, чтобы платить сотруднику по 1/7 части каждый день?

Решение

Разметим на слитке 7 равных между собой отрезков. После этого разделим слиток на три части А, В и С, где А равен одному отрезку, В — двум отрезкам, С — четырём отрезкам.

День 1: Отдаём A. Сотрудник получает +1 золотой отрезок.

День 2: Сотрудник возвращает A, мы отдаём B. Сотрудник лишается одного отрезка и получает два взамен.

День 3: Отдаём отрезок А. Теперь у сотрудника три золотых отрезка.

День 4: Сотрудник возвращает A и B, мы отдаём ему C. Так сотрудник лишается трёх золотых отрезков, но получает четыре взамен.

День 5: Отдаём А. У сотрудника пять золотых отрезков.

День 6: Сотрудник возвращает отрезок A, мы отдаём ему B. То есть сотрудник лишается одного отрезка из пяти, но получает два взамен. Итого у него шесть отрезков.

День 7: Отдаём отрезок А. У сотрудника семь отрезков, то есть весь слиток.

Охота лисы за уткой

Ещё одна задачка с собеседований Microsoft.

Лиса охотится за уткой, и последняя приземляется в центр идеально круглого пруда.

Лиса не может плавать, а утка не может взлететь с воды. Чтобы утка могла сбежать, ей нужно добраться до берега и взлететь. Однако лиса в четыре раза быстрее утки.

Может ли утка добраться до края пруда и улететь, не будучи съеденной? Если да, то каким образом?

Решение

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

За время, которое утка преодолеет радиус пруда r, лиса может пробежать 4r. При этом для того, чтобы оказаться на противоположном берегу, лисе нужно пройти всего половину окружности Pi*r, что меньше 4r, ведь Pi = 3.14…

Как же утка может максимально усложнить жизнь лисе? Если она начнёт просто плавать вдоль берега, лиса просто будет бегать за уткой по окружности пруда, и утка останется в ловушке.

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

Когда утка обгонит лису на 180 градусов, ей придется преодолеть расстояние 3r/(4 + дельта), чтобы достичь края пруда. За это время лиса должна пройти половину окружности пруда.

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

Шапки заключённых

Задача от Google. Четверо заключенных были арестованы, но тюрьма переполнена, и тюремщику некуда их посадить. Он решает дать им головоломку. Если они справятся, то выйдут на свободу, а если не справятся, то будут казнены.

Тюремщик выстроил трех человек в линию. Четвертого он посадил за ширму. Каждому заключённому он дал по одной шапке.

Тюремщик объяснил, что есть две черные и две белые шапочки, и каждый заключенный носит одну из них. При этом каждый из заключенных должен видеть только шапки тех, кто находится перед ним, но не собственные шапки или не шапки тех, кто находится позади. Четвертый человек за ширмой не может видеть шапки других заключённых, а они не видят, какая шапка на его голове. Общаться заключённым тоже нельзя.

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

Как заключённым избежать казни?

10 логических задач с собеседований, которые заставят задуматься 1
Решение

Заключенные A и B по сути изолированы. У них нет информации, которая помогла бы им дать ответ. Заключенные C и D понимают это, поэтому решение задачи лежит на них.

Заключенный D видит шляпы заключенных B и C. Если бы у B и C были шляпы одного цвета (например, чёрного), то D догадался бы, что на его голове точно должна быть шляпа другого цвета, то есть белого.

Когда время почти истекло, С понимает, что D не может дать ответ. Это значит, что цвет его шляпы отличается от цвета шляпы B, иначе D сразу ответил бы. Поэтому С делает вывод, что на нём черная шляпа, так как он видит белую шляпу В.

Отравленное вино короля

Задача с собеседований Amazon. У короля есть погреб с 1000 бутылок восхитительного вина. Королева по соседству решила убить короля и послала слугу отравить вино. Стражники короля поймали слугу после того, как он отравил только одну бутылку.

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

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

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

Как королю выявить отравленную бутылку при помощи 10 заключённых?

Решение

Пронумеруйте каждую бутылку вина в двоичном коде. Тогда первая бутылка будет пронумерована как 0000000001, вторая — 0000000010, бутылка №500 — 0111110100, а последняя бутылка №1000 — 1111101000.

Возьмите 10 заключенных и пронумеруйте их от 1 до 10. Пусть заключенный №1 пьёт вино только из тех бутылок, у которых в младшем разряде стоит 1. Заключенный №10 будет пить вино из бутылок, у которых в старшем бите стоит 1. Если в присвоенном им бите находится 0, они не пьют вино из бутылки.

Иными словами, мы используем номера заключённых, чтобы соотнести их с битами в двоичном коде.

Например, бутылку №924 с кодом 1110011100 будут пить заключённые 10, 9, 8, 5, 4 и 3. Если бутылка №924 была отравлена, умрут только эти заключенные.

Через четыре недели нужно выстроить заключенных в порядке следования битов. Каждый живой будет битом 0, а каждый мертвый — битом 1. Полученный код поможет найти бутылку вина, которая была отравлена.

Как найти вора

Ещё одна задача от Google. Вор пытался скрыться от полиции и забежал в пещеру. Когда полиция зашла в неё, то обнаружила, что внутри по кругу расположены 13 ходов. В одном из них находится вор, который надеется улизнуть.

Каждый день вор может перемещаться в любой из соседних ходов или остаться на месте и никуда не бежать. При этом каждый день полиции разрешается заходить только в две пещеры по своему выбору.

Как полиции быстрее всего отыскать вора?

Решение

Предположим, что вор находится в ходе C1 и перемещается по часовой стрелке, а полицейские начинают поиск с C13 и C12 в первый день. Во второй день они проверяют С13 и С11, в третий — С13 и С10, и так далее.

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

Ответ: 12 дней.

Задача о десяти монетах

Эту головоломку задают в Yahoo. Вас ослепили и положили перед вами 10 монет. Вам можно трогать монеты, но вы не можете определить на ощупь, какая сторона монеты смотрит вверх.

Вам сказали, что на столе лежат 5 монет с орлом сверху и 5 монет решкой вверх, но вы не знаете, какие из них именно.

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

Решение

Сделайте две кучки по пять монет. Теперь переверните все монеты в одной из кучек. Вот и всё!

Например, вы разделили монеты так, что в первой куче лежат две монеты орлом (О) вверх и три монеты решкой (Р) вверх:

			К1 : О О Р Р Р
К2 : О О О Р Р
		

Если перевернуть первую кучку (К1), получится:

			К1 : Р Р О О О
		

Тогда количество монет с орлом в обеих кучках будет равно трём.

Другой случай:

			К1 : О Р Р Р Р
К2 : Р О О О О
		

Переверните все монеты в первой кучке (К1) и получите четыре монеты с орлом кверху, как и во втором множестве.

Рай или ад

Вы умерли и стоите перед двумя вратами. Одна из них ведет в рай, а другая — в ад.

У каждой двери стоит по одному стражу. Один из них всегда говорит правду, а другой всегда лжет, но вы не знаете, кто из них честен, а кто — лжец.

Вам нужно найти дорогу в рай, задав одному из стражей только один вопрос. Что это за вопрос?

Это одна из классических головоломок, задаваемых на собеседовании в Infosys.

Решение

Стоит задать вопрос: “Если я спрошу другого охранника о том, какие врата ведут в рай, что он ответит?”.

Независимо от того, какому из стражей вы зададите этот вопрос, вы всегда получите ответ, который приведёт вас в ад. Поэтому вам стоит выбрать другие врата, чтобы отправиться в рай.

Предположим, что левая дверь ведет в рай. Если спросить охранника, который всегда говорит правду, то он скажет: “Правые врата”. Если спросить лжеца, что ответит честный привратник, то лжец ответит, что честный отправит вас в правую дверь.

Мы используем лживость адского привратника против него. Поэтому, если на этот вопрос вам указывают на правую дверь, вам стоит выбрать левые врата.

Тигры и принцессы

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

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

Если преступник откроет дверь, за которой окажется принцесса, то он женится на ней. Если он откроет дверь, за которой окажется тигр, то будет съеден заживо.

На каждой из дверей висит табличка. На первой двери написано: “В этой комнате находится принцесса, а в другой — тигр”.

На второй двери написано: “В одной из этих комнат находится принцесса, а в одной из этих комнат — тигр”.

Преступнику сказали, что одно из утверждений истинно, а другое — ложно. Какую дверь должен открыть преступник?

Это — задача с собеседований в Yahoo.

Решение

Преступник должен открыть вторую дверь.

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

Значит, если первое утверждение ложно, за дверьми могут быть Тигр и Тигр, Принцесса и Принцесса, Тигр и Принцесса.

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

Получается, остается только третий вариант, поэтому преступник должен открыть вторую дверь.

Заключение

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

Какие из них показались вам простыми, а какие — сложными? Может быть, у вас есть более “тонкие” способы решить их?

Задачи умеренной сложности
Работа
Собеседование
16039