Чеклист подготовки к алгоритмическому собесу

Эта страница — финальный чеклист перед интервью. Используй её как self-check за 1–2 недели до собеседования, чтобы убедиться, что ничего не упущено: алгоритмы, реализации без подсказок IDE, поведенческие истории и расписание занятий.

Кодинг без IDE

На собесах в крупные компании (Google, Meta, Amazon) часто просят писать код в шаринговом редакторе без автодополнения и подсветки ошибок. Натренируй мышечную память — попробуй на бумаге или в Notepad реализовать 10 ключевых алгоритмов:

1. Binary Search (рекурсивно и итеративно)
2. Quicksort с partition
3. Merge Sort
4. BFS / DFS на графе
5. Dijkstra с min-heap
6. Topological Sort
7. Union-Find с path compression и union by rank
8. KMP (с построением LPS)
9. Knapsack 0/1 (DP)
10. LRU Cache (HashMap + LinkedList или JS Map)

Если хотя бы один из этих алгоритмов ты не можешь написать без подглядывания — это пробел. Закрывай его.

Must-know для Middle

• Структуры данных: Array, LinkedList, Stack, Queue, Deque, HashMap, HashSet, Tree, BST, Heap.
• Сортировки: Quicksort, Mergesort, понимание stable vs unstable.
• Поиск: Binary Search и его варианты (lower_bound, upper_bound, на ответе).
• Графы: BFS, DFS, обнаружение цикла, connected components.
• DP: classic problems — Fibonacci, Climbing Stairs, House Robber, LCS, LIS, Coin Change, Knapsack 0/1.
• Two Pointers, Sliding Window, Prefix Sum.
• Big-O анализ для своего кода.

Senior+ (дополнительно)

• Графы: Dijkstra, Bellman-Ford, Floyd-Warshall, MST (Kruskal/Prim), Topological Sort, Tarjan/Kosaraju (SCC), Articulation Points & Bridges.
• Продвинутый DP: Bitmask DP, DP on trees, Digit DP, DP optimizations (Convex Hull Trick, Divide & Conquer).
• Строки: KMP, Rabin-Karp, Z-function, Suffix Array.
• Структуры: Segment Tree (с lazy propagation), Fenwick Tree, Union-Find, Trie.
• Алгоритмическая теория: P/NP, NP-hard, амортизация, randomized algorithms.

Tech Lead (дополнительно)

• System Design структуры: LRU/LFU, Bloom Filter, Consistent Hashing, LSM Tree, Skip List, B+ Tree, Merkle Tree.
• Distributed algorithms: Paxos, Raft, vector clocks, gossip protocols.
• Concurrency: locks, lock-free структуры, CAS, MVCC.
• Capacity planning: оценка QPS, throughput, latency budget.
• Архитектурные паттерны: CQRS, Event Sourcing, Saga, Circuit Breaker.

Поведенческая часть (Behavioral)

Готовь 5–7 STAR-историй (Situation, Task, Action, Result), покрывающих типичные темы:

• Конфликт с коллегой / руководителем — как разрешил.
• Ошибка в продакшене — что сломал, как починил, что выучил.
• Сложное технические решение — trade-off, аргументация.
• Лидерство без полномочий — как повёл за собой команду.
• Несогласие с решением старшего — как высказал и что вышло.
• Делегирование / mentoring — как обучил junior’а.
• Переоценка приоритетов / срыв дедлайна — как пришёл к решению.

Принцип: история должна быть специфичной (имена, проекты, метрики), а не «однажды я работал в команде, и мы всё сделали хорошо».

Программа подготовки на 1–2 недели

Неделя 1 (фундамент)

• День 1–2: Arrays, Strings, Two Pointers, Sliding Window. Решить 10 задач с LeetCode Easy/Medium.
• День 3: HashMap, HashSet. 5 задач (Two Sum, Group Anagrams, Subarray Sum Equals K).
• День 4: Stack, Queue, Monotonic Stack. 5 задач.
• День 5: LinkedList, Trees (DFS, BFS). 8 задач.
• День 6: BST, Heap. 5 задач (K Closest Points, Merge K Sorted Lists).
• День 7: mock-интервью (с другом или на pramp.com / interviewing.io).

Неделя 2 (продвинутые темы)

• День 8: Graphs (BFS, DFS, topo sort, Union-Find). 6 задач.
• День 9: Dijkstra, Bellman-Ford, MST. 4 задачи.
• День 10: DP (1D, 2D, knapsack). 8 задач.
• День 11: Backtracking, Bitmask DP. 5 задач.
• День 12: Strings (KMP, Rabin-Karp), Tries. 4 задачи.
• День 13: System Design (1–2 кейса: дизайн URL shortener, chat, news feed).
• День 14: mock-интервью + Behavioral подготовка.

Cheatsheet перед собесом

Тема	Ключевая формула / факт
Quicksort avg	O(n log n), worst O(n²), in-place
Mergesort	O(n log n), stable, O(n) extra
Heap insert/extract	O(log n)
BST balanced	O(log n) all ops
HashMap	O(1) avg, O(n) worst
BFS/DFS	O(V + E)
Dijkstra	O((V+E) log V)
Bellman-Ford	O(VE)
Floyd-Warshall	O(V³)
Kruskal	O(E log E)
KMP	O(n + m)
Knapsack 0/1	O(n·W)
LCS / Edit Distance	O(n·m)

Финальная мантра

:::tip Перед интервью

1. Уточни условие — никогда не пиши код после первого прочтения.
2. Brute force first — назови наивное решение, потом оптимизируй.
3. Сложность вслух — до и после.
4. Прокатай руками — на маленьком примере.
5. Edge cases — пустой вход, один элемент, дубликаты, переполнение.
6. Не молчи — интервьюер оценивает мышление, а не только финальный код.
7. Признай, если застрял — попроси подсказку лучше, чем 10 минут тишины. :::

Чеклист перед отправкой кода

• Назвал сложность по времени и памяти.
• Проверил edge cases: пустой вход, один элемент, переполнение.
• Использовал осмысленные имена переменных (не только i, j).
• Прокатил алгоритм на 1–2 примерах вслух.
• Объяснил trade-off с альтернативами.
• Готов к follow-up: «а как изменится при потоковых данных / распределённом сценарии / памяти O(1)?».

Удачи на интервью.