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

Как устроен

скользящее окно

Статьи

DS Структура данных АВЛ-дерево Дерево поиска, где высоты веток у узла различаются не больше чем на 1: высота до ~1,44·log₂ n. O(log n) на поиск, вставку и удаление 2 задачи STR Алгоритм Алгоритм Рабина — Карпа Хеш окна катится по тексту, буквы сравниваются только при совпадении хеша; тысячи образцов — за один проход. O(n + m) в среднем 1 задача STR Алгоритм LZ77 и LZW Повторы — ссылками назад (LZ77) или номерами фраз растущего словаря (LZW); хеш-цепочки, уровни, окно. O(n · chain) 2 задачи SYS Алгоритм Алгоритм rsync Передаёт только изменённые куски файла: суммы блоков туда, новые байты обратно; блоки находятся на любом смещении.

O(n + m): сумма окна сдвигается за O(1), сильная сумма — только при совпадении слабой

2 задачи TEC Приём Два указателя Два индекса движутся только вперёд и заменяют перебор пар или отрезков одним проходом за O(n). O(n) 2 задачи TEC Приём Скользящее окно Окно ширины w ползёт по данным: ответ правится по входящему и уходящему элементу за O(1) вместо O(w). O(n) 2 задачи

Задачи

Не больше R оповещений Повороты на конвейере Слова без повторов Словарное разнообразие Старые блоки в новом файле Сушь Медиана за окно Самое сильное за месяц Фраза k раз

Часто рядом

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