9 математичних та логічних завдань зі співбесід в Apple, Google і Microsoft

Хто б не хотів влаштуватися на роботу в 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 кульки, вона – одна з тих двох, які залишилися.

7. За версією користувача, відповідь повинна була бути 9 пакетів в секунду. Але людина, яка проводила інтерв’ю, з ним не погодилася, правда, відповіді не сказала, але наполягала, що «через ретрансмісію пропускна здатність повинна бути зменшена більше, ніж на 1/10»