Алгоритмы: минимум для ML-инженера

Рабочий минимум для алгоритмической секции без олимпиадной глубины: оценка сложности O(·), массивы и строки, хэш-таблицы, два указателя и скользящее окно, сортировка и бинарный поиск, стек и очередь, куча для top-k, BFS, DFS и топологическая сортировка, редакционное расстояние через ДП. Для каждой техники — идея, шаблон на Python, задача и типичная ошибка; план тренировок на 6–8 недель.

УРОКstage-11/11-3-interviews/05-algorithms.mdx3 ч 20 минУрок 5 из 6

После урока вы сможете

Оценивать сложность по времени и памяти и по ограничениям на размер входа понимать, какой алгоритм нужен
Узнавать по условию девять базовых техник и писать их шаблоны на Python без подсказок
Решать задачи на хэш-таблицы, скользящее окно, кучу и динамическое программирование и находить в них типичные ошибки
Составить план тренировки на 6–8 недель и вести разбор ошибок в тетради ошибок

Зачем это нужно

Алгоритмическая секция — классическая задача «на доске» вроде «найдите самую длинную подстроку без повторов». Многие компании дают её не только разработчикам, но и ML-инженерам. Это дешёвый фильтр: за 45 минут видно, умеет ли человек писать корректный код, оценивать его скорость и рассуждать вслух. Олимпиадная глубина здесь не нужна. Хватает рабочего минимума из девяти техник, и почти каждая уже встречалась вам в курсе:

хэш-таблица считает пары символов в BPE (урок 4.2.2);
куча и top-k — это top-k сэмплирование (4.1.3) и выдача лучших документов в RAG (8.2.1);
топологическая сортировка — порядок обхода графа в backward() из micrograd (3.2.2);
скользящее окно нарезает документы на чанки под окно контекста;
редакционное расстояние стоит за метриками WER и CER в распознавании речи (9.1.5).

Как вести себя на секции, вы уже знаете из урока 11.3.4: уточнить условие, проговорить план, написать, проверить на примере, назвать сложность. Здесь добавится одно правило: сначала назовите решение «в лоб» и его сложность, потом улучшайте. Перебор, сказанный за минуту, лучше молчания на пять минут.

Сложность O(·) на примерах

Сложность по времени отвечает на вопрос: как растёт число операций с размером входа $n$ ? Считают, сколько раз выполняется самая внутренняя строка. Один цикл по $n$ элементам — $O(n)$ . Два вложенных — $O(n^2)$ . Цикл, который каждый раз делит диапазон пополам, — $O(\log n)$ : для $n = 10^6$ это около 20 шагов. Сортировка — $O(n \log n)$ .

Чтобы перевести сложность в секунды, нужна одна константа. Python выполняет порядка $10^7$ простых операций в секунду: цикл из $10^7$ сложений в CPython 3.11 занял у нас 0.73 с. Отсюда таблица, по которой ограничения в условии подсказывают нужный алгоритм. Это оценка порядка, а не точная граница.

Размер входа	Сколько операций в $O(n^2)$	Что подойдёт за 1–2 с на Python
$n \le 20$	—	даже $O(2^n)$ : $2^{20} \approx 10^6$
$n \le 10^3$	$10^6$	$O(n^2)$
$n \sim 10^5$	$10^{10}$ — часы	$O(n \log n)$ или $O(n)$
$n \sim 10^7$	$10^{14}$	только $O(n)$ , и лучше векторно на NumPy

Сложность по памяти считают так же. Матрица попарных расстояний для $10^5$ объектов — это $10^{10}$ чисел float64, то есть 80 ГБ. Поэтому в уроке 11.3.4 AUC считали через сортировку, а не через матрицу пар.

Главная ловушка Python — операции, которые выглядят мгновенными, но стоят $O(n)$ :

Операция	Сложность	Замена
`x in some_list`	$O(n)$	`x in some_set` — $O(1)$ в среднем
`lst.pop(0)`, `lst.insert(0, x)`	$O(n)$	`collections.deque`: `popleft()` за $O(1)$
`s += ch` в цикле по строке	может стать $O(n^2)$	собрать список и `"".join(parts)`
`sorted(lst)` внутри цикла	$O(n \log n)$ на каждый шаг	отсортировать один раз или взять кучу

Цифры с той же машины. Дедупликация 20 000 строк проверкой if d not in seen заняла 0.94 с, когда seen — список, и 2.7 мс, когда seen — множество. Разница в 350 раз, а код отличается одним словом. 100 000 вызовов list.pop(0) заняли 0.9 с, а столько же deque.popleft() — 4 мс.

Девять техник

1. Массивы и строки: префиксные суммы

Идея. Если нужно много раз спрашивать «сумма на отрезке $[l, r)$ », посчитайте один раз префиксные суммы $P_i = a_0 + \dots + a_{i-1}$ . Тогда сумма отрезка — $P_r - P_l$ за $O(1)$ .

def prefix_sums(a):
    p = [0]
    for x in a:
        p.append(p[-1] + x)      # p[i] — сумма первых i элементов
    return p

tokens = [120, 340, 90, 410, 75]        # длины документов в токенах
p = prefix_sums(tokens)
print(p[4] - p[1])                      # документы 1..3: 340 + 90 + 410 = 840

Типичная ошибка — путаница с границами. Договоритесь о полуинтервалах $[l, r)$ , как в срезах Python, и держитесь их во всём решении: тогда длина отрезка — r - l, а пустой отрезок — l == r.

2. Хэш-таблицы: dict и set

Идея. хеш-таблица находит ключ за $O(1)$ в среднем. Почти любую задачу «найти пару, повтор, посчитать» она переводит из $O(n^2)$ в $O(n)$ .

def two_sum(nums, target):              # LeetCode 1: индексы двух чисел с суммой target
    first = {}                          # значение → индекс, где оно встретилось впервые
    for j, x in enumerate(nums):
        if target - x in first:         # «дополнение» уже встречалось — пара найдена
            return first[target - x], j
        first.setdefault(x, j)
    return None

Задача с разбором. Сгруппировать анаграммы: «кот», «ток», «окт». Перебор пар — $O(n^2)$ сравнений. Лучше придумать ключ, одинаковый у всех анаграмм: отсортированные буквы "".join(sorted(w)). Группировка по ключу в словаре — один проход. Подбор ключа — главный приём хэш-таблиц. Подсчёт пар в BPE устроен так же: ключ — кортеж из двух токенов.

Типичные ошибки. Список как ключ: TypeError: unhashable type: 'list', нужен кортеж. Изменение словаря во время обхода по нему: RuntimeError. И in по списку там, где нужен set.

3. Два указателя и скользящее окно

Идея. два указателя: два индекса движутся только вперёд, поэтому вместо вложенного цикла получается один проход. скользящее окно — частный случай: окно [left, right) растёт вправо и сжимается слева, пока нарушает условие. Каждый индекс входит в окно и выходит из него не больше одного раза, отсюда $O(n)$ .

def longest_unique(s):                  # LeetCode 3: самая длинная подстрока без повторов
    last, left, best = {}, 0, 0
    for right, ch in enumerate(s):
        if ch in last and last[ch] >= left:    # повтор ВНУТРИ окна
            left = last[ch] + 1                # сдвигаем левую границу за прошлое вхождение
        last[ch] = right
        best = max(best, right - left + 1)
    return best

Задача с разбором. Для «pwwkew» окно растёт до «pw». На второй «w» левая граница прыгает за первую «w», окно становится «w», потом «wk» и «wke» — длина 3. Перебор всех подстрок дал бы $O(n^2)$ подстрок и ещё $O(n)$ на проверку каждой.

Типичная ошибка — условие last[ch] >= left. Без него на строке «abba» вторая «a» вернёт левую границу назад, на позицию 1, и окно «bba» с повтором будет посчитано как ответ.

4. Сортировка и бинарный поиск

Идея. После сортировки за $O(n \log n)$ многие задачи решаются одним проходом. двоичный поиск находит элемент в отсортированном массиве за $O(\log n)$ (модуль bisect). Самое полезное применение для ML — бинарный поиск по ответу. Если условие монотонно («влезает в память» верно для всех batch size до какого-то порога и неверно после), порог ищется за $\log_2$ шагов, а не перебором.

def max_true(lo, hi, ok):               # ok: True … True False … False; ищем последний True
    while lo < hi:
        mid = (lo + hi + 1) // 2        # округление ВВЕРХ, иначе при lo = mid цикл зависнет
        if ok(mid):
            lo = mid
        else:
            hi = mid - 1
    return lo

fits = lambda batch: batch * 0.75 <= 40          # условно: 0.75 ГБ на пример, 40 ГБ свободно
print(max_true(1, 1024, fits))                   # 53 — за 10 проверок вместо 53

На настоящей карте fits — это попытка сделать шаг обучения и поймать ошибку нехватки памяти. Каждая проверка стоит секунды, поэтому 10 попыток вместо 53 — реальная экономия.

Типичная ошибка — бесконечный цикл. При mid = (lo + hi) // 2 и ветке lo = mid два соседних значения lo и hi дают mid == lo навсегда. Проверяйте шаблон на диапазоне из двух элементов.

5. Стек и очередь

Идея. стек (последним пришёл — первым ушёл) хранит «незакрытое»: открытые скобки, вызовы функций. очередь (первым пришёл — первым ушёл) — это порядок обработки, например в обходе в ширину.

def balanced(text):                     # LeetCode 20: правильно ли вложены скобки
    pairs = {")": "(", "]": "[", "}": "{"}
    stack = []
    for ch in text:
        if ch in "([{":
            stack.append(ch)
        elif ch in pairs:
            if not stack or stack.pop() != pairs[ch]:   # закрыли не то или закрывать нечего
                return False
    return not stack                    # в конце всё должно быть закрыто

Задача с разбором. Быстрая проверка, не оборван ли JSON-ответ модели по max_tokens (урок 8.1.1). Оборванный ответ оставляет в стеке незакрытые { и [. Полный разбор всё равно делает json.loads, но стек сразу говорит, где оборвалось. Учтите только, что скобки внутри строк JSON надо пропускать.

Типичные ошибки. Очередь на list.pop(0) — $O(n)$ на каждый вызов. Забытая проверка пустого стека перед pop(). Забытая проверка «стек пуст в конце»: для строки «((» функция без неё вернёт True.

6. Куча для top-k

Идея. куча отдаёт минимум за $O(1)$ , вставка и извлечение стоят $O(\log n)$ . Чтобы найти $k$ лучших из $n$ , держат min-кучу размера $k$ . Новый элемент лучше вершины — вершина выбрасывается. Итог — $O(n \log k)$ вместо $O(n \log n)$ полной сортировки, и памяти нужно $O(k)$ , даже если данные идут потоком.

import heapq

def top_k_frequent(counts, k):          # LeetCode 347: k самых частых, ничьи — по алфавиту
    return heapq.nsmallest(k, counts.items(), key=lambda kv: (-kv[1], kv[0]))

def kth_largest(nums, k):               # LeetCode 215
    heap = nums[:k]
    heapq.heapify(heap)                 # O(k)
    for x in nums[k:]:
        if x > heap[0]:
            heapq.heapreplace(heap, x)  # выбросить минимум и положить x — O(log k)
    return heap[0]

Задача с разбором. Поисковый индекс RAG разбит на 16 шардов, каждый вернул свои 100 лучших документов по убыванию скора. Нужны общие 10 лучших. Склеивать 1600 пар и сортировать незачем. Положите в кучу по одной «голове» от каждого шарда, извлекайте максимум и добавляйте следующий элемент того же шарда. Получается $O(k \log s)$ для $s$ шардов (LeetCode 23, слияние $k$ отсортированных списков).

Типичные ошибки. heapq — min-куча: для максимума кладите $-\text{score}$ . При равных первых элементах кортежи сравниваются по вторым. Если там словари, Python бросит TypeError. Добавляйте счётчик-разрешитель ничьих: (-score, counter, doc).

7. Графы: BFS, DFS и топологическая сортировка

Идея. Граф хранят словарём смежности {вершина: [соседи]}. Обход в ширину идёт слоями через очередь и в невзвешенном графе находит кратчайший путь по числу рёбер. Обход в глубину идёт «до упора», потом назад; он ищет компоненты связности и циклы. топологическая сортировка упорядочивает вершины ориентированного графа без циклов так, что каждая идёт после всех, от которых зависит.

flowchart LR
A["скачать дамп"] --> B["очистить HTML"]
B --> C["дедупликация"]
C --> E["токенизация"]
D["обучить токенизатор"] --> E
E --> F["упаковка в шарды"]

Пайплайн данных как граф зависимостей: топологическая сортировка даёт порядок запуска шагов

from collections import deque

def topo_order(graph):                  # алгоритм Кана; graph: {шаг: [шаги, которые от него зависят]}
    indeg = {v: 0 for v in graph}
    for v in graph:
        for u in graph[v]:
            indeg[u] += 1
    queue = deque(v for v in graph if indeg[v] == 0)    # шаги без зависимостей
    order = []
    while queue:
        v = queue.popleft()
        order.append(v)
        for u in graph[v]:
            indeg[u] -= 1
            if indeg[u] == 0:           # все зависимости u выполнены
                queue.append(u)
    if len(order) < len(graph):
        raise ValueError("в графе цикл — порядка выполнения нет")
    return order

Задача с разбором. «Можно ли пройти все курсы, если у некоторых есть пререквизиты?» (LeetCode 207) — это вопрос «есть ли в графе цикл». Алгоритм Кана отвечает на него сам: если в order попали не все вершины, у оставшихся входящая степень так и не обнулилась. BFS пишется по тому же шаблону: deque, множество посещённых, слой за слоем.

Типичные ошибки. Нет множества посещённых — обход ходит по циклу вечно. Вершину отмечают посещённой при извлечении из очереди, а не при добавлении, и одна вершина попадает в очередь много раз. Рекурсивный DFS на длинной цепочке упирается в лимит глубины рекурсии Python (по умолчанию 1000) — переходите на явный стек.

8. Простое динамическое программирование: редакционное расстояние

Идея. Динамическое программирование — это ответ большой задачи из ответов подзадач, которые хранятся в таблице. Нужно ответить на три вопроса: что такое подзадача, как её ответ выражается через меньшие (переход) и что известно сразу (база).

редакционное расстояние — минимальное число вставок, удалений и замен, превращающих строку $a$ в $b$ . Подзадача $D[i][j]$ — расстояние между первыми $i$ символами $a$ и первыми $j$ символами $b$ :

D[i][j] = \min\big(D[i-1][j] + 1,\; D[i][j-1] + 1,\; D[i-1][j-1] + [a_i \ne b_j]\big), \qquad D[i][0] = i,\; D[0][j] = j.

Первое слагаемое — удалить $a_i$ , второе — вставить $b_j$ , третье — заменить (бесплатно, если символы совпали). Таблица для «кот» → «скот»:

	∅	с	к	о	т
∅	0	1	2	3	4
к	1	1	1	2	3
о	2	2	2	1	2
т	3	3	3	2	1

Ответ в правом нижнем углу — 1: одна вставка «с». Таблица заполняется по строкам, и каждой строке нужна только предыдущая. Поэтому памяти хватает на две строки: $O(\min(n, m))$ вместо $O(nm)$ .

Связь с метриками. WER (word error rate) — то же расстояние, только элементы — слова, делённое на длину эталона: «мама мыла раму» против «мама мыло раму» даёт $1/3$ . CER — по символам; для китайского, где нет пробелов, это основная метрика. WER может быть больше 1: вставок бывает больше, чем слов в эталоне.

Типичные ошибки. Неверная база (нулевая первая строка вместо $0, 1, 2, \dots$ ). Сдвиг индексов: в таблице $i$ , а в строке — a[i - 1]. Таблица $n \times m$ там, где нужно только число.

Как узнать технику по условию

Признак в условии	Техника
«найти пару», «есть ли повтор», «посчитать, сгруппировать»	хэш-таблица
«подотрезок или подстрока с условием», «самый длинный кусок, который…»	скользящее окно
массив отсортирован или условие монотонно («наибольший, при котором…»)	бинарный поиск
«k лучших», «k самых частых», «слить отсортированные списки»	куча
скобки, вложенность, «ближайший больший слева»	стек
«за сколько шагов», уровни, кратчайший путь без весов	BFS
зависимости, «в каком порядке выполнить», «есть ли цикл»	топологическая сортировка
«минимум операций», «сколько способов», две строки и их префиксы	динамическое программирование
$n \le 20$	перебор всех подмножеств или перестановок

Как тренироваться: план на 6–8 недель

Алгоритмы — навык руки, а не знания. Прочитать разбор полезно, но без самостоятельного решения он забывается за неделю. Ниже наш рекомендуемый план: 1–1.5 часа в день, 5 дней в неделю, около 80 задач. Это не гарантия и не норматив, а ритм, который реально выдержать параллельно с работой.

Неделя	Темы	Задач	На что смотреть
1	Сложность, массивы, строки, хэш-таблицы	12	Сначала оценить сложность, потом писать
2	Два указателя, скользящее окно	10	Шаблон окна наизусть, ловушка «abba»
3	Сортировка, бинарный поиск, бинпоиск по ответу	10	Шаблон без бесконечного цикла
4	Стек, очередь, куча	10	`deque`, `heapq`, разрешение ничьих
5	Графы: BFS, DFS, топологическая сортировка	10	Множество посещённых, итеративный DFS
6	Динамическое программирование	10	Подзадача, переход, база — словами до кода
7–8	Смешанные задачи с таймером, пробные собеседования	15–20	45 минут на задачу, вслух

Где решать. LeetCode — главная площадка с автотестами; у неё есть китайская версия LeetCode China со своими обсуждениями. Олимпиадные площадки вроде Codeforces полезны, если вам нравятся соревнования, но для собеседований глубже, чем нужно. Учебник к задачам — hello-algo (о нём в китайском углу ниже), у него есть русский перевод. Если задача из урока по номеру LeetCode не открывается, найдите её по названию: «Two Sum», «Longest Substring Without Repeating Characters», «Top K Frequent Elements», «Edit Distance».

Правило 30 минут. Решили сами за 30 минут — зачёт. Не решили — прочитайте разбор, закройте его и напишите решение заново. Такая задача идёт в тетрадь ошибок.

Как разбирать ошибки. На каждую проваленную задачу заведите в тетради ошибок запись из пяти строк:

условие в одну фразу;
какая техника нужна и по какому признаку её можно было узнать (таблица выше);
где ошиблись: не та идея, реализация или крайний случай;
правильная идея в одну фразу;
даты повтора: через 1, 3 и 7 дней решить заново без подсказок.

Через месяц такая тетрадь покажет ваши личные слабые места. У одних это бинарный поиск по ответу, у других — база ДП. Именно их и стоит тренировать на неделях 7–8.

Практика

Четыре задачи, по одной на ключевую технику. Таймеры — на всё задание целиком. Сначала назовите вслух решение «в лоб» и его сложность, потом пишите быстрое.

Хэш-таблица. Таймер: 20 минут.

Частые слова, анаграммы и Two Sum через хэш-таблицу5 тестов

import re

# Хэш-таблица: dict и set ищут ключ за O(1) в среднем. Таймер: 20 минут на все четыре функции.
# Collections.Counter не используйте — смысл в том, чтобы написать счётчик словарём самому.

WORD = re.compile(r"[0-9a-zа-яё]+|[\U0001F300-\U0001FAFF]")   # слово из букв/цифр или один эмодзи


def word_freq(text):
    """Частоты слов: dict {слово: сколько раз}. Слова — WORD.findall(text.lower()).

    Эмодзи часто пишут подряд, без пробелов, поэтому каждый эмодзи здесь — отдельное «слово».
    Пример: word_freq("Мама мыла раму, мама!") → {"мама": 2, "мыла": 1, "раму": 1}.
    """
    # TODO: проход по словам, counts[w] = counts.get(w, 0) + 1
    ...


def first_repeated_word(text):
    """Первое слово, которое встретилось ВТОРОЙ раз (по месту повтора), или None, если повторов нет.

    Пример: "a b b a" → "b" (b повторилась на позиции 2, раньше чем a на позиции 3). O(n) через множество.
    """
    # TODO: ваш код
    ...


def group_anagrams(words):
    """Группы анаграмм — слов из одних и тех же букв: «кот», «ток», «окт».

    Ключ словаря — "".join(sorted(слово)). Группы — в порядке первого появления, слова внутри — в порядке появления.
    Пример: ["кот", "нос", "ток", "сон"] → [["кот", "ток"], ["нос", "сон"]].
    """
    # TODO: ваш код
    ...


def two_sum(nums, target):
    """Пара индексов (i, j), i < j, с nums[i] + nums[j] == target, или None.

    Из всех таких пар — с наименьшим j, а при нём с наименьшим i (так получается при одном проходе слева направо
    со словарём «значение → первый индекс»). Двойной цикл O(n²) не пройдёт тест на скорость.
    Пример: two_sum([2, 7, 11, 15], 9) → (0, 1).
    """
    # TODO: ваш код
    ...


print(word_freq("Мама мыла раму. Мама — молодец! 👍👍 AI"))
print(first_repeated_word("кот видит кота, а кот видит мышь"))   # кот
print(group_anagrams(["кот", "нос", "ток", "сон", "окт", "кит"]))
print(two_sum([2, 7, 11, 15], 9))                                 # (0, 1)

Куча. Таймер: 25 минут.

Top-k и слияние шардов через кучу6 тестов

import heapq

# Куча (heapq) — минимум за O(1), вставка и извлечение за O(log n). Таймер: 25 минут на три функции.
# heapq — это MIN-куча: для «самых больших» держите кучу размера k из лучших и выкидывайте наименьший.


def kth_largest(nums, k):
    """k-й по величине элемент (k = 1 — максимум). Куча размера k: O(n log k). Список nums не менять.

    Пример: kth_largest([3, 2, 1, 5, 6, 4], 2) → 5.
    """
    # TODO: ваш код
    ...


def top_k_frequent(counts, k):
    """k самых частых слов: список пар (слово, частота) по убыванию частоты, при равенстве — по алфавиту.

    counts — dict {слово: частота}. k ≤ 0 → []; k больше числа слов → все слова.
    Подойдёт heapq.nsmallest(k, ..., key=...) — внутри он держит кучу размера k: O(n log k), а не O(n log n).
    Пример: top_k_frequent({"a": 5, "b": 2, "c": 5}, 2) → [("a", 5), ("c", 5)].
    """
    # TODO: ваш код
    ...


def merge_shards(shards, k):
    """Слить топы из нескольких шардов поискового индекса (как в RAG с шардированным индексом).

    shards — список списков пар (score, doc_id); каждый отсортирован по убыванию score
    (при равных score — по возрастанию doc_id). Вернуть k лучших пар по убыванию score, при равенстве —
    меньший doc_id раньше. Через кучу из «голов» шардов: O(k log s), где s — число шардов.
    Пример: merge_shards([[(0.9, "d1"), (0.5, "d4")], [(0.8, "d2")]], 2) → [(0.9, "d1"), (0.8, "d2")].
    """
    # TODO: ваш код
    ...


print(kth_largest([3, 2, 1, 5, 6, 4], 2))                                  # 5
print(top_k_frequent({"кот": 3, "ток": 3, "кит": 3, "нос": 1}, 2))          # [('кит', 3), ('кот', 3)]
print(merge_shards([[(0.9, "d1"), (0.5, "d4")], [(0.8, "d2"), (0.7, "d3")], []], 3))

Скользящее окно. Таймер: 25 минут.

Подстрока без повторов и кусок документа под бюджет контекста6 тестов

# Скользящее окно: [left, right) расширяем вправо и сжимаем слева, пока условие нарушено. Таймер: 25 минут.
# Каждый индекс входит в окно и выходит из него не больше одного раза — поэтому O(n), а не O(n²).


def longest_unique_substring(s):
    """Самая длинная подстрока без повторяющихся символов; при равной длине — самая левая.

    Подсказка к шаблону: словарь «символ → последняя позиция». Если символ уже был ВНУТРИ окна,
    левую границу сдвигаем за его прошлую позицию (но никогда не назад!).
    Примеры: "abcabcbb" → "abc", "pwwkew" → "wke", "" → "".
    """
    # TODO: ваш код
    ...


def longest_fit(lengths, budget):
    """Самый длинный непрерывный кусок документа, который влезает в бюджет контекста.

    lengths — длины предложений в токенах (целые > 0), budget — сколько токенов помещается в окно модели.
    Вернуть (start, end): отрезок lengths[start:end] с суммой ≤ budget и наибольшим числом предложений
    end − start; при равенстве — самый левый. Если не влезает ни одно предложение — (0, 0).
    Пример: longest_fit([3, 1, 2, 7, 1, 1, 1], 5) → (4, 7) — три последних предложения, 3 токена.
    """
    # TODO: ваш код
    ...


print(longest_unique_substring("abcabcbb"))                # abc
print(longest_unique_substring("🙂👍🙂🔥🚀👍"))                # 👍🙂🔥🚀
print(longest_fit([3, 1, 2, 7, 1, 1, 1], 5))              # (4, 7)

Динамическое программирование. Таймер: 25 минут.

Редакционное расстояние, WER и CER6 тестов

# Динамическое программирование: ответ большой задачи собирается из ответов маленьких. Таймер: 25 минут.
# D[i][j] — расстояние между a[:i] и b[:j]. База: D[i][0] = i (удалить i символов), D[0][j] = j (вставить j).
# Переход: D[i][j] = min(D[i-1][j] + 1, D[i][j-1] + 1, D[i-1][j-1] + (a[i-1] != b[j-1])).


def edit_distance(a, b):
    """Расстояние Левенштейна: минимум вставок, удалений и замен (по 1 за каждую), чтобы из a получить b.

    a и b — строки или списки токенов. Храните только две строки таблицы: O(min(n, m)) памяти.
    Примеры: ("kitten", "sitting") → 3, ("кот", "скот") → 1.
    """
    # TODO: ваш код
    ...


def wer(reference, hypothesis):
    """Word Error Rate: edit_distance по словам (str.split()), делённое на число слов эталона.

    Пустой эталон → ValueError. Пример: wer("мама мыла раму", "мама мыло раму") → 1/3.
    """
    # TODO: ваш код
    ...


def cer(reference, hypothesis):
    """Character Error Rate: то же по символам (пробел — тоже символ). Пустой эталон → ValueError."""
    # TODO: ваш код
    ...


print(edit_distance("kitten", "sitting"))            # 3
print(wer("мама мыла раму", "мама мыло раму"))        # 0.333…
print(cer("мама", "папа"))                            # 0.5

Китайский угол: «шуати», китайский LeetCode и открытые маршруты подготовки

Систематическое решение задач перед собеседованиями по-китайски называют «шуати». Главная площадка — китайская версия LeetCode, leetcode.cn (по-китайски «Ликоу»). Вокруг неё выросли открытые учебники и маршруты на GitHub. Три из них полезны и русскоязычному читателю.

hello-algo «Hello, алгоритмы» — учебник по структурам данных и алгоритмам с анимациями и кодом, который запускается в один клик (в том числе на Python). Есть русский перевод на hello-algo.com/ru. К этому уроку подходят главы 2.3 о временной сложности, 6.1 «Хеш-таблица», 8.3 «Задача Top-k», 9.3 «Обход графа» и 14.6 о расстоянии редактирования. Книгу рекомендуют профессор Университета Цинхуа Дэн Цзюньхуэй и Ли Му, один из авторов «Dive into Deep Learning» (d2l): по его словам, с такой книгой учить алгоритмы было бы в 10 раз проще. Лицензия CC BY-NC-SA 4.0 — для личной учёбы свободно.
«Записки о коде» · leetcode-master — готовый маршрут: темы идут в порядке «массивы → связные списки → хэш-таблицы → … → графы», в каждой — теория, задачи по порядку и итоговый разбор. В маршруте есть ровно наши задачи: 347 «k самых частых элементов» в разделе о стеке и очереди и 72 «редакционное расстояние» в разделе о ДП. Основной язык разборов — C++, но к задачам есть решения на Python.
«Алгоритмические заметки labuladong» — подход «мышление каркасами» (шаблонами): отдельные шаблоны для скользящего окна, BFS, динамического программирования. Есть английская версия на labuladong.online. Там же есть страница «Шаблоны кода для режима ACM». На части онлайн-тестов ввод нужно читать из stdin и печатать ответ самому, а не писать функцию, как на LeetCode. Перед таким тестом стоит отрепетировать этот формат.

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

Проверь себя

Проверь себя6 вопросов

1 Во входе до

n = 10^5

чисел, лимит — 2 секунды на Python. Подойдёт ли решение с двумя вложенными циклами по всем парам?Да, 10⁵ — это немногоНет: это около 10¹⁰ операций, при ~10⁷ операций в секунду — часы; нужен O(n log n) или O(n)Да, если писать на NumPy поэлементно в цикле

2 Какой структурой лучше хранить очередь в обходе в ширину на Python?list с append и pop(0)collections.deque с append и popleftsetdict с ключами-номерами

3 Чему равна длина самой длинной подстроки без повторяющихся символов в строке «pwwkew»?

4 Чему равно редакционное расстояние между «кот» и «скат»?

5 Какие задачи естественно решаются кучей размера

k

за

O(n \log k)

?Можно выбрать несколько ответовk самых частых слов в корпусеk-й по величине элемент массиваСлияние уже отсортированных выдач нескольких шардов индекса в общий топ-kПроверка правильной вложенности скобок

6 Алгоритм Кана на графе из 6 вершин вернул порядок только из 4 вершин. Что это значит?Ошибка в коде: топологическая сортировка всегда возвращает все вершиныВ графе есть цикл: у двух оставшихся вершин входящая степень так и не обнулиласьДве вершины изолированы и не имеют рёбер

Итоги

Сложность переводится в секунды одной константой: Python делает порядка $10^7$ простых операций в секунду. По ограничениям на $n$ видно, нужен ли $O(n \log n)$ вместо $O(n^2)$ .
Самые дорогие ошибки на Python — операции, которые выглядят мгновенными: in по списку, pop(0), сортировка внутри цикла.
Рабочий минимум — девять техник: префиксные суммы, хэш-таблицы, два указателя и окно, сортировка и бинарный поиск (в том числе по ответу), стек и очередь, куча для top-k, BFS, DFS и топологическая сортировка, простое ДП. Технику обычно выдаёт признак в условии.
Тренировка — 6–8 недель по темам, около 80 задач, правило 30 минут и тетрадь ошибок с повторами через 1, 3 и 7 дней.

Дальше: урок 11.3.6 — резюме, портфолио и рассказ о проектах: как превратить проекты курса и выпускной проект в опыт, который видно работодателю.