Алгоритмы

Алгоритмическую секцию на Python-собеседовании проходят не пересказом учебника, а двумя числами — временем и памятью того, что вы только что написали. Формулировка «работает за O(n)» без второго числа считается половиной ответа, а «работает быстро» не считается вовсе. При этом Python добавляет к классической теории собственный слой: у каждой операции стандартной библиотеки есть своя цена, и она часто противоречит внешнему виду кода. x in some_list выглядит так же, как x in some_set, но стоит O(n) против O(1); list.pop(0) выглядит как извлечение из очереди, но сдвигает весь хвост.

Второй слой — что в Python уже реализовано, и переписывать это руками не надо. list.sort() и sorted() — это Timsort — устойчивая гибридная сортировка со строгой гарантией O(n log n) в худшем случае и линейным поведением на частично упорядоченных данных. Двоичный поиск лежит в модуле bisect. Куча — в heapq, очередь — в collections.deque. Собственный quicksort пишут ровно для одной цели — показать на собеседовании, что вы понимаете разбиение, выбор опорного элемента и худший случай; в продакшен-коде он проигрывает sorted() по всем параметрам сразу. Разберите каждый механизм в слоях ниже — и обязательно вслух проговаривайте обе оценки, временную и по памяти.

Карта темы

• Big-O и асимптотика — верхняя оценка роста времени и памяти, отбрасывание констант и почему меньшая асимптотика проигрывает на малых входах.
• Настоящая цена операций Python — сложность операций list, dict, set в CPython, амортизация и превращение O(n·m) в O(n) одним set.
• Линейный поиск — O(n) без требований к порядку, когда он честно выигрывает у двоичного и как хеш-таблица заменяет вложенный перебор.
• Двоичный поиск и bisect — половинное деление по отсортированным данным за O(log n), инвариант границ и готовые bisect_left / bisect_right.
• Сдвинутый отсортированный массив — вариация двоичного поиска, где на каждом шаге определяют, какая половина осталась отсортированной.
• Quicksort и Timsort — разбиение вокруг опорного, O(n log n) в среднем против O(n²) на крайнем опорном, отсутствие устойчивости и почему в проде берут sorted().
• Сортировка подсчётом — O(n + k) без единого сравнения, когда диапазон значений ограничен, и при каком k она проигрывает.
• Внешняя сортировка — данные не помещаются в RAM — нарезка на отсортированные серии и k-путевое слияние через heapq.merge.
• Два указателя — встречные и однонаправленные указатели, дающие O(n) времени при O(1) дополнительной памяти.
• Дедупликация — dict.fromkeys сохраняет порядок первого появления, set — нет, а нехешируемые элементы требуют ключа.
• Обход матрицы — индексы главной и побочной диагоналей, ловушка [[0]*n]*n и транспонирование через zip(*m).
• Поиск в ширину — обход по уровням на collections.deque за O(V + E) и кратчайший путь только в невзвешенном графе.
• Алгоритм Дейкстры — кратчайшие пути по весам через heapq, ленивое удаление вместо decrease-key и запрет отрицательных рёбер.
• Динамическое программирование — оптимальная подструктура и перекрывающиеся подзадачи, мемоизация сверху вниз против табуляции снизу вверх.
• Жадные алгоритмы — локально оптимальный выбор, условия его доказуемой оптимальности и роль приближения для NP-полных задач.
• k ближайших соседей — ленивый классификатор без обучения, обязательное шкалирование признаков и проклятие размерности.

Частые ошибки и ловушки

Значение для собеседований

Алгоритмическая секция устроена как воронка. Сначала спрашивают определения — что такое O(n), чем линейный поиск отличается от двоичного, как работает quicksort. Здесь достаточно точности формулировок, но ровно одна деталь отделяет джуна от мидла — названы ли обе оценки. «Двоичный поиск за O(log n)» — половина; «O(log n) по времени, O(1) по памяти в итеративном варианте и O(log n) в рекурсивном, и вход обязан быть отсортирован» — полный ответ, после которого половина уточняющих вопросов отпадает.

Дальше идут вопросы на худший случай и на Python-специфику, и именно на них сыплются. «Когда quicksort становится O(n²)?» — ждут связку «крайний опорный элемент плюс уже отсортированный вход», а не общее «при плохих данных». «Почему BFS не находит кратчайший путь во взвешенном графе?» — ждут, что вы назовёте Дейкстру и объясните, что очередь считает рёбра, а не веса. «Как убрать дубликаты с сохранением порядка?» — ждут dict.fromkeys, а не set. В практической части почти всегда просят обогнать перебор — свести O(n²) к O(n) через dict в задаче о двух слагаемых, O(n·m) к O(n) через set, O(n·m) к O((n + m) log n) через bisect. Типичная ошибка одна и та же — решение работает и выдаёт правильный ответ, но кандидат ни разу не произносит его сложность, а интервьюер оценивает именно её.