Шпаргалка по алгоритмам перед собесом
↑ 8.3 Алгоритмы и структуры данных · ← Предыдущая
Зачем это на собесе
Быстрое повторение перед интервью: признаки задач и подходящие приёмы.
Узнать тип задачи
| Формулировка | Первая идея |
|---|---|
| Найти пару, тройку, сумму | хэш-таблица, два указателя |
| Подмассив/подстрока, непрерывная | скользящее окно, префиксные суммы |
| Отсортированный ввод | бинарный поиск, два указателя |
| Скобки, вложенность, «отмена» | стек |
| Порядок, уровни, кратчайший путь | BFS (очередь) |
| Все комбинации, перестановки | backtracking |
| Количество способов, минимум/максимум | ДП |
| Сетка, острова, компоненты | DFS/BFS, union-find |
| Зависимости, порядок сборки | топологическая сортировка |
| Топ-K, слияние потоков | heap |
| Префиксы, автодополнение | trie |
| Кэш | Map, LRU |
Сложности
| Структура | Доступ | Поиск | Вставка | Удаление |
|---|---|---|---|---|
| Массив | O(1) | O(n) | O(n) | O(n) |
| Связный список | O(n) | O(n) | O(1)* | O(1)* |
| Хэш-таблица | — | O(1) | O(1) | O(1) |
| BST сбалансированный | — | O(log n) | O(log n) | O(log n) |
| Heap | — | O(n) | O(log n) | O(log n) |
| Стек, очередь | — | — | O(1) | O(1) |
* при известном узле.
Шаблоны кода
// два указателя
let l = 0, r = a.length - 1
while (l < r) { /* ... */ }
// скользящее окно
for (let r = 0, l = 0; r < n; r++) { /* добавить a[r] */ while (invalid()) { /* убрать a[l++] */ } }
// BFS
const q = [start], seen = new Set([start])
while (q.length) { const v = q.shift()!; for (const n of adj(v)) if (!seen.has(n)) { seen.add(n); q.push(n) } }
// backtracking
const go = (i: number) => { if (done) return save(); for (const c of choices) { choose(c); go(i + 1); undo(c) } }
// бинарный поиск по ответу
let lo = min, hi = max
while (lo < hi) { const m = (lo + hi) >> 1; ok(m) ? (hi = m) : (lo = m + 1) }Чек-лист на интервью
- граничные случаи: пустой ввод, один элемент, дубликаты, отрицательные числа, очень большие n;
- изменение входных данных: разрешено ли мутировать;
Number.MAX_SAFE_INTEGER,NaN,-0;- итог: время, память, возможные улучшения;
- тесты: 2–3 примера и крайний случай.
Приёмы JS
Math.max(...a) // осторожно с большими массивами
[...new Set(a)] // уникальные
Object.groupBy(items, i => i.type) // группировка (ES2024)
a.at(-1) // последний элемент
structuredClone(x) // глубокая копияВопросы с ответами
Что сделать первым, когда не видно решения?
Уточнить условия, решить вручную на примере, предложить наивный перебор, затем искать узкое место и приём для его устранения.