прислать материал
AIN.UA » Техно10 математических и логических задач из собеседований в Apple, Google, Adobe и Microsoft

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

280527 137

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

  1. На улице стоят пять домов.
  2. Англичанин живет в красном доме.
  3. У испанца есть собака.
  4. В зеленом доме пьют кофе.
  5. Украинец пьет чай.
  6. Зеленый дом стоит сразу справа от белого дома.
  7. Тот, кто курит Old Gold, разводит улиток.
  8. В желтом доме курят Kool.
  9. В центральном доме пьют молоко.
  10. Норвежец живет в первом доме.
  11. Сосед того, кто курит Chesterfield, держит лису.
  12. В доме по соседству с тем, в котором держат лошадь, курят Kool.
  13. Тот, кто курит Lucky Strike, пьет апельсиновый сок.
  14. Японец курит Parliament.
  15. Норвежец живет рядом с синим домом.
  16. Каждый из домов покрашен в отдельный цвет, в каждом доме живет представитель отдельной национальности, у каждого — свой питомец, своя любимая марка сигарет и напиток.

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

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

Заметили ошибку? Выделите ее и нажмите Ctrl+Enter, чтобы сообщить нам.

Также подобрали для вас

загрузить еще

Добавить комментарий

Такой e-mail уже зарегистрирован. Воспользуйтесь формой входа или введите другой.

Вы ввели некорректные логин или пароль

144 комментария

по хронологии
по рейтингу сначала новые по хронологии

Потери пакетов будут 0.1(1) в среднем, ведь вероятность фэйла ретрансляции также 1/10. Таким образом, потери = 0.1 + 0.1 * 0.1 + (0.1)^3 + (0.1)^4 + ... (0.1)^(inf) = 0.1(1)
Поправьте, если не так. Интересно.
http://www.wolframalpha.com/input/?i=sum+0.1%5Ex+where+x%3D1+to+infinity

Southern Oracle

Тільки таби побило. Вставити за сенсом. 🙂

Southern Oracle

Можемо провести обчислювальний експеримент.

Хоч потоком з мільйона пакетних передач.

from random import randint

s = 0
for i in range(1000000):
if randint(0, 9) == 0: continue
s += 1

print(s/1000000)

Хоч 100000 експериментів групами по 10 пакетних передач, точно як в умові.

from random import randint

ts = 0
for t in range(100000):

s = 0
for i in range(10):
if randint(0, 9) == 0: continue
s += 1

ts += s/10

ts = ts / 100000

print(ts)

Відповід весь час одна, в середньому рівно 0.9

...только вот вероятность неудачной ретрансляции вы упустили 😉

Southern Oracle

Зовсім ні. Код можна розуміти так.
Робляться спроби передачі пакета доти, доки він не буде успішно переданий. Тільки потім він зараховується (s+=1). Кожна спроба є неуспішною з ймовірністю 1/10 (if randint(0, 9) == 0: continue). Кожна спроба. Ніякої помилки.

Александр Колесник

Задачка с двойным дном))
По сути, если принять сферического коня в вакууме и считать что отправка неудачного пакета происходит мгновенно, тогда да, надо считать по формуле прогрессивной вероятности sum 0.1^x where x=1 to infinity но фишка в том, что системе пофиг на "неудавшийся пакет" для нее передача неудавшегося = передаче обычного следующего пакета)) все с той же вероятностью 0,9
т.е. 0,9 - правильный ответ

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

Southern Oracle

Наочно демонструє, що пропускна здатність каналу таки рівно одиниця мінус ймовірність неуспішної передачі. Незалежно від того, передаємо ми пакети повторно чи ні (за цієї рафінованої умови задачі звичайно).

Southern Oracle

Так і є. Але одночасно він є точною моделлю задачі.

Вы заблуждаетесь. Сейчас вы проверяете сколько пакетов долетает. Очевидно, ровно столько, сколько вы пропускаете. Ваша же задача - понять сколько нужно в среднем отправить пакетов, чтобы на том конце получили N. Другими словами, сейчас вы почему-то считаете кол-во отправленных пакетов константой и считаете, сколько долетело. А должно быть - полученных константа и посмотреть, сколько надо выстрелить, чтобы долетело.

Вот мой код, ответ совпадает с моим расчетом. http://ideone.com/TLQbMW

Southern Oracle

Ваша модель нічим принципово не відрізняється, окрім того, що ви інакше інтерпретуєте поняття пропускної здатності. Ви обчислюєте якусь дивну величину, (total_transmited - 100000) / 100000, тобто відношення кількості побитих пакетів (total_transmitted - 100000) до успішно переданих. Ще й віднімаєте її від одиниці, в той час, коли ця величина сама може перевищувати одиницю. Спробуйте ймовірність псування пакету підняти до 9/10 і ви отримаєте пропускну здатність -8.0, що очевидно неможливо.
Замініть вираз на 1.0 - (total_transmited - 100000) / total_transmited і ви отримаєте точно таке значення, як і в мене. Цей вираз еквівалентний просто 100000/total_transmited, що і є пропускною здатністю каналу, відношенню кількості успішно переданих пакетів до часу передачі (в пакетах).

Да, перемудрил что-то (
На то он и был спор с интервьювером 🙂

Southern Oracle

Пропускна здатність каналу буде рівнесенько 90%. Інтерв’ювер не правий.
Поглянемо на задачу за такої сторони. В кожних 10 таймслотах цілі досягають в середньому 9 пакетів, і всі ці 9 пакетів є різними, бо ж ми не передаємо повторно пакет, який досяг цілі. Відповідно пропусна здатність каналу буде рівно 9/10.

Max Tatevskyi

припустімо, маємо 10 пакетів для передачі, з вірогідністю 10% ми втрачаємо пакет.
припустімо перший же пакет б'ється, тоді ми його передамо з вірогідністю 100% за наступні 9 ре-трансміссій. так як перший же пакет побився то всі наступні 9 пакетів повинні дійти до цілі неушкодженими.
отже маємо к-ть трансмісій з ретрансмісіями: 1(битий пакет)+9(ретрансміссій)+9(цілих пакетів) = 19 передач з яких тільки 10 з корисною інформацією, а 9 ре-трансмісії.
пропускна здатність буде 10/19 => близько 0,53 тобто 53% ніяк, не 90% - повірте.

Max Tatevskyi

nevermind щось посередночі сам себе заплутав...

Serg Khalif

При передаче первых 10 пакетов 9 будет передано. При следующей передаче будет передаваться 1 пакет из предыдущей передачи и 9 новых. 9 будет передано и так до конца полной передачи. Погрешность даст последняя группа.

Почитайте оригинал задания. Имеется ввиду "передача десяти пакетов". Передача каждого пакета осуществляется до тех пор, пока он успешно не будет передан (в оригинале - When it fails, the transmitter retransmit the packet, until it finally succeeds). В задаче. очевидно, идет речь о сетевом пакете - 802.11 packet

Serg Khalif

Я внимательно прочитал задание. Я расписал алгоритм по которому получивший задание утверждал, что пропускная способность 9 пакетов в секунду. Формулу Бернулли следует применять для расчета времени, необходимого на полную передачу, а для пропускной способности нужно 10 разделить на 1.111111111(1)

Да, да, схема Бернулли

Olha Karpenko

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

Денис Дидковский

все именно так 😉

victor gavrin

Простите, возможно я не очень дружу с железом. Но меня напрягает вот эта часть условия: "Когда передача неудачная, трансмиттер будет передавать пакет до тех пор, пока не преуспеет." Разве это не означает априори, что пропускная способность всегда 100%? Разве подвох не в самой постановке?

Anna Rakityanskaya

Про мотоциклы херня, можно использовать все топливо и заехать на 390км.

Olga Karpenko

А почему во втором вопросе в условии нет информации о том, что именно половина шляп одного цвета? Почему не 1:9 или 2:8?

+1. И еще вопрос по этой задаче. Почему в конце сказано "Таким образом гарантированно выживают 9 из 10, а у первого отвечавшего шанс 1 к 1.", ведь выживают все

id135074967

8 Задача весьма любопытна. Для начала мы предполагаем, что N больше K. Если смотреть на задачу по-простому, то понятно, что может быть несколько случаев (т.е. получаем сумму вероятностей несвязанных событий):
1) проигрыши идут подряд, тут все просто (1-p)^K
2) проигрыши чередуются с выигрышами. Тут, чтобы все проиграть, число проигрышей должно превышать число выигрышей на К. Получаем формулу (1-p)^(K плюс M)*p^M, где М - целое количество дополнительных конов, от 1 до бесконечности.
И тут всплывает последнее, самое интересное условие, о выигрыше. Ведь нужно учесть, что в чередовании выигрышей и проигрышей наш персонаж не наберет заветную сумму N, а это возможно, если разница между количеством выигрышей и проигрышей в любой из моментов достигнет разницы между N и K. Итак, имеем количество выигрышей М и число проигрышей, которое допускает набор суммы N, если его разместить в начале выборки вместе с выигрышами, равное M-(N-K). Теперь нужно определить, сколько существует запрещенных вариантов расположения выигрышей и проигрышей, чтобы знать, сколько вычитать. Воспользуемся формулой числа сочетаний из M плюс (M-(N-K)) по M-(N-K) и получаем (M плюс M-(N-K))!/(M!*(M-(N-K))!) Осталось исключить случаи, когда общее число вариантов для данного М меньше числа запрещенных вариантов, т.е. (K плюс M)!/(К!*М!) должно быть больше, чем (M плюс M-(N-K))!/(M!*(M-(N-K))!)

Таким образом, получаем формулу (1-p)^K плюс [если (K плюс M)!/(К!*М!) больше (M плюс M-(N-K))!/(M!*(M-(N-K))!)] (1-p)^(K плюс M)*p^M*((K плюс M)!/(К!*М!)-(M плюс M-(N-K))!/(M!*(M-(N-K))!)) плюс ...

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

Эту задачу мне предлагали на собеседовании (Junior QA), настаивая на поиске нескольких вариантов решения. Решила тремя вариантами.

И как результат собеседования?

Anna Slavutskaya

Отрицательный. Так и тружусь техническим писателем...

Вот и решай им потом задачки...

Tonichka Katochimotokitoka

це все круто, але де ж відповіді?

Загрузить еще

Поиск

Сообщить об опечатке

Текст, который будет отправлен нашим редакторам: