хеш-таблица

Статьи

DS Структура данных Хеш-таблица Поиск, вставка и удаление по ключу в среднем за O(1): ключ превращается в номер ячейки массива. O(1) в среднем 2 задачи DS Структура данных LRU-кэш Словарь плюс двусвязный список: get и put за O(1), выселяется тот, к кому дольше всех не обращались. O(1) на get и put 2 задачи GRA Приём Как хранить граф Матрица, списки, массив рёбер и CSR: память, скорость и какие вопросы каждая запись задаёт дёшево.

соседи вершины: O(n) у матрицы, O(deg) у списков и CSR; есть ли ребро: O(1) у матрицы, O(deg) у списков

2 задачи SYS Структура данных CRDT Данные, копии которых правят независимо и сливают в любом порядке: счётчики, множества, текст.

O(1) на операцию у счётчика и множества; вставка в текст — O(1) в среднем

2 задачи SYS Алгоритм LFU и ARC Кэши, которые помнят частоту: LFU за O(1) на корзинах счётчиков и ARC, который сам делит места между свежими и частыми. O(1) на запрос у обоих 2 задачи TEC Приём Скользящее окно Окно ширины w ползёт по данным: ответ правится по входящему и уходящему элементу за O(1) вместо O(w). O(n) 2 задачи TEC Приём Мемоизация Запомнить ответ функции для каждого набора аргументов, чтобы не считать его заново: экспонента превращается в многочлен. O(число разных аргументов × работа на один вызов) 2 задачи TEC Приём Амортизационный анализ Оценка всей последовательности операций, а не каждой: суммой, монетами и потенциалом — и где она не спасает. оценка на последовательность 2 задачи TEC Приём Как выбрать структуру данных Сначала список операций, потом структура: стоимость каждой операции в Python и Go на одной карте. зависит от выбора 1 задача TEC Приём Сколько займёт в памяти Байты на запись — и сразу видно, поместится ли миллиард: из чего складывается вес данных в Python и Go. прикидка — байты на запись × число записей 1 задача

Задачи

Две книги на сертификат Есть ли такой участок Анаграммы Толстого Заказы по сроку Кэш страниц Очередь на выселение LFU Пары из корзин Распаковать LZW Ровно ноль градусов Самая длинная цепочка Коллатца Самые частые слова Слияние с надгробиями Слова без повторов Словарное разнообразие Список покупок на двоих Текст без пробелов Частые слова за один проход Шторм повторов Два частотных словаря Кольцо из кусков Повторить ARC Похожие пароли Слить правки без сервера Словарь двух томов Треугольники импортов Пятнашки за наименьшее число ходов

Часто рядом

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