Логічні задачки, які задають на співбесідах в IT-компаних (фото + текст)

113

Багато великі IT-компанії під час співбесід з потенційними працівниками люблять задавати їм задачки на логіку. Для того щоб впоратися з більшістю завдань знадобляться знання з шкільного курсу математики або гарна кмітливість. Так перевіряють можливих працівників Intel, Apple, Google, Microsoft та інші. Приклади подібних завдань чекають вас нижче.

Щоб побачити правильну відповідь (відповіді), виділіть рядок мишкою.

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

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

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

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