Курси / Як проходити співбесіди із задачами
У вас дві мотузки й запальничка. Кожна мотузка горить рівно годину, але нерівномірно: половина мотузки не обов'язково згорає за пів години. Як відміряти 45 хвилин?
«Не поспішайте. Думайте вголос, мені цікаво, як ви міркуєте».
Таку задачу можна отримати на співбесіді в квант-фонд, консалтинг, аналітику чи розробку. Курс про те, що робити в ці десять хвилин. Спершу вчимося міркувати вголос: читати умову, пробувати малі випадки, іти від кінця, оцінювати на пальцях і будувати відповідь. Потім збираємо інструменти: скільки дає одна перевірка, найгірший випадок, інваріанти, розумний розклад. Третя частина про ймовірності і про те, що робити, коли застрягли. Наприкінці пробна співбесіда з таймером і підказками, і розбір задачі про мотузки.
≈ 1,5–2 години, можна частинами по 10–15 хвилин; прогрес зберігається.
Шість звичок, які видно інтерв'юеру з перших хвилин. Кожен розділ починається з маленької задачі: спершу вгадайте, потім перевірте на живій картинці. Тут досить арифметики.
«Мені дадуть задачу. А якщо я не знатиму відповіді?»
Задача на співбесіді — це не іспит із відповіддю в кінці підручника. Інтерв'юер має десять хвилин, щоб побачити, як ви думаєте, і записати це. Відповідь важлива, але це лише один рядок у його нотатках.
Двом кандидатам дали ту саму задачу. А мовчки думає хвилину й називає правильне число, а на «як ви це отримали?» каже, що знав задачу. Б думає вголос, помиляється, сам помічає помилку, виправляє і перевіряє відповідь на маленькому прикладі. Хто, найімовірніше, отримає вищу оцінку?
Задача: «Скільки всього квадратів можна побачити на шахівниці 8×8?»
(хвилина тиші)
— 204.
— Як ви це отримали?
— Я знав цю задачу.
уточнення— Рахуємо квадрати будь-якого розміру, складені з кліток? Тобто і всю дошку теж?
простий випадок— Квадратів 1×1 — 64. Квадрат 2×2 можна поставити у 8 позицій уздовж ряду... ні, у 7, бо він займає дві клітки. Тож 7×7 = 49.
закономірність— Схоже, квадратів k×k буде (9 − k)². Тоді всього 64 + 49 + … + 1, сума квадратів від 1 до 8, це 204.
перевірка— Перевірю на дошці 2×2: за формулою 4 + 1 = 5. Рахую руками: чотири маленькі й один великий. Сходиться.
Обидва дійшли до 204. Але про А в нотатках буде одне слово «знав», а про Б — чотири сигнали, за якими його й оцінюватимуть.
Чи питають задачі взагалі? Залежить від того, куди ви йдете. Великі технологічні компанії від головоломок здебільшого відмовилися: у 2013 році Ласло Бок, тоді віцепрезидент Google з персоналу, сказав New York Times, що їхні власні дані не показали від головоломок жодної користі для найму. Зате в квант-фондах і трейдингу задачі на ймовірність і логіку досі звичайна частина співбесіди, у консалтингу дають оцінки «на пальцях», а в розробці й аналітиці — алгоритмічні й ймовірнісні задачі, які легко прийняти за головоломку.
«Відповідь очевидна. Чому інтерв'юер усміхається?»
Найчастіша помилка на співбесіді — не складна математика, а швидка відповідь на іншу задачу, ніж та, яку поставили. Мозок підставляє знайомий шаблон, і виходить упевнене, але хибне число.
Блокнот і ручка разом коштують 130 грн. Блокнот на 100 грн дорожчий за ручку. Скільки коштує ручка?
Десять секунд на таку перевірку рятують від найприкрішої помилки: впевнено сказати число, яке не задовольняє умову.
Друга половина читання умови — питання до інтерв'юера. Багато класичних задач змінюють відповідь від однієї деталі, яку легко пропустити. Ось умова задачі Монті Голла. Натисніть на підкреслені слова: кожне з них — припущення, яке варто проговорити вголос.
Ви на телешоу й обираєте одні з трьох дверей. За одними авто, за двома кози. Ведучий, , і . Чи варто змінювати?
Глибше: класична версія задачі з блокнотом і задача Монті Голла, з грою і симуляцією.
Бита й м'яч разом коштують 1,10 $. Бита на 1 долар дорожча за м'яч. Скільки коштує м'яч?
Ви на телешоу й обрали одні з трьох дверей. Ведучий, який знає, де авто, відчиняє інші двері з козою й пропонує змінити вибір. Змінювати?
«Сто учасників, сто кроків. Як це взагалі тримати в голові?»
Великі числа в умові часто лише лякають. Якщо задачу не видно одразу, розв'яжіть її для 1, 2, 3, 4 і подивіться на відповіді. Закономірність зазвичай проступає вже на п'ятому кроці, а пояснити її легше, ніж вгадати.
У коридорі 100 зачинених шафок. Перший учень відчиняє всі. Другий змінює стан кожної другої (2, 4, 6, …): відчинену зачиняє, зачинену відчиняє. Третій — кожної третьої, і так до сотого, який змінює лише сотую. Скільки шафок відчинено в кінці?
Чому квадрати? Шафку 12 чіпають учні 1, 2, 3, 4, 6 і 12, її дільники. Дільники ходять парами: 1 і 12, 2 і 6, 3 і 4, тож шафка змінює стан парну кількість разів і лишається зачиненою. Пари немає лише в квадрата: у 16 дільник 4 стоїть сам із собою. Малі випадки дали закономірність, а пояснення перетворило її на доказ.
Глибше: дві задачі, де малі випадки — єдиний шлях до розв'язку.
Гість каже острів'янам те, що вони й так знали: «Я бачу когось із блакитними очима». Чи може це щось змінити?
Кожен із 100 в'язнів може відкрити 50 коробок зі 100, щоб знайти свій номер. Усіх звільнять, лише якщо свій номер знайде кожен. Який шанс у найкращої стратегії?
Тут знадобиться те, що ви ще не пройшли: розділ 3 «Малі випадки»
«Тут гра на багато ходів. З чого почати?»
Коли задача — це послідовність кроків, починати з першого часто безнадійно: варіантів забагато. Зате останній крок зазвичай простий. Розв'яжіть його, потім передостанній, і так назад до початку. Це те саме «малі випадки», тільки малим тут є кінець гри.
На столі 21 сірник. Двоє по черзі беруть 1, 2 або 3 сірники. Хто взяв останній, той виграв. Вам дають вибір. Що робити?
А тепер від кінця. Позиція з 0 сірників програшна для того, хто ходить: він уже програв. З 1, 2, 3 можна забрати все й виграти. З 4 будь-який хід лишає суперникові 1, 2 або 3, тож 4 знову програшна. Натискайте, щоб розфарбувати решту.
Чорні клітинки — програшні позиції для того, хто ходить.
Глибше: пірати, які ділять золото від кінця, і озеро, яке зручно читати з останнього дня.
П'ятеро логічних піратів ділять 100 монет, а капітана, чий поділ не підтримала половина, викидають за борт. Скільки монет він залишить собі?
Ряска щодня подвоюється, і одна рослина вкриває озеро за 30 днів. За скільки днів упораються дві рослини?
«Звідки мені знати, скільки їх? Я не пам'ятаю таких чисел».
Питання на оцінку, їх ще називають питаннями Фермі, не перевіряють пам'ять. Їх дають, щоб побачити, як ви розкладаєте невідоме число на кілька відомих, називаєте припущення і перевіряєте, чи результат правдоподібний. Точність «у межах разу-двох» зазвичай більш ніж достатня.
Скільки дітей народжується у світі за одну добу?
Ідея: кожна людина колись народилася. Якщо населення приблизно стале, то щороку народжується стільки, скільки людей «змінюється» за рік: населення, поділене на тривалість життя.
Дані: Our World in Data за World Population Prospects 2024 (ООН): 132,1 млн народжень у 2023 році, населення 8,09 млрд, очікувана тривалість життя 73,2 року.
З реальними числами оцінка дає близько 300 тисяч на добу, приблизно на шосту частину менше за правду. Ця різниця теж цікава, і її варто проговорити: населення не стале, а росте, тож молодих людей більше, ніж у сталому світі, і дітей вони народжують більше. Сказати, в який бік і чому ваша оцінка може помилятися, — найкращий спосіб закінчити відповідь.
Глибше: задача, де відчуття масштабу підводить майже всіх.
Мотузку навколо екватора подовжили на 1 метр і рівномірно підняли. Яка щілина між нею і землею?
Тут знадобиться те, що ви ще не пройшли: розділ 1 «Що насправді оцінюють»
«П'ята хвилина, а я досі не бачу розв'язку. Що казати?»
Глухий кут на співбесіді — нормальна частина задачі, а не провал. Інтерв'юер часто навмисно дає задачу, яку за десять хвилин мало хто розв'яже до кінця, щоб побачити, що ви робите, коли не знаєте.
Ви застрягли на п'ятій хвилині й уже хвилину мовчите. Що найкраще зробити?
Якщо застрягли — поверніться на крок 4 і скажіть це вголос: «Я застряг тут, спробую для двох».
Чотири ідеї, на яких тримається більшість логічних задач зі співбесід у розробку й квант: скільки інформації дає одна перевірка, найгірший випадок, інваріант і розумний розклад. Тут знадобляться степені двійки й трохи терпіння.
«Кандидатів сотні тисяч, а перевірок — лічені. Хіба так можна?»
Багато задач питають: скільки перевірок потрібно, щоб напевно знайти одне з багатьох? Замість перебирати стратегії, порахуйте, скільки різних відповідей можуть дати ваші перевірки разом. Якщо відповідей менше, ніж варіантів, жодна стратегія не допоможе. Якщо більше або стільки ж — зазвичай можна.
Ви загадали одне слово зі словника на 100 000 слів. Я ставлю питання, на які можна відповісти лише «так» або «ні». Скільки питань мені потрібно, щоб напевно вгадати слово?
Я вгадаю його не більше ніж за 10 питань, бо 210 = 1024. Відповідайте чесно.
–
А якщо перевірка має не два результати, а три? Шалькові терези показують «ліва важча», «права важча» або «рівно», тож n зважувань дають 3n різних результатів. Ще цікавіше, коли перевірок кілька одночасно: тоді рахувати треба не питання, а комбінації відповідей усіх перевірок разом. Обидві задачі нижче розв'язуються саме цим підрахунком.
Глибше: дві класичні задачі на підрахунок результатів.
З 1000 пляшок вина одна отруєна, а перевірити щурами можна лише за один раунд. Скільки щурів потрібно, щоб напевно знайти отруєну пляшку?
Серед 12 монет одна фальшива, легша чи важча, невідомо. Скільки зважувань на шалькових терезах потрібно, щоб напевно знайти її і сказати, легша вона чи важча?
Тут знадобиться те, що ви ще не пройшли: розділ 7 «Скільки дає одна перевірка»
«Двійковий пошук же найкращий. Чому він тут не працює?»
«Напевно» на співбесіді означає «в найгіршому випадку». Зручно уявити злого суперника, який знає вашу стратегію і щоразу відповідає так, щоб вам було найгірше. Стратегія хороша, якщо навіть він не змусить вас зробити більше кроків.
Будинок на 10 поверхів і два однакові яйця. З якогось поверху яйця починають битися, нижче — ні. Розбите яйце більше не кинеш, ціле можна кидати знову. Скільки кидків потрібно в найгіршому випадку, щоб напевно знайти найвищий безпечний поверх?
Будинок не вирішує наперед, з якого поверху яйця б'ються. Він відповідає так, щоб вам довелося кидати якомога довше, але ніколи собі не суперечить. Натискайте поверхи.
Глибше: та сама ідея на 100 поверхах і в турнірі коней без секундоміра.
Будинок на 100 поверхів і лише два яйця. Скільки кидків потрібно в найгіршому випадку, щоб напевно знайти найвищий поверх, з якого яйце не б'ється?
25 коней, доріжка лише на 5 і жодного секундоміра. Скільки забігів потрібно, щоб напевно знайти трьох найшвидших коней і їхній порядок?
«Я пробую й пробую, і завжди лишається дірка. Може, я щось не так роблю?»
Інваріант — це величина, яка не змінюється, хоч що ви робите. Якщо вона в кінці мала б бути іншою, ніж на початку, то мета недосяжна, і доводити це перебором не треба. На співбесіді це найкоротший шлях від «не виходить» до «неможливо, і ось чому».
З шахівниці 8×8 вирізали дві протилежні кутові клітинки. Лишилося 62 клітинки. Чи можна покрити їх 31 доміно, кожне з яких накриває рівно дві сусідні клітинки?
Покладіть доміно: натисніть дві сусідні клітинки. Натиск на покладене доміно прибирає його.
Глибше: сто людей, капелюхи й одна парність на всіх.
100 людей у ряд у чорних і білих капелюхах бачать лише тих, хто попереду. Скільки з них можуть напевно назвати колір свого капелюха?
Тут знадобиться те, що ви ще не пройшли: розділ 6 «Як будувати відповідь»
«Я просто робитиму найкраще на кожному кроці. Що може піти не так?»
Жадібна стратегія — щоразу робити те, що здається найкращим саме зараз, — природний перший крок і гарна «перша груба відповідь» з розділу 6. Але в задачах на розклад вона часто програє, а перевірити це допомагає нижня межа: скільки часу потрібно щонайменше, хоч як крути.
У тостер влазять дві скибки хліба, і він підсмажує лише один бік кожної за хвилину. Треба підсмажити з обох боків три скибки. Перевертати й міняти скибки можна миттєво. Який найменший час?
Оберіть до двох скибок і натисніть «Хвилина минула»: у кожної обраної підсмажиться ще один бік.
Глибше: нічний міст, ліхтарик і задача, де жадібність програє.
Четверо мають уночі перейти міст на двох з одним ліхтариком. Вони ходять за 1, 2, 5 і 10 хвилин. Який найменший час на переправу?
Три пастки інтуїції, які люблять на співбесідах у квант і аналітику: умовна ймовірність, середнє значення й момент зупинки. Тут знадобляться дроби й поняття середнього. Останній розділ частини про те, як брати підказку, коли жоден інструмент не спрацював.
Тут знадобиться те, що ви ще не пройшли: розділ 2 «Прочитайте умову ще раз»
«Лишилося два варіанти, значить, п'ятдесят на п'ятдесят?»
«Два варіанти — отже, половина на половину» — найчастіша помилка в задачах на ймовірність. Варіанти бувають нерівноцінні: важить не те, скільки їх лишилося, а якими шляхами ви могли прийти до того, що бачите.
У мішку три картки: одна червона з обох боків, одна біла з обох боків, одна з одного боку червона, з іншого біла. Ви навмання витягаєте картку й кладете на стіл. Верхній бік червоний. Який шанс, що нижній теж червоний?
Глибше: дві задачі, де «половина на половину» — пастка.
Ви на телешоу й обрали одні з трьох дверей. Ведучий, який знає, де авто, відчиняє інші двері з козою й пропонує змінити вибір. Змінювати?
У сім'ї двоє дітей, і хоча б один із них хлопчик. Який шанс, що обидва хлопчики? А якщо хоча б один із них хлопчик, народжений у вівторок?
«Тут же купа випадків. Невже все перебирати?»
У задачах на середнє часто не треба знати, як розподілені варіанти. Досить розкласти величину на суму простих частин: середнє суми дорівнює сумі середніх, навіть коли частини залежать одна від одної. А симетрія підказує середнє кожної частини без жодних обчислень.
Десятеро здали капелюхи в гардероб, а гардеробник повертає їх цілком навмання. Скільки людей у середньому отримають свій капелюх?
Стовпчики — у скількох вечорах рівно 0, 1, 2, … людей отримали свій капелюх.
Подивіться на останнє число: приблизно в 37% вечорів ніхто не отримує свій капелюх, а отже, хоч один отримує в 63%. Це другий прийом із цього розділу: коли питають «хоча б один», порахуйте протилежне, «жодного», і відніміть від одиниці. Так розв'язують і задачу про дні народження.
Глибше: альбом із наліпками, де середнє складається з простих частин, і кімната, де «хоча б одна пара» рахується через «жодної».
В альбомі 50 місць, а наліпки в пакетиках випадкові. Скільки наліпок у середньому треба купити, щоб заповнити весь альбом?
Скільки людей має зібратися в кімнаті, щоб двоє з них, імовірно, народилися в один день?
Тут знадобиться те, що ви ще не пройшли: розділ 3 «Малі випадки»
«Брати першу пропозицію чи чекати кращої?»
Задачі про зупинку схожі на життя: варіанти приходять по одному, відмову не повернеш, а про майбутні нічого не відомо. Великий випадок одразу не видно, тож починаємо з малого (розділ 3): з трьох кандидатів усіх порядків лише шість, їх можна перелічити руками.
Троє кандидатів приходять у випадковому порядку. Про кожного треба вирішити одразу: найняти чи відмовити назавжди. Ви бачите лише, чи кращий він за попередніх. Яка стратегія частіше наймає найкращого?
1 — найкращий кандидат, 3 — найслабший. Порядок читається зліва направо.
Глибше: те саме зі ста кандидатами.
100 кандидатів приходять по одному, і про кожного треба вирішити одразу. Який шанс найняти найкращого?
Тут знадобиться те, що ви ще не пройшли: розділ 2 «Прочитайте умову ще раз»розділ 3 «Малі випадки»розділ 9 «Інваріант і парність»
«Мені дали підказку. Це вже мінус?»
Підказка — звичайна частина розмови: інтерв'юер дає її, щоб задача рухалась і він встиг побачити більше. Оцінюють не те, що вона знадобилась, а що ви з нею зробили: чи зрозуміли, куди вона веде, і чи пов'язали її з тим, що вже спробували.
Ви вже кілька хвилин крутите задачу про сто предметів, і інтерв'юер питає: «А якби їх було лише двоє?» Що це, найімовірніше, означає?
На столі 100 монет, 10 із них гербом догори. У вас зав'язані очі: ви не бачите монет і не відчуваєте боку на дотик, але можете їх пересувати й перевертати. Розділіть монети на дві купки так, щоб гербів у них було порівну.
Підказка 1А якби монет було дві, і одна з них гербом догори?
Підказка 2Купки не мусять бути однакові за розміром. Скільки монет покласти в меншу?
Підказка 3Якщо в купці з 10 монет k гербів, то скільки гербів у ній стане, коли перевернути всі десять?
Зверніть увагу, що зробила кожна підказка: перша — малий випадок (розділ 3), друга зняла непомічене обмеження (розділ 2), третя — інваріант: різниця гербів між купками лишається керованою (розділ 9). Підказки на співбесідах майже завжди ведуть до одного з інструментів цього курсу. Тож почувши підказку, скажіть, до якого прийому вона веде, і поясніть, як вона змінює ваш план.
Чотири нові задачі, як на справжній співбесіді: з таймером, драбиною підказок і самооцінкою. Оцінюємо не лише відповідь, а й те, як ви до неї йшли.
Тут знадобиться те, що ви ще не пройшли: розділ 2 «Прочитайте умову ще раз»розділ 5 «Оцінка на пальцях»розділ 6 «Як будувати відповідь»розділ 7 «Скільки дає одна перевірка»розділ 12 «Симетрія і середнє»
«У вас п'ять хвилин на задачу. Думайте вголос».
Як тренуватися: запустіть таймер і розв'язуйте вголос, можна диктофону чи другові. Застрягли — візьміть наступну підказку, як узяли б її від інтерв'юера. Тоді оберіть відповідь і чесно відзначте, що ви зробили по дорозі. Кожна задача тренує свій розділ курсу.
Задача 1 · оцінка
Скільки разів б'ється серце людини за 80 років життя?
Розкладіть на два числа: удари за хвилину і хвилини за життя.
У спокої серце дорослого б'ється 60–100 разів на хвилину. Візьміть 70.
У році 60 × 24 × 365 ≈ 525 600 хвилин, тобто близько півмільйона.
Задача 2 · перевірки
Є 8 однакових на вигляд куль, одна з них трохи важча. Скільки зважувань на шалькових терезах без гир потрібно, щоб напевно знайти важку?
Скільки різних результатів може показати одне зважування?
Три: ліва важча, права важча, рівно. Два зважування дають 3 × 3 = 9 результатів, а куль 8.
Покладіть по 3 кулі на кожну шальку, а 2 відкладіть.
Задача 3 · простіший погляд
Два потяги за 100 км один від одного їдуть назустріч, кожен зі швидкістю 50 км/год. Муха летить від одного потяга до другого зі швидкістю 75 км/год, розвертається, летить назад і так далі, доки потяги не зустрінуться. Скільки кілометрів пролетить муха?
Не рахуйте відрізки польоту по одному: їх нескінченно багато.
Що простіше дізнатися: шлях мухи чи час її польоту?
Потяги зближуються зі швидкістю 100 км/год. Скільки часу до зустрічі?
Задача 4 · середнє
Ви підкидаєте чесну монету, доки не випадуть два герби поспіль. Скільки підкидань знадобиться в середньому?
Позначте стани: «з нуля» і «щойно випав герб».
Нехай E — середнє число підкидань із нуля, F — після одного герба. Що стається після наступного підкидання в кожному стані?
E = 1 + ½·F + ½·E, а F = 1 + ½·0 + ½·E.
Дві мотузки, кожна горить рівно годину, але нерівномірно. Як відміряти 45 хвилин?
Ось як могла б звучати сильна відповідь. Кожен рядок — звичка з курсу.
Тренуватися на задачах із каталогу зручно в «Тренажері співбесіди»: випадкова задача, таймер, три підказки й самооцінка міркувань.
Усі книжки з розділами, де трапляються задачі каталогу, — на полиці сайту.