10 завдань з співбесід у великі компанії

Відомі корпорації Google, Intel або Apple — славляться тим, що на співбесіді задають претендентам каверзні задачки. Сайт AIN.UA зібрав 10 цікавих прикладів таких завдань. Деякі з них запропонували самі компанії, а деякі виклали користувачі, вже проходили співбесіди. Для їх вирішення потрібні знання математики на шкільному рівні або просто кмітливість.

Social.org.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.

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

Є морфологічний словник об'ємом приблизно 100000 входів, у якому дієслова доконаного і недоконаного виду поміщені в окремі статті (тобто «робити» і «зробити» вважаються різними словниковими входами). Вам потрібно знайти в словнику такі видові пари і «склеїти» статті в одну.

Питання: Опишіть загальний сценарій розв'язання такої задачі і приблизний алгоритм пошуку видових пар.

Відповідей на завдання «Яндекса» у нас, на жаль, немає.

І бонус

Завдання 10.

Цю задачу приписують Альберту Ейнштейну — нібито з її допомогою він підбирав собі помічників. Інша майже легендарна історія приписує авторство Льюїсу Керроллу. Відзначимо, що вона дуже просто вирішується на папері, але, якщо хочете хардкору — спробуйте вирішити в розумі.

На вулиці стоять п'ять будинків.
Англієць живе в червоному будинку.
У іспанця є собака.
В зеленому будинку п'ють каву.
Українець п'є чай.
Зелений будинок стоїть одразу праворуч від білого дому.
Той, хто курить Old Gold, розводить равликів.
У жовтому будинку курять Kool.
У центральному будинку п'ють молоко.
Норвежець живе в першому будинку.
Сусід того, хто курить Chesterfield, тримає лисицю.
В будинку по сусідству з тим, в якому тримають коня, курять Kool.
Той, хто курить Lucky Strike, п'є апельсиновий сік.
Японець курить Parliament.
Норвежець живе поруч з синім будинком.
Кожен з будинків пофарбований в окремий колір, в кожному будинку живе представник окремої національності, у кожного — свій вихованець, своя улюблена марка сигарет і напій.

Питання: Хто п'є воду? Хто тримає зебру?

Японець тримає зебру, норвежець п'є воду.