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

Где встречается

операционные системы

Статьи

SRT Алгоритм Пирамидальная сортировка Куча прямо в массиве: n log n в худшем случае без лишней памяти — страховка introsort и сортировка ядра Linux. O(n log n) 2 задачи DS Структура данных Связный список Узлы со ссылками на соседей: вставка и удаление у известного узла за O(1), путь к k-му — k шагов. O(1) у известного узла 2 задачи DS Структура данных Двоичная куча Минимум под рукой, добавление и извлечение за O(log n): дерево в массиве, на котором живут календари событий. O(log n) 2 задачи DS Структура данных АВЛ-дерево Дерево поиска, где высоты веток у узла различаются не больше чем на 1: высота до ~1,44·log₂ n. O(log n) на поиск, вставку и удаление 2 задачи DS Структура данных Красно-чёрное дерево Дерево поиска с узлами двух цветов: высота до 2·log₂(n + 1), не больше трёх поворотов на операцию. O(log n) на поиск, вставку и удаление 2 задачи DS Структура данных LRU-кэш Словарь плюс двусвязный список: get и put за O(1), выселяется тот, к кому дольше всех не обращались. O(1) на get и put 2 задачи STR Алгоритм Бойер — Мур Сравнивает справа налево и перепрыгивает буквы: на длинных образцах читает лишь малую часть текста. O(n + m) 2 задачи SYS Алгоритм Планирование задач Порядок работы: короткие сначала, сроки, прерывания, много ядер и аномалии Грэма. O(n log n): сортировка или куча 2 задачи SYS Алгоритм LFU и ARC Кэши, которые помнят частоту: LFU за O(1) на корзинах счётчиков и ARC, который сам делит места между свежими и частыми. O(1) на запрос у обоих 2 задачи TEC Приём Битовые трюки Число как набор флажков: маски, младшая единица, подсчёт единиц и перебор подмножеств без рекурсии. O(1) на операцию над словом 1 задача

Задачи

Права доступа Кратчайший остаток

Часто рядом

собеседования 8 классика 7 в проде 7 дерево 4 куча 3 массив 3 связный список 3 кэширование 3 редакторы текста 2 расписание 2 дерево поиска 2 поиск 2