Практикум: паттерны и план тренировок
Перед началом: весь курс — этот модуль собирает его в систему. Инструменты: Go 1.27, журнал решений (любой). Трудоёмкость: ~4 ч (теория 1.5 ч · практика 2.5 ч) + тренировки дальше.
🔥 Инцидент: «Триста решённых задач — и ступор на собеседовании»
Кандидат три месяца решал задачи подряд, по номерам, от лёгких к сложным. На собеседовании ему дали «минимальную вместимость корабля за D дней» — и он не узнал задачу: на LeetCode она выглядела иначе, тегов он не читал, а идею «бинарный поиск по ответу» ни разу не формулировал словами. Решённые задачи остались набором фактов, а не инструментов. Лечится это не количеством, а каталогом: у каждой задачи есть паттерн, и узнавать нужно паттерн, а не задачу. Этот модуль — ваш каталог: 30 паттернов курса, признаки узнавания и план тренировок.
📖 Теория
20.1 Каталог паттернов: признак → паттерн → модуль
Паттерн — это не название алгоритма, а связка «признак в условии → структура решения». Учите таблицу слева направо: признак вы увидите раньше, чем вспомните название.
| Признак в условии | Паттерн | Модуль |
|---|---|---|
| Отсортированный вход, «найти пару/тройку» | Два указателя | 3 |
| «Подотрезок / подстрока / окно» с монотонным условием | Скользящее окно | 3 |
| «Появлялось ли уже», частоты, группы | Хеш-таблица | 4 |
| Суммы на префиксах, «сумма подотрезка = k» | Префиксные суммы | 3 |
| «Следующий больше/меньше», вложенные скобки | Монотонный стек / стек | 5 |
| «Порядок последних использованных», LRU | Список + map | 6 |
| «Медиана/середина», цикл в списке | Fast/slow указатели | 6 |
| «Все варианты / комбинации / расстановки» | Перебор с возвратом | 7 |
| «Топ k», «k наименьших», слияние потоков | Куча | 9 |
| Данные отсортированы, поиск границы | Lower/upper bound | 10 |
| «Минимальное максимальное / минимальная вместимость» | Поиск по ответу | 10 |
| Обход дерева, «уровни», LCA | Обходы дерева / BFS | 11 |
| Поиск по префиксу, словарь | Trie | 13 |
| Сетка, «достижимость», «острова» | BFS/DFS по графу | 14 |
| «Порядок с зависимостями», цикл в графе | Топологическая сортировка | 14 |
| Группировка/слияние множеств, «лишнее ребро» | DSU | 15 |
| Взвешенный граф, «кратчайший/дешёвый маршрут» | Дейкстра | 15 |
| «Минимальная сеть, соединить всё» | MST (Краскал/Прим) | 15 |
| Интервалы: пересечения, брони, покрытия | Жадный по концу | 18 |
| «Минимум монет/шагов/путей» с выбором | DP (1D) | 16 |
| Рюкзак, «выбрать подмножество с суммой» | DP (2D) | 17 |
| Две строки: расстояние, общая часть | DP по двум строкам | 17 |
| «Самая длинная возрастающая подпоследовательность» | LIS: DP или tails+bsearch | 17 |
| Флаги, чётность, «элемент без пары» | Биты и XOR | 19 |
| Делимость, простые, степени по модулю | Математика | 19 |
Полный список — не для заучивания наизусть, а для закрытия пробелов: идите по строкам от модуля 1 к 19 и отмечайте, где «видел, но сам не писал».
20.2 Как узнавать паттерн: сигналы из условия
Три вопроса к условию — до написания кода:
- Что дано? Отсортировано → два указателя / бинарный поиск; сетка → граф; два словаря → trie; интервалы → сортировка по концу.
- Что просят? «Все варианты» → бэктрекинг; «оптимальное значение» → DP или жадный; «быстро проверить наличие» → хеш; «k из n» → куча.
- Что растёт и как? Одна строка → 1D DP; две → таблица; «независимые выборы на каждом шаге» → DP-состояние, а не жадный, если выбор влияет на будущее.
Ошибка узнавания стоит дороже ошибки реализации: выберете не тот паттерн — задача не сойдётся при любом качестве кода. Поэтому первые пять минут решения — это классификация, на бумаге, без редактора.
20.3 Три задачи end-to-end
Задача 1: LRU-кэш. Признак: «порядок последних использованных» →
map (доступ за O(1)) + двусвязный список (порядок за O(1)). Разбор — модуль 6.
Схема: get двигает узел в голову; put при переполнении удаляет хвост.
Задача 2: число островов. Признак: «сетка, достижимость» → граф, BFS/DFS. Разбор — модуль 14. Схема: проход по всем клеткам; земля запускает заливку, которая её же и «затапливает» — повторных обходов нет.
Задача 3: edit distance. Признак: «две строки, преобразование» →
DP по двум строкам, модуль 17. Схема: таблица (n+1)×(m+1), переход —
минимум из трёх; ответ в правом нижнем углу.
Общее у всех трёх: паттерн определил структуру данных, структура — код. Это и есть весь «секрет»: не заучивать решённые задачи, а собирать связки «признак → структура».
20.4 Процесс решения: пять шагов
- Уточните вход и крайние случаи. Пустой вход? Отрицательные числа? Дубликаты? Один элемент?
- Приведите маленький пример руками. Три-четыре элемента, на бумаге. Именно здесь паттерн проявляется.
- Сформулируйте наивное решение и его сложность. Даже O(n²) — это отправная точка и страховка, если не успеете иначе.
- Улучшайте или пишите. Если паттерн узнали — сразу целевое решение; если нет — пишите наивное и ищите, что пересчитывается зря.
- Проверьте на крайних случаях из шага 1 и проговорите сложность по времени и памяти.
На собеседовании шаги 1–3 важнее кода: интервьюер проверяет мышление, а не скорость набора. Проговаривайте «почему эта структура» — это ровно те доказательства инвариантов, которые вы делали в модулях 3, 10 и 14.
20.5 План тренировок на 8 недель
| Неделя | Тема | Задач |
|---|---|---|
| 1 | Массивы, окно, хеш (модули 2–4) | 8–10 |
| 2 | Стек, списки, рекурсия (5–7) | 8–10 |
| 3 | Сортировки, куча, бинарный поиск (8–10) | 8–10 |
| 4 | Деревья, trie, строки (11–13) | 8–10 |
| 5 | Графы: обходы, топосорт, DSU (14–15) | 8–10 |
| 6 | Дейкстра, MST, интервалы (15, 18) | 6–8 |
| 7 | DP: 1D и 2D (16–17) | 8–10 |
| 8 | Биты, математика, повторение слабых мест (19) | 6–8 + повтор |
Правила: одна задача — максимум 30 минут самостоятельной работы, потом разбор (не подсматривание кода, а чтение идей). Каждые выходные — 20–30 минут на задачи, где были ошибки: повторение важнее новых задач. Ведите журнал: дата, паттерн, ошибка (узнавание / реализация / крайний случай). Через три недели журнал покажет ваши системные дыры точнее любого списка тем.
20.6 Компромиссы
| Решение | За | Против |
|---|---|---|
| 30 мин на задачу, дальше разбор | Не застреваете, растёт покрытие | Привычка сдаваться быстро |
| 3 часа на задачу, но сам | Глубина, тренировка упорства | Мало паттернов за месяц |
| Много лёгких задач | Скорость, узнавание | Средних на интервью больше |
| Мало средних/сложных | Реализм интервью | Больно, если базы нет |
| Шпаргалка паттернов | Ускоряет узнавание | Заменяет понимание, если раньше времени |
Баланс: первые недели — много лёгких (закрепление паттернов), дальше соотношение 1 : 2 лёгких к средним, иначе собеседование на средних застанет врасплох. Шпаргалку пишите сами — по памяти, после недели решений; чужая шпаргалка в голову не переносится.
💻 Практика
- Личный каталог паттернов. Заведите таблицу: паттерн, признак, шаблон кода (10–15 строк), 2 задачи-представителя. Заполните по модулям 3–19 из памяти, потом сверьте с §20.1 — расхождения и есть ваши пробелы.
- Три шаблона-заготовки. Соберите собственный файл
templates.goс готовыми: (а) lower bound бинарного поиска; (б) BFS по сетке с 4 соседями; (в) DP «минимум монет» с 1D-массивом. Требование: каждый шаблон — с тестовым вызовом на фиксированных данных, вывод детерминирован. - Разбор трёх задач end-to-end. Возьмите три задачи из §20.3 и распишите для каждой по шагам §20.4: крайние случаи, пример руками, наивное решение и его сложность, целевое решение. Цель — научиться проговаривать путь, а не только писать код.
- Журнал и повтор. Заведите журнал решений по формату из §20.5 и перерешайте три задачи, где вы ошибались, — без подсматривания. Если повторное решение заняло больше 30 минут, паттерн не закреплён: вернитесь к соответствующему модулю курса.
🧩 Quiz
✅ Итоги модуля
- Паттерн — связка «признак условия → структура решения»; учить нужно признаки, а не задачи.
- Каталог курса: 26 паттернов от двух указателей до modpow — таблица §20.1 плюс ваш личный каталог из практики.
- Процесс решения из пяти шагов важнее скорости печати: классификация паттерна — первые пять минут любой задачи.
- План тренировок: 8 недель по модулям, 30 минут на задачу, повторение слабых мест, журнал ошибок.
🔗 Куда дальше
Курс закончился, библиотека — нет. У вас на руках: 20 модулей реализаций, собственные структуры (куча, хеш-таблица, trie, BST), три шаблона-заготовки и каталог паттернов. Что делать со всем этим дальше:
- Тренируйте по плану §20.5 — первые две недели по каталогу, дальше «слепые» задачи без тегов: узнавание важнее решения.
- Двигайтесь к продвинутым темам, когда база устоится: сегментное дерево и дерево Фенвика, суффиксный автомат, потоки и паросочетания, сжатие путей в DP. Все они — надстройки над этим курсом, не замена.
- Применяйте в продукте: структуры вы теперь умеете выбирать осознанно — от top-K в метриках до DSU в дедупликации аккаунтов.
Хорошая остановка — пересобрать свой каталог паттернов через месяц: он должен заполняться быстрее и точнее, а не переписываться с нуля.