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

Что решает

частоты

Статьи

SRT Алгоритм Top-k: k лучших Куча из k с худшим наверху: поток читается один раз, почти каждый элемент отсеивается одним сравнением. O(n log k) 2 задачи DS Структура данных Хеш-таблица Поиск, вставка и удаление по ключу в среднем за O(1): ключ превращается в номер ячейки массива. O(1) в среднем 2 задачи DS Структура данных Дерево Фенвика Суммы на префиксе с изменениями за O(log n) в одном массиве: блоки длиной в младшую единицу номера. O(log n) на сумму префикса и на изменение 2 задачи STR Алгоритм Код Хаффмана Оптимальный префиксный код по частотам знаков: два самых редких дерева склеиваются, пока не останется одно. O(n log n) 2 задачи SYS Структура данных Count-Min Sketch Частоты элементов потока в фиксированной памяти: минимум из d счётчиков, ошибка только вверх. O(d) на элемент и на запрос 2 задачи

Задачи

Анаграммы Толстого Две оценки Подсказки по роману Самые частые слова Сколько бит займёт текст Частые слова за один проход Подарок к покупке Топ по частям

Часто рядом

в проде 4 собеседования 3 классика 3 куча 2 потоковая обработка 2 базы данных 2 хеширование 2 массив 2 сжатие 2 k-я статистика 1 ближайший сосед 1 распределённость 1