Алгоритмы с нуля
Инструментарий: выбор техники
Суть Кросс-трековый тест: прочти задачу и выбери технику и причину, взвешивая сложность, структуру данных и режим отказа неверного инструмента.
Высота — путь к senior
НольJuniorMiddleSenior
Ты на middle-высоте — в небеВесь трек сводится к одному навыку: прочесть задачу и назвать верный инструмент до того, как написана первая строка. Каждый вопрос даёт формулировку задачи и спрашивает не ‘каков ответ’, а ‘какая техника и почему именно она, а не соблазнительный неверный вариант’.
Цель
Убедись, что умеешь отображать форму задачи — её ограничения, структуру, то, что она просит — на подходящую технику и объяснять, почему очевидная альтернатива не работает или тратит время.
Викторина
Completed
Дан неотсортированный массив из 10^6 целых чисел; нужно ответить на 10^5 запросов вида 'существует ли значение X?'. Какой подход и почему?
Heads-up Это работает и годится как запасной вариант, но для чистой проверки принадлежности hash set отвечает за O(1) в среднем против O(log n), и ты избегаешь сортировки за n log n. Бинарный поиск выигрывает, только если нужен ещё порядок или диапазонные запросы.
Heads-up O(n) на запрос умножить на 10^5 запросов даёт 10^11 операций. Весь смысл трека — потратить O(n) препроцессинга один раз, чтобы каждый запрос стал дешёвым. Это та грубая сила, ради победы над которой существуют остальные инструменты.
Heads-up Сортировка не помогает запросу принадлежности, если потом не делать бинарный поиск; линейный проход после сортировки всё равно O(n) на запрос. Ты заплатил за сортировку и ничего не получил.
Викторина
Completed
Задача просит число различных способов набрать сумму N заданными номиналами монет. N до 10^4. Какая техника и в чём признак?
Heads-up Жадность даёт корректное решение для канонических систем монет, но НЕ считает все способы, а для произвольных номиналов может даже промахнуться мимо минимума. Подсчёт различных комбинаций требует суммирования по подзадачам — это DP, а не жадность.
Heads-up Backtracking обходит всё дерево комбинаций — экспонента от N. Подзадачи сильно перекрываются (одна и та же оставшаяся сумма встречается в разных ветвях), а это и есть сигнал к мемоизации или табуляции. Чистый backtracking упирается в таймаут.
Heads-up Бинарный поиск по ответу требует монотонного предиката допустимости на числовом диапазоне. Число способов набрать сумму — задача подсчёта без такой монотонной структуры для деления пополам.
Викторина
Completed
Нужно найти k наименьших элементов потока из n чисел (n заранее неизвестно, k фиксировано и мало). Какая структура данных несёт технику?
Heads-up Поток неизвестной длины нельзя отсортировать без буферизации всех n элементов, что стоит O(n) памяти и O(n log n) времени. Куча держит только k элементов и никогда не видит все n сразу.
Heads-up Min-heap размера k делает дешёвым извлечение наименьшего, но чтобы СОХРАНЯТЬ k наименьших, нужно дёшево вытеснять наибольший из текущих k — это максимум в корне max-heap. Min-heap заставляет сканировать за O(k), чтобы найти элемент на выброс.
Heads-up Hash set даёт принадлежность, а не порядок. Он не подскажет, какой элемент вытеснить, чтобы сохранить k наименьших. Упорядочивание по приоритету — работа кучи.
Викторина
Completed
Дан отсортированный массив; найди два индекса, значения которых дают в сумме target. Массив может быть огромным, а доп. памяти разрешено O(1). Какая техника?
Heads-up Two-sum через hash map — верный инструмент для НЕотсортированного массива, но стоит O(n) доп. памяти. Здесь массив уже отсортирован и память ограничена — two pointers использует порядок для O(1) памяти. Чтение ограничений выбирает инструмент.
Heads-up O(n log n) и игнорирует структуру, которую использует проход two pointers. Это работает, но строго медленнее, чем O(n)-проход two pointers, а вопрос просит использовать отсортированность полностью.
Heads-up Перебор всех пар — O(n^2) и полностью выбрасывает отсортированный порядок. Отсортированный вход — самая громкая подсказка для two pointers или бинарного поиска, но никак не для перебора пар грубой силой.
Викторина
Completed
Нужно определить, есть ли цикл в ориентированном графе зависимостей, и если нет — выдать корректный порядок сборки. Какая техника?
Heads-up Дейкстра находит кратчайшие взвешенные пути; он не определяет цикл в смысле зависимостей и не выдаёт порядок, уважающий все ограничения предшествования. Упорядочивание по зависимостям — это топологическая сортировка, а не кратчайший путь.
Heads-up Union-Find находит циклы в НЕориентированных графах. Графы зависимостей ориентированы, где о цикле сигнализирует обратное ребро, а не общая компонента, и тебе ещё нужен порядок. Топосортировка даёт и то, и другое.
Heads-up DP по подмножествам — для задач вроде гамильтоновых путей или TSP на малых графах (экспонента от V). Упорядочивание по предшествованию — это линейная топосортировка; DP здесь дико избыточно.
Викторина
Completed
Задача даёт n <= 20 предметов и просит оптимальное подмножество при ограничении, которое сопротивляется любой жадной или value-DP формулировке. Ограничения кричат об определённом семействе. О каком, и в чём признак n <= 20?
Heads-up Малое n не делает жадность корректной — корректность про структуру (аргумент обмена или матроид), а не про размер. Признак n <= 20 — это разрешение перебирать экспоненциально, именно потому что полиномиальные жадность или DP не подходят.
Heads-up Value-DP нужен ограниченный числовой измеритель для табуляции; задача сообщает, что сопротивляется такой формулировке. Когда естественное состояние ЕСТЬ подмножество, а n крошечно, перебирают подмножества (2^n), а не значения.
Heads-up Размеры ограничений — главный сигнал выбора техники. n <= 20 (около 10^6 подмножеств) против n <= 10^5 (нужно O(n log n)) против n <= 10^9 (нужно O(log n) или математика) указывают на разные семейства. Игнорировать n значит отбросить самую громкую подсказку.
Итог
Выбор техники — это чтение, а не зубрёжка. Размеры ограничений — самый громкий сигнал: n ≤ 20 разрешает перебор 2^n; n ≤ 10^5 требует O(n log n); 10^9 вынуждает O(log n) или математику. Глагол задачи называет семейство — ‘существует ли’ ведёт к хешированию; ‘k наименьших или следующий по приоритету’ к куче; ‘сколько способов или оптимизация по перекрывающимся подзадачам’ к DP; ‘лучший локальный выбор, который можно доказать’ к жадности; ‘упорядочить по зависимости’ к топосортировке; ‘пара в отсортированных данных при O(1) памяти’ к two pointers. Каждый неверный ответ выше — это реальный инструмент, применённый не туда; навык в том, чтобы сопоставить форму инструменту, а затем понимать, почему соблазнительная альтернатива тратит время или ломается.