Технічні співбесіди в ІТ часто сприймаються як нескінченний марафон задач з LeetCode. Втім, значна частина типових завдань зводиться до невеликого набору базових патернів. Канал Tech With Tim у стислій добірці виділяє саме ті підходи, які найчастіше зустрічаються на співбесідах і покривають більшість стандартних задач.
1. Два вказівники: від пар до циклів у списках
Патерн «two pointers» — один із найпрактичніших для масивів і зв’язаних списків.
Класичний варіант: два індекси
Суть у тому, що замість одного індексу використовуються два — зазвичай:
- з протилежних кінців масиву, або
- з різною швидкістю руху по структурі даних.
Такий підхід особливо корисний для:
- пошуку пар елементів (наприклад, сума двох чисел у відсортованому масиві);
- роботи з відсортованими масивами (злиття, видалення дублікатів тощо);
- задач, де важливо одночасно контролювати «лівий» і «правий» контекст.
Fast & slow pointers: виявлення циклів
Окремий різновид — «fast and slow pointers», коли:
- один вказівник рухається на один крок,
- інший — на два кроки.
Це стандартний інструмент для:
- виявлення циклів у зв’язаних списках;
- пошуку середнього елемента списку.
Якщо швидкий вказівник «наздожене» повільний — у структурі є цикл. Якщо ж цикл не виявлено, повільний вказівник часто вказує на середину.
2. Слайдінг-вікно: робота з підпослідовностями
Патерн «sliding window» застосовується до послідовностей (масивів, рядків), де потрібно аналізувати піддіапазони — підмасиви або підрядки.
Основна ідея:
- формується «вікно» — діапазон елементів;
- межі вікна динамічно розширюються або звужуються залежно від умови;
- замість повного перерахунку на кожному кроці оновлюється лише те, що змінилося при зсуві.
Це дає змогу ефективно розв’язувати задачі на кшталт:
- пошук підрядка з певними властивостями;
- максимальна/мінімальна сума підмасиву фіксованої або змінної довжини;
- підрахунок унікальних елементів у поточному вікні.
3. Пошук і обходи структур: від бінарного пошуку до DFS/BFS
Варіації бінарного пошуку
Бінарний пошук — не лише про «знайти елемент у відсортованому масиві». На співбесідах часто з’являються модифіковані версії:
- пошук у повернутому (rotated) відсортованому масиві;
- пошук лівого або правого кордону (перша/остання поява елемента);
- пошук у «нескінченній» послідовності, де межі наперед невідомі.
У всіх випадках ключова ідея та сама: звужувати діапазон пошуку, використовуючи властивості впорядкованості або структури даних.
DFS і BFS: дерева та графи
Для задач на дерева й графи базовими залишаються два підходи:
- DFS (Depth-First Search) — заглиблюється в одну гілку до кінця, а потім повертається й переходить до наступної;
- BFS (Breadth-First Search) — обходить структуру рівень за рівнем.
Ці патерни лежать в основі:
- пошуку шляхів у графах;
- перевірки зв’язності;
- задач на рівні дерева (наприклад, вивід по рівнях, пошук найкоротшого шляху в неваговому графі).
4. Побудова рішень: динамічне програмування та бектрекінг
Динамічне програмування: розбиття на підзадачі
Dynamic Programming (DP) застосовується, коли:
- задачу можна розбити на перекривні підзадачі;
- результати цих підзадач доцільно зберігати, щоб не обчислювати повторно.
Типовий підхід:
- Формалізувати стан (що саме зберігається).
- Визначити перехід між станами (рекурентну формулу).
- Зберігати проміжні результати (таблиця або мемоізація).
Це дозволяє значно зменшити складність у задачах на:
- підрахунок кількості способів (шляхи, розбиття, комбінації);
- оптимізацію (мінімум/максимум вартості, часу, шляху тощо).
Бектрекінг: повний перебір із «розумним» відсіканням
Backtracking — це систематичне дослідження всіх можливих рішень шляхом:
- поступового побудування кандидата;
- відмови від гілок, які явно не ведуть до коректного результату.
Алгоритм:
- Додаємо наступний елемент до поточного рішення.
- Перевіряємо, чи ще можливо отримати валідне рішення.
- Якщо ні — «відкочуємося» (backtrack) і пробуємо інший варіант.
Цей патерн використовується в задачах на:
- генерацію всіх комбінацій, перестановок, підмножин;
- розв’язання головоломок і задач із жорсткими обмеженнями.
Висновок: менше хаосу, більше патернів
Замість хаотичного розв’язання сотень випадкових задач, фокус на кількох ключових патернах — два вказівники, слайдінг-вікно, варіації бінарного пошуку, DFS/BFS, динамічне програмування та бектрекінг — дає структурований підхід до підготовки. Більшість класичних інтерв’ю-завдань так чи інакше вкладаються в ці рамки, тож глибоке розуміння саме цих технік суттєво підвищує шанси успішно пройти технічну співбесіду без «нескінченного грінду».