Задачник Базовый курс EN

Как устроен

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

Статьи

DS Структура данных Связный список Узлы со ссылками на соседей: вставка и удаление у известного узла за O(1), путь к k-му — k шагов. O(1) у известного узла 2 задачи STR Алгоритм Алгоритм Манакера Все палиндромы строки за O(n): зеркало внутри самого правого палиндрома; фаги и палиндромы в их ДНК. O(n) 2 задачи DP Приём Convex hull trick Минимум прямых вместо перебора: 1776 тестов каталога по запускам песочницы — и квадратичная динамика становится линейной. O(n) 2 задачи GEO Приём Вращающиеся калиперы У 971 из 2679 кварталов центра Алматы наименьший прямоугольник повёрнут на 4–8°: сетка улиц смотрит не строго на север. O(n) после оболочки, O(n log n) с ней 2 задачи SYS Алгоритм Ограничение частоты запросов Не больше N запросов в единицу времени: окно, журнал, два счётчика и ведро с токенами. O(1) на запрос (журнал — O(N)) 2 задачи SYS Структура данных Инвертированный индекс и BM25 Словарь «слово → документы, где оно есть»: запрос читает несколько коротких списков вместо всех текстов. O(сумма длин списков слов запроса); «И» галопом — O(m·log(n/m)) 2 задачи TEC Приём Два указателя Два индекса движутся только вперёд и заменяют перебор пар или отрезков одним проходом за O(n). O(n) 2 задачи TEC Приём Скользящее окно Окно ширины w ползёт по данным: ответ правится по входящему и уходящему элементу за O(1) вместо O(w). O(n) 2 задачи

Задачи

Два ограничителя Слова без повторов Сушь Толчки рядом во времени Три класса глубины Квадраты фон Неймана Параллельные пары Самая далёкая пара

Часто рядом

собеседования 5 классика 4 олимпиады 3 массив 2 оптимизация 2 потоковая обработка 2 в проде 2 скользящее окно 2 наука и физика 2 связный список 1 редакторы текста 1 кэширование 1