Алгоритми та структури даних
Big O — перше, що треба засвоїти
Перш ніж писати будь-який код на інтервʼю, потрібно вміти оцінювати його ефективність. Big O нотація описує, як зростає час виконання або споживання памʼяті залежно від розміру вхідних даних.
| Нотація | Назва | Приклад |
|---|---|---|
| O(1) | константна | звернення до масиву за індексом |
| O(log n) | логарифмічна | бінарний пошук |
| O(n) | лінійна | прохід по масиву |
| O(n log n) | лінійно-логарифмічна | злиттєве сортування |
| O(n²) | квадратична | вкладені цикли |
| O(2ⁿ) | експоненційна | рекурсія без мемоізації |
Структури даних — обовʼязковий мінімум
Лінійні структури
Array / Slice — основа всього. Потрібно знати: звернення за індексом O(1), вставка в кінець O(1) амортизовано, вставка на початок O(n).
Hash Map (словник) — найчастіше використовувана структура на інтервʼю. Середній час пошуку, вставки і видалення — O(1). Більшість задач на підрахунок, пошук дублікатів і групування вирішуються через хеш-таблицю.
Stack — структура LIFO (last in, first out). Використовується в задачах на дужки, монотонні стеки, DFS ітеративно.
Queue / Deque — структура FIFO. Основа для BFS і задач типу sliding window з видаленням з обох кінців.
Нелінійні структури
Linked List — рідше зустрічається на практиці, але популярна тема на інтервʼю. Важливо вміти: reverse list, знайти цикл (алгоритм Флойда), знайти середину.
Binary Tree / BST — обовʼязково. Обходи (inorder, preorder, postorder), пошук в BST за O(log n), перевірка збалансованості.
Heap (Min/Max Heap) — використовується в задачах типу “знайти K найбільших елементів”. Вставка і видалення — O(log n), отримання мін/макс — O(1).
Graph — орієнтовані та неорієнтовані, зважені та незважені. Представлення через список суміжності або матрицю. Основні алгоритми: BFS, DFS, Dijkstra, топологічне сортування.
Алгоритмічні патерни — важливіше за зубріння задач
Замість того щоб заучувати сотні задач, варто засвоїти 15 патернів. Тоді нові задачі починають впізнаватись за структурою, а не за умовою.
| Патерн | Де застосовується |
|---|---|
| Two Pointers | відсортовані масиви, паліндроми, пошук пар |
| Sliding Window | підрядки, підмасиви фіксованого або змінного розміру |
| Binary Search | відсортовані дані, задачі “мінімальний максимум” |
| BFS / DFS | дерева, графи, задачі на острови та компоненти |
| Dynamic Programming | “скільки способів”, задачі на оптимум |
| Backtracking | комбінації, перестановки, N-Queens |
| Greedy | інтервали, задачі з локальним оптимумом |
| Monotonic Stack | next greater element, задачі на гістограми |
| Union-Find | connected components, задачі на обʼєднання множин |
| Topological Sort | залежності між задачами, курси, build order |
Порядок вивчення
Не варто стрибати одразу на графи або динамічне програмування. Ось послідовність, яка дає найшвидший результат:
1. Big O нотація — 2-3 дні
2. Array + Hash Map — 1-2 тижні
3. Two Pointers + Sliding Window — 1 тиждень
4. Binary Search — 1 тиждень
5. Stack + Queue — 1 тиждень
6. Linked List — 1 тиждень
7. Trees + BFS/DFS — 2 тижні
8. Heap — 1 тиждень
9. Graphs — 2 тижні
10. Dynamic Programming — 3-4 тижні (найскладніший блок)
Фреймворк для розвʼязання задачі
На інтервʼю важливо не просто отримати правильну відповідь, а продемонструвати структурне мислення. Ось покроковий підхід:
- Прочитай умову двічі — не поспішай писати код
- Уточни edge cases — пустий масив? відʼємні числа? один елемент?
- Придумай brute force — проговори вголос, навіть якщо він повільний
- Оптимізуй — що тут надлишково? що можна кешувати або передобчислити?
- Напиши код — чистий, з говорячими іменами змінних
- Перевір вручну — пройдись по прикладу на папері або в голові
- Назви складність — час і памʼять
Навіть якщо не вдається дійти до оптимального рішення — правильний процес мислення важливий не менше, ніж відповідь.
Ресурси для підготовки
- NeetCode.io — найкращий структурований roadmap з відео поясненнями по кожному патерну
- LeetCode — основна платформа для практики (починай з Easy, потім Medium)