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

Задачі в 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.
• Норвежець живе поряд із синім будинком.

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

Запитання: хто п’є воду? Хто тримає зебру?
Відповідь: Японець тримає зебру, норвежець п’є воду.