Питання співбесіди DSA

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

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

Крок розпізнавання — причина, чому практика патернів перевершує обсяг. Задачі рідко бувають справді новими; це рекомбінації. Щойно ви можете сказати в першу хвилину це sliding window над картою частот, решта — це виконання. Пов'язані банки питань за мовою та роллю є в центрі питань для співбесід.

Ці патерни охоплюють більшість того, що запитують. Навчіться розпізнавати сигнал, який вказує на кожен з них.

• Two pointers. Відсортований вхід, суми пар, розбиття на місці (in-place), перевірка паліндромів.
• Sliding window. Найдовший або найкоротший суцільний підмасив за певного обмеження.
• Підрахунок через hash map. Анаграми, дублікати, порівняння частот, перший унікальний елемент.
• Бінарний пошук. Відсортовані масиви, а також пошук у просторі відповідей, коли масив не відсортовано.
• Пошук у ширину та в глибину. Дерева, сітки, зв'язні компоненти, найкоротший шлях без ваг.
• Купа та черга з пріоритетом. Задачі top-k, злиття відсортованих потоків, поточні медіани.
• Інтервали. Злиття, вставка та виявлення накладання після сортування за початком.
• Динамічне програмування. Задачі з накладеними підзадачами: підйом по сходах, розмін монет, відстань редагування, підпослідовності.
• Backtracking. Перестановки, комбінації, підмножини, задачі з обмеженнями.
• Графові алгоритми. Топологічне сортування, union find, найкоротший шлях із вагами.

Типові формулювання, як їх ставлять інтерв'юери:

• Знайдіть два числа в масиві, сума яких дорівнює цілі, а потім зробіть це без додаткової пам'яті.
• Поверніть довжину найдовшого підрядка без повторюваних символів.
• Маючи повернутий відсортований масив, знайдіть ціль за логарифмічний час.
• Об'єднайте перетинні інтервали й поясніть, чому сортування виправдовує свою вартість.
• Переверніть бінарне дерево, а потім знайдіть його максимальну глибину.
• Перевірте бінарне дерево пошуку і скажіть, що пропускає наївна перевірка.
• Порахуйте острови на сітці, а потім скажіть, як би ви обробили сітку, надто велику для пам'яті.
• Знайдіть k найчастіших елементів і обґрунтуйте вибір структури даних.
• Обчисліть мінімальну кількість монет для суми і сформулюйте рекурентне співвідношення.
• Виявіть цикл у зв'язаному списку, а потім поверніть вузол, де він починається.
• Серіалізуйте і десеріалізуйте бінарне дерево.
• Маючи передумови курсів, визначте, чи можливий розклад.

Нещодавній випускник на співбесіді на бекенд-позицію отримує задачу з підрядком і одразу починає друкувати. Код майже правильний, але інтерв'юер витрачає весь раунд, запитуючи, що він робить, і оцінка відображає тишу, а не баг. Кандидат, який витрачає сорок секунд, щоб сказати вікно над картою символів, розширюю праворуч, звужую ліворуч при дублікаті, відстежую максимум, уже пройшов найважчу для відновлення частину.

Мовчазне розв'язування формує неправильний рефлекс. Жива співбесіда вимагає одночасно розповіді та коду, і це окрема навичка порівняно з кожною з них окремо.

Змініть вправу, а не набір задач. Перш ніж щось писати, промовте вголос патерн, підхід і очікувану складність. Пишіть код, продовжуючи розповідати. Коли закінчите, назвіть складність знову і назвіть один межовий випадок, який ви обробили, і один, про який запитали б. Робота над десятьма задачами так формує більше навичок для співбесіди, ніж мовчазне розв'язання п'ятдесяти.

Сесія пробної співбесіди надає додаткові запитання — частину, яку неможливо відпрацювати самостійно, — і дає запис вашої власної розповіді для перегляду. Одне чесне обмеження діє завжди: письмове кодування в браузері під наглядом — це не розмова, і жоден живий асистент не має в ній місця. Центр типів співбесід пояснює, які формати кодування є живими, а які автоматизованими.