Литкод на русском: как готовиться к алгоритмам на собесе

«Прорешай литкод», советуют каждому, кто готовится к собесу в большую компанию. За этим обычно стоит картинка: пятьсот задач на LeetCode, полгода вечеров, и вот ты готов. Так не работает. Задач на платформе тысячи, а приёмов, которыми они решаются, всего десяток. Готовятся не к задачам, а к паттернам.

Ниже карта этих приёмов и того, что за ними на самом деле проверяют. Примеры на Python, но идеи не про язык.

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

LeetCode это площадка с задачами по алгоритмам и структурам данных. Название стало нарицательным: «литкод» давно не сайт, а жанр задач, которые дают на алгоритмической секции. В Яндексе, Т-Банке, Авито и почти любом биг-техе есть этап, где вам показывают задачу, а вы пишете код и вслух объясняете ход мысли.

Загвоздка в том, что сам LeetCode англоязычный, и разборы к нему в основном тоже. На русском системного мало: либо переводы условий, либо готовые решения без объяснения, почему оно такое. А понимать надо именно «почему», потому что на собесе дадут не ту задачу, что вы вызубрили, а соседнюю.

Что проверяют на алгосекции (не то, что кажется)

Кажется, что проверяют факт: решил или не решил. Это не так. Решение важно, но интервьюер смотрит на другое:

Сводите ли перебор к чему-то быстрому. Почти у каждой задачи есть наивное решение за O(n²) и красивое за O(n) или O(n log n). Увидеть второе и есть навык.
Проговариваете ли сложность. Написали решение, сразу скажите, за сколько оно работает по времени и по памяти. Молчание здесь читается как «не знаю».
Ловите ли крайние случаи. Пустой вход, один элемент, дубликаты, отрицательные числа, переполнение. Хороший кандидат проговаривает их сам, до того как его ткнут носом.
Думаете ли вслух. Молчаливое правильное решение хуже, чем рассуждение вслух с небольшой ошибкой. Интервьюер нанимает человека, с которым потом обсуждать задачи, а не телепата.

Держите это в голове, пока читаете паттерны ниже. Каждый из них про две вещи сразу: как решить и что при этом сказать.

Карта паттернов: 80% задач это десяток приёмов

Смысл подготовки в том, чтобы, услышав условие, узнать в нём знакомый каркас. Вот приёмы, которые закрывают большую часть алгосекций.

Хеш-таблица: O(n) вместо O(n²)

Самый частый способ ускорить перебор. Нужно проверить, есть ли в массиве из миллиона элементов дубликаты. Наивно: сравнить каждый с каждым, это O(n²), и на миллионе оно не досчитает никогда. С хеш-множеством хватает одного прохода:

def has_duplicates(nums):
    seen = set()
    for x in nums:
        if x in seen:      # проверка в среднем O(1)
            return True
        seen.add(x)
    return False

Поиск по ключу в set/dict в среднем O(1): хеш сразу указывает, где лежит элемент. В списке так нельзя, там идёшь подряд, O(n). За эту среднюю O(1) вы платите памятью под таблицу. И держите в уме худший случай: при массовых коллизиях хеш-таблица деградирует до O(n) на операцию. На собесе это хороший момент проговорить вслух, до того как спросят.

Два указателя

На отсортированном массиве вместо вложенного цикла часто хватает двух указателей, бегущих навстречу. Классика: найти пару с заданной суммой.

def two_sum_sorted(nums, target):
    lo, hi = 0, len(nums) - 1
    while lo < hi:
        s = nums[lo] + nums[hi]
        if s == target:
            return (lo, hi)
        if s < target:
            lo += 1        # нужна сумма побольше
        else:
            hi -= 1        # нужна поменьше
    return None

O(n) вместо O(n²), без лишней памяти. Приём просится, когда массив отсортирован (или его не жалко отсортировать) и ответ зависит от пары элементов с разных концов.

Скользящее окно

Родственник двух указателей для задач про непрерывный подотрезок: самая длинная подстрока без повторов, максимальная сумма подмассива длины k. Вместо того чтобы пересчитывать каждое окно заново, вы двигаете правую границу и подтягиваете левую, поддерживая ответ на лету. Снова O(n) там, где в лоб было бы O(n·k).

Префиксные суммы

Когда запросов «сумма на отрезке [l, r]» много, а массив не меняется, предподсчитайте массив префиксов P, где P[i] это сумма первых i элементов. Тогда сумма любого отрезка это P[r+1] - P[l], за O(1). Разовый препроцессинг за O(n) окупается, если запросов больше одного.

Бинарный поиск, и не только по массиву

O(log n), но с одним жёстким условием: данные должны быть отсортированы. Без этого бинпоиск бессмысленен.

Его же чаще всего пишут с багом, ошибаясь в границах. Неверный сдвиг lo/hi, пропущенный или лишний элемент, зацикливание на двух оставшихся. Пишите инвариант явно и проверяйте на массиве из одного-двух элементов, там всё и всплывает.

Недооценённый приём это бинарный поиск по ответу. Если можно быстро проверить «подходит ли значение X», а ответ монотонен (подошло X, подойдёт и всё, что больше), то сам ответ ищется бинпоиском, даже когда никакого отсортированного массива на входе нет. Так решаются задачи вида «минимальная скорость, чтобы успеть».

Стек

Структура «последним пришёл, первым вышел». Естественно ложится на проверку парности скобок: открывающую кладём на стек, на закрывающую снимаем верхнюю и сверяем.

def valid_brackets(s):
    pairs = {")": "(", "]": "[", "}": "{"}
    stack = []
    for c in s:
        if c in "([{":
            stack.append(c)
        elif not stack or stack.pop() != pairs[c]:
            return False
    return not stack       # всё закрыли, стек пуст

Версия посложнее это монотонный стек: он держит элементы по возрастанию или убыванию. Им решают «найти следующий больший элемент справа» за один проход вместо квадрата.

Куча (priority queue)

Когда нужен не полный порядок, а только «самый большой прямо сейчас». Задача: держать топ-k наибольших чисел в потоке из миллионов, не храня весь поток. Ответ это куча на k элементов. Новое число сравниваем с минимумом кучи, и если больше, заменяем. Память O(k) вместо O(n), и поток может быть хоть бесконечным.

BFS и DFS по графам

Обходы это фундамент всего, что про графы и деревья. Различие, которое любят спрашивать: в невзвешенном графе кратчайший путь находит BFS, а не DFS. BFS расходится волнами по уровням, поэтому, впервые дойдя до вершины, он дошёл по кратчайшему маршруту. DFS уходит вглубь по одной ветке и такой гарантии не даёт.

Два обязательных момента при обходе. Помечайте посещённые вершины, иначе на графе с циклом зациклитесь. И на больших графах не ходите рекурсивным DFS: в Python он упрётся в лимит глубины стека. Заводите явный стек или поднимайте лимит, но осознанно.

Backtracking

Перебор с отсечением. Генерируете варианты (перестановки, комбинации, расстановку ферзей), но как только ветка стала заведомо проигрышной, отрезаете её и откатываетесь. От полного перебора отличается тем, что не достраивает безнадёжные варианты до конца. Только трезво оценивайте масштаб: подмножеств у множества из n элементов 2ⁿ, перестановок n!. Backtracking спасает от лишней работы, но экспоненту в общем случае не отменяет.

Динамическое программирование

Пугает сильнее всех, а сводится к двум вопросам: что взять за состояние и как из меньших состояний собрать большее (переход). Наивная рекурсия для чисел Фибоначчи разворачивается в дерево с повторными вычислениями и работает за экспоненту. Стоит запомнить уже посчитанное, и она схлопывается в линию.

Две формы записи одного и того же:

мемоизация: обычная рекурсия плюс кэш посчитанных подзадач, сверху вниз;
табуляция: заполняем таблицу от базовых случаев к ответу, снизу вверх.

На этих рельсах едут классические задачи: рюкзак 0/1, размен суммы минимальным числом монет (где жадность «бери самую крупную» не всегда оптимальна), наибольшая общая подпоследовательность, LIS. Начало всегда одно: определить состояние и переход. Остальное техника.

Сложность: на чём валятся первым

Алгоритм можно написать правильно и всё равно завалить секцию, если плывёте в оценке сложности. Что спрашивают чаще всего:

O-нотация это про скорость роста, а не про точное число операций. O(n) значит, что при удвоении входа время растёт примерно вдвое. Константы и младшие члены отбрасывают: O(2n + 5) это O(n).
Амортизированная сложность. append в список это O(1) в среднем, хотя изредка массив переаллоцируется и копируется целиком. Разбросав редкую дорогую операцию по всем дешёвым, получаем амортизированную O(1).
Средний случай и худший это разные вещи. У quicksort в среднем O(n log n), но при неудачном выборе опорного элемента O(n²). Сказать «quicksort это O(n log n)» и промолчать про худший случай, вот и повод для доп-вопроса.
С «A всегда быстрее B» осторожнее. O(n log n) асимптотически лучше O(n²), но на маленьких n и с большими константами реальность бывает обратной. Асимптотика это про поведение на росте, а не приговор на всех входах.

Классические баги, которые интервьюер ждёт

Некоторые ошибки настолько типовые, что их проверяют специально:

Границы в бинарном поиске. Самый частый источник багов, см. выше.
pop(0) у списка это O(n): Python сдвигает все элементы. Нужна очередь FIFO, берите collections.deque, там это O(1).
Рекурсивный обход большого графа. Переполнение стека. Спасает явный стек или поднятый лимит.
Наивная рекурсия там, где нужна мемоизация. Экспонента на ровном месте.

Как готовиться, чтобы это работало

Не ставьте целью «прорешать N задач». Число решённых это тщеславная метрика: можно закрыть три сотни и провалиться, если каждую щёлкал как отдельную головоломку. Работает другое:

Разбирайте по паттернам, а не подряд. Взяли хеши, прорешали десяток задач на хеши, пока приём не станет рефлексом. Потом два указателя. И дальше по карте выше.
Возвращайтесь к тому, что забыли. Паттерн, разобранный неделю назад и ни разу не повторённый, к собесу выветрится. Гоняйте темы по кругу, налегая на те, где плывёте. Забывается ровно то, что не повторяешь.
Проговаривайте вслух и считайте сложность. Каждое решение заканчивайте фразой «это работает за столько-то». Тренируйте руки и язык сразу: на собесе говорить придётся не меньше, чем писать.

SQL, кстати, спрашивают отдельной секцией и по своим правилам. Если готовитесь к аналитике или дата-инженерии, посмотрите разбор SQL-задач с собесов.

Где тренироваться на русском

Разбор прочитать мало: паттерн ставится руками. Берёте задачу, выбираете приём, проверяете себя, ошибаетесь, правите. Ровно под это в Сеньорчике собрана тема по алгоритмам: задачи с вариантами и разбором на русском, от сложности и хеш-таблиц до графов и динамики. Движок отслеживает, где вы плывёте, и возвращает эти темы, пока они не начнут отскакивать от зубов. Есть в треках Data Science и Java, начать можно бесплатно.

А карту паттернов держите под рукой перед собесом. Когда услышите условие, первым делом спросите себя: какой это из десяти приёмов. Чаще всего один из них.