Распознавание паттернов и выбор алгоритма (CEASE-фреймворк)

Самый частый промах на алгоритмическом собесе — потратить 15 минут на «вглядывание» в задачу и не увидеть паттерн. Опытный инженер за 2–3 минуты определяет «семейство» задачи (сортировка, граф, DP, two pointers) и сразу выбирает подходящую технику. Эта страница — система того, как это делать осознанно.

Фреймворк CEASE

Используй пять шагов перед написанием кода:

1. Clarify — уточни вход/выход, ограничения, edge cases (пустой ввод, дубликаты, отрицательные числа).
2. Examples — построй 2–3 примера: маленький, граничный, нетривиальный. Прогон вручную часто подсказывает алгоритм.
3. Approach — обозначь подход: brute force → improvement. Назови сложность каждого варианта.
4. Solve — пиши код, проговаривай инварианты вслух.
5. Evaluate — прогон на примерах + тесты на edge cases + сложность по времени/памяти.

Пример: K Closest Points to Origin

Условие: дан массив точек, верни k ближайших к (0,0).

Распознавание: «top-k» → подсказывает heap. Размер k маленький → max-heap размера k. Сложность O(n log k) предпочтительнее, чем сортировка O(n log n).

function kClosest(points: number[][], k: number): number[][] {
  // max-heap по квадрату расстояния (избегаем sqrt — мы только сравниваем)
  const heap = new MaxHeap<[number, number[]]>((a, b) => a[0] - b[0]);

  for (const p of points) {
    const dist = p[0] * p[0] + p[1] * p[1];
    if (heap.size() < k) heap.push([dist, p]);
    else if (dist < heap.top()![0]) {
      heap.pop();
      heap.push([dist, p]);
    }
  }

  return heap.toArray().map(([, p]) => p);
}

Альтернативы:

• Sort O(n log n) — простой, но избыточный для маленького k.
• Quickselect O(n) average — лучший по сложности, но сложнее в реализации и нестабильный.
• Heap O(n log k) — баланс между простотой и эффективностью.

Таблица: сигнал → паттерн

Сигнал в условии	Паттерн / алгоритм
«отсортированный массив», «найти X»	Binary Search
«отсортированный массив», «пара / тройка»	Two Pointers
«подмассив с суммой», «непрерывный»	Prefix Sum / Sliding Window
«k ближайших», «top-k», «k-й элемент»	Heap (size k) или Quickselect
«все перестановки / комбинации / подмножества»	Backtracking
«найти подстроку», «pattern matching»	KMP / Rabin-Karp / Z-function
«кратчайший путь, веса ≥ 0»	Dijkstra
«кратчайший путь, есть отрицательные»	Bellman-Ford / SPFA
«связные компоненты», «MST»	Union-Find / Kruskal / Prim
«уровни / BFS»	Queue + visited
«возможность достичь», «есть путь»	DFS / BFS
«топологический порядок», «зависимости»	Topological Sort (Kahn / DFS)
«количество способов», «оптимальный выбор»	DP
«непересекающиеся интервалы», «сортируй и иди»	Greedy + sort
«скользящее окно фиксированной длины»	Sliding Window
«LRU / cache»	HashMap + LinkedList
«range queries / updates»	Segment Tree / BIT (Fenwick)
«пересечение / объединение интервалов»	Sort by start + sweep
«balanced parens / nested»	Stack
«next greater element»	Monotonic Stack
«найти цикл в массиве/связном списке»	Floyd’s tortoise & hare
«n-я цифра / разряд»	Math + цифровая декомпозиция
«битовая операция / уникальный элемент»	XOR / bit manipulation
«многоисточниковый BFS»	BFS из всех источников одновременно

Сложность как навигация

Часто ограничения в условии напрямую подсказывают сложность:

n (размер входа)	Допустимая сложность
n ≤ 10	O(n!) — backtracking, brute force
n ≤ 20	O(2ⁿ) — bitmask DP
n ≤ 500	O(n³) — Floyd-Warshall, 3-вложенный DP
n ≤ 5 000	O(n²) — DP с двумя индексами
n ≤ 10⁶	O(n log n) — sort, heap, Dijkstra
n ≤ 10⁸	O(n) — линейный проход, hashmap, two pointers
n ≤ 10¹⁸	O(log n) — binary search, math, fast exponentiation

Если задача даёт n = 10⁵, а твой алгоритм O(n²) — он не пройдёт по времени, ищи O(n log n) или O(n).

Типичные ловушки

:::caution Ловушки распознавания

• «Найти максимум» ≠ всегда heap. Если массив уже линейный — простой проход O(n). Heap нужен только для top-k или динамического стрима.
• «Подстрока» ≠ всегда KMP. Для one-shot strstr длинного текста — да; для коротких строк brute-force O(nm) проще и читаемее.
• «Граф» в условии может быть имплицитным. Word ladder, открытые комнаты, состояния игры — это графы, даже если слово «граф» не звучит.
• «Минимум / максимум» ≠ всегда DP. Иногда хватает greedy. Проверяй: можно ли локально принять решение без знания будущего?
• DP vs Greedy: если жадный выбор в одном случае ухудшает будущее (нет матроидной структуры) — нужно DP. :::

Follow-up вопросы

• Как понять, нужна ли DP или хватит greedy? Попробуй сделать обратный пример к жадному. Если есть случай, когда локально оптимальный выбор приводит к глобально худшему — нужно DP. Activity selection — greedy работает; 0/1 knapsack — нет, нужно DP.

• Когда использовать Dijkstra vs BFS? BFS — невзвешенный граф (или все веса = 1). Dijkstra — веса ≥ 0. Для отрицательных — Bellman-Ford. Для unweighted DAG критического пути — топологическая сортировка + DP по слоям.

• Что выбрать: Segment Tree или Fenwick (BIT)? Fenwick проще и быстрее для point update + range sum. Segment Tree — гибче (max/min/gcd/range update with lazy propagation), но в 2× больше кода.

• Когда хеш-таблица плоха? Worst-case O(n) при коллизиях (или adversarial input в C++); строгие требования к latency (real-time); упорядоченные операции (нужен tree map).

Чеклист распознавания на собесе

• Прочитал условие 2 раза, выписал input/output на бумаге.
• Назвал brute force и его сложность ДО оптимизации.
• Заметил ключевые слова из таблицы сигналов выше.
• Сравнил n из ограничений с допустимой сложностью.
• Прокатал руками минимум 2 примера.
• Озвучил инварианты алгоритма перед кодом.
• После решения — назвал альтернативы и trade-off.