Алгоритмы и структуры данных: шпаргалка перед собеседованием
Собеседования по алгоритмам проверяют не память, а узнавание паттерна: увидеть в условии задачи «это два указателя» или «это скользящее окно» и применить готовую конструкцию, а не изобретать решение с нуля. Эта шпаргалка — то, что стоит пробежать глазами за час до звонка: таблица сложности операций и код на четыре паттерна, которые вместе покрывают большинство задач уровня easy/medium на live coding.
Таблица сложности: Big-O по структурам данных
Знать эту таблицу наизусть — не блажь, а минимум, с которым можно начинать разговор про эффективность решения:
| Структура | Доступ | Поиск | Вставка | Удаление |
|---|---|---|---|---|
| Массив | 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) | O(log n) |
| Куча (heap) | — | O(n) | O(log n) | O(log n)** |
* В среднем случае; в худшем — O(n) при массовых коллизиях. ** Удаление минимума/максимума.
Полная версия с сортировками и худшими случаями — на bigocheatsheet.com, удобно держать открытой вкладкой во время подготовки.
Два указателя (two pointers)
Паттерн для задач на отсортированном массиве или строке: два индекса двигаются навстречу друг другу или в одном направлении, вместо вложенного цикла за O(n²) получаем O(n).
def has_pair_with_sum(numbers, target):
left, right = 0, len(numbers) - 1
while left < right:
current = numbers[left] + numbers[right]
if current == target:
return True
if current < target:
left += 1
else:
right -= 1
return False
has_pair_with_sum([1, 3, 4, 7, 9], 11) # True — 4 + 7
Узнать задачу на два указателя просто: «отсортированный массив» + «пара/тройка элементов с условием» почти всегда сигнализирует именно этот паттерн, а не перебор.
Скользящее окно (sliding window)
Когда нужно найти подмассив или подстроку фиксированного или переменного размера с каким-то свойством (максимальная сумма, все уникальные символы), пересчитывать сумму окна целиком на каждом шаге — расточительно. Скользящее окно пересчитывает только разницу:
def max_sum_subarray(numbers, k):
window_sum = sum(numbers[:k])
best = window_sum
for i in range(k, len(numbers)):
window_sum += numbers[i] - numbers[i - k]
best = max(best, window_sum)
return best
max_sum_subarray([2, 1, 5, 1, 3, 2], 3) # 9 — окно [5, 1, 3]
Наивное решение здесь — O(n·k), скользящее окно — O(n): каждый элемент заходит в сумму и выходит из неё ровно один раз.
BFS и DFS
Обход графа или дерева — база для задач на связность, кратчайший путь без весов и обход уровнями:
from collections import deque
def bfs(graph, start):
visited = {start}
queue = deque([start])
order = []
while queue:
node = queue.popleft()
order.append(node)
for neighbor in graph[node]:
if neighbor not in visited:
visited.add(neighbor)
queue.append(neighbor)
return order
BFS идёт «вширь» через очередь и находит кратчайший путь в невзвешенном графе. DFS — та же обвязка, но со стеком (или рекурсией) вместо очереди, и обычно проще в реализации для задач «есть ли путь» или «сколько компонент связности». Разница на собеседовании звучит так: если важна кратчайшая длина пути — BFS; если важен сам факт достижимости или полный обход — подойдёт и DFS, и он короче кода.
Рекурсия и динамическое программирование
Первый сигнал задачи на DP — рекурсивное решение, которое пересчитывает одни и те же подзадачи много раз:
def climb_stairs_naive(n):
if n <= 2:
return n
return climb_stairs_naive(n - 1) + climb_stairs_naive(n - 2) # O(2^n)
def climb_stairs_memo(n, cache={}):
if n <= 2:
return n
if n not in cache:
cache[n] = climb_stairs_memo(n - 1, cache) + climb_stairs_memo(n - 2, cache)
return cache[n] # O(n)
Наивная версия пересчитывает climb_stairs_naive(3) заново на каждом уровне рекурсии — отсюда экспонента. Мемоизация (кеш уже посчитанных подзадач) превращает её в линейную. На собеседовании достаточно сказать вслух: «здесь есть перекрывающиеся подзадачи — добавлю кеш» — это и есть суть DP, дальше просто техника.
Сортировки: что действительно нужно знать
Реализовывать сортировку с нуля почти никогда не просят — но объяснить их поведение просят часто. Быстрая сортировка (quicksort) в среднем O(n log n), но деградирует до O(n²) на уже отсортированном массиве при неудачном выборе опорного элемента — поэтому стандартные библиотеки языков (Python, Java, V8) используют гибридные алгоритмы вроде Timsort, которые подстраиваются под частично отсортированные данные и не имеют этой слабости.
Как использовать эту шпаргалку
- Прогоните все пять примеров кода выше руками — перепишите без подсматривания, сверьтесь.
- Полный план подготовки к live coding на 4 недели, с типами задач по темам и чеклистом — в статье как проходит live coding собеседование.
- Общую структуру технического интервью — язык, базы данных, системный дизайн — смотрите в статье вопросы на техническом собеседовании.
- На реальном интервью, если задачу дают со скриншота или голосом, Interview Assistant распознаёт условие и подсказывает подход — полезно свериться, тот ли паттерн вы узнали, пока не начали писать код. Первые 20 минут бесплатны.
Частые вопросы
Нужно ли помнить Big-O наизусть или можно вывести на месте?
Таблицу для базовых структур (массив, список, хеш-таблица, дерево) лучше знать наизусть — выводить её на месте под таймером рискованно. А вот сложность конкретного вашего решения интервьюер как раз просит вывести на месте: это и есть часть оценки.
Какой паттерн встречается на собеседованиях чаще всего?
Два указателя и скользящее окно вместе — это 50–60% задач уровня easy/medium: они возникают в любой задаче про подмассивы, подстроки или пары элементов. BFS/DFS — следующий по частоте, особенно в задачах на графы и деревья.
Обязательно ли решать на Python, как в примерах?
Нет, примеры — только для демонстрации паттерна. Пишите на языке, на котором работаете каждый день: интервьюер оценивает подход и рассуждение, а не синтаксис конкретного языка.
С чего начать, если совсем не готов к алгоритмам?
С таблицы Big-O и одного паттерна — двух указателей: это самый частый и самый простой для входа паттерн. Решите 5–7 задач именно на него, затем переходите к скользящему окну. Хаотичное решение случайных задач без разбора по паттернам — куда менее эффективно.
Что если на собеседовании задача не подходит ни под один паттерн?
Такое бывает на medium/hard уровне и в бигтехе. В этом случае ценнее не угадать паттерн с первой попытки, а рассуждать вслух: начать с грубого решения (перебор), назвать его сложность, и затем искать, что можно ускорить — часто по ходу рассуждения нужный паттерн проявляется сам.