Algorithms and Data Structures
Алгоритмы и структуры данных
Модель обучается за часы, а признаки считаются за сутки — обычно потому, что где-то в пайплайне стоит квадратичный цикл. Эта глава о том, как увидеть его заранее: оценка сложности, выбор структуры данных, классические приёмы и границы применимости каждого. У каждого приёма разобраны его частые типы с примерами и отдельно — сигналы в условии, по которым этот приём узнают. Плюс то, что спрашивают на алгоритмической секции собеседования.
Что означают метки тем
Problem Pattern Recognitionактуально
Как распознать паттерн задачиУровень над алгоритмами: по формулировке условия понять, какой приём здесь работает. «Отсортированный массив», «подряд идущие элементы», «ближайший больший справа» — каждая такая фраза указывает на конкретное семейство решений.
Two Pointers and Sliding Windowактуально
Два указателя: семейство приёмов4 темы внутриЗонтичная тема: что общего у четырёх приёмов с двумя индексами и как выбрать нужный. Сами приёмы разобраны каждый на своей странице.
Opposite-Direction Pointersактуально
Встречные указателивнутри «Два указателя: семейство приёмов»Два индекса сходятся с концов отсортированного массива. На каждом шаге отбрасывается конец, который заведомо не даст лучшего ответа, — и вместе с ним целая полоса пар.
Sliding Windowактуально
Скользящее окновнутри «Два указателя: семейство приёмов»Окно между двумя границами: правая расширяет, левая чинит. Состояние не пересчитывается, а обновляется инкрементально — отсюда линейное время на задачах о подотрезках.
Fast and Slow Pointersактуально
Быстрый и медленный указательвнутри «Два указателя: семейство приёмов»Два указателя идут в одну сторону с разной скоростью. Если структура зациклена, быстрый догоняет медленного — цикл находится без журнала посещённых узлов.
Same-Direction Pointersактуально
Два указателя в одну сторонувнутри «Два указателя: семейство приёмов»Слияние, пересечение и запись на месте: каждому источнику свой указатель, ни один не откатывается назад. Основа сортировки слиянием и merge join в базах данных.
Prefix Sumsактуально
Префиксные суммыОдин предварительный проход превращает сумму на любом отрезке в одно вычитание. Тот же приём вместе с хеш-таблицей находит подотрезок с заданной суммой за линейное время.
Monotonic Stack and Dequeактуально
Монотонный стек и декПриём поверх стека: хранить только тех, для кого ответ ещё не найден. Даёт ближайший больший элемент для всех позиций сразу и максимум в скользящем окне — за один проход.
Binary Searchактуально
Бинарный поискПоловинное деление на отсортированных данных: за логарифм шагов вместо линейного перебора. Приём шире поиска — им ищут ответ в любой монотонной задаче.
Dynamic Programmingактуально
Динамическое программированиеПеребор, в котором каждое подсостояние считается ровно один раз. Превращает экспоненциальный перебор в полиномиальный, если подзадачи перекрываются.
Greedy Algorithmsактуально
Жадные алгоритмыНа каждом шаге берём локально лучший вариант и не пересматриваем решение. Работает не всегда — но когда работает, проще и быстрее динамики.
Time and Space Complexityактуально
Асимптотическая сложностьСпособ сравнить алгоритмы, не запуская их: как растёт время работы с ростом входа. Отбрасывает константы и оставляет то, что решает на больших данных.
Recursion and Divide and Conquerактуально
Рекурсия и разделяй-и-властвуйЗадача сводится к таким же задачам меньшего размера. Основа сортировки слиянием, быстрой сортировки, обхода деревьев и почти всей динамики.
Numerical Methodsактуально
Численные методыиз «Основы»Компьютер считает приближённо. Понимание точности float, устойчивости и обусловленности спасает от NaN и «необъяснимых» расхождений.
Hash Tablesактуально
Хеш-таблицыДоступ по ключу за константу в среднем. Основа словарей и множеств — и структура, на которой держится большая часть повседневного кода.
Arrays, Lists, Stacks and Queuesактуально
Массивы, списки, стеки и очередиЧетыре базовых способа хранить последовательность. Отличаются не тем, что умеют, а тем, что у них дёшево, а что дорого.
Trees and Heapsактуально
Деревья и кучиИерархические структуры, дающие логарифмические операции: двоичное дерево поиска для упорядоченных запросов, куча — для быстрого минимума.
Partitioningактуально
Партиционированиеиз «Инженерия данных»Разделение данных по ключу (обычно по дате), чтобы запрос читал минимум файлов.
Cachingактуально
Кешированиеиз «Системный дизайн ML-сервисов»Не считать то, что уже посчитано: кеш предсказаний, признаков и эмбеддингов.
Sorting Algorithmsактуально
СортировкиБыстрая, слиянием, пирамидальная — три способа упорядочить данные за O(n log n) с разными свойствами по памяти, устойчивости и худшему случаю.
String Algorithmsактуально
Алгоритмы на строкахПоиск подстроки, сравнение и индексация текста за линейное время вместо квадратичного перебора.
Order Statisticsактуально
Порядковые статистикиНайти k-й по величине элемент, не сортируя весь массив. Quickselect делает это в среднем за линию.
Graph Traversalактуально
Обходы графа: семейство2 темы внутриЗонтичная тема: что общего у обоих обходов, как увидеть граф в задаче, где он не назван, и по каким двум вопросам выбирается обход. Сами обходы разобраны отдельно.
Breadth-First Searchактуально
Поиск в ширинувнутри «Обходы графа: семейство»Обход слоями: сначала всё, до чего один шаг, потом — два. Первое посещение вершины оказывается кратчайшим путём, если все переходы равноценны.
Depth-First Searchактуально
Поиск в глубинувнутри «Обходы графа: семейство»Идти вглубь до упора и возвращаться. Порядок завершения вершин даёт топологическую сортировку, три цвета — обнаружение циклов, откат состояния — перебор с возвратом.
Shortest Pathsактуально
Кратчайшие путиДейкстра для неотрицательных весов, Беллман — Форд для отрицательных, A* — когда есть оценка расстояния до цели.
Graph Basicsактуально
Основы графовиз «Графы и сети»Вершины, рёбра, веса и направления. Матрица смежности и список рёбер — два способа хранить одно и то же.
4 тем показаны здесь из других глав — они подходят по смыслу и открываются в своей главе.