Структуры данных
Выбирать стек, очередь, дерево, кучу и структуру диапазонных запросов по операциям.
Объяснения и разобранные примеры
Как битовая маска хранит несколько независимых флагов
битовая маска хранит несколько независимых флагов. Каждому независимому флагу назначают отдельную степень двойки.
Когда нужен стек, а когда очередь
Когда нужен стек, а когда очередь. Стек извлекает последний добавленный элемент первым: LIFO.
Как порядок поддеревьев определяет поиск в бинарном дереве
порядок поддеревьев определяет поиск в бинарном дереве. В бинарном дереве поиска ключи каждого левого поддерева меньше ключа узла, а правого — больше, если рассматриваются уникальные ключи.
Как две отметки задают прибавку на целом диапазоне
две отметки задают прибавку на целом диапазоне. Разностный массив хранит изменение между соседними значениями.
Почему двоичная куча выдаёт минимум без полной сортировки
Почему двоичная куча выдаёт минимум без полной сортировки. В минимальной двоичной куче значение родителя не больше значений его детей.
Как монотонный стек находит следующий больший элемент
монотонный стек находит следующий больший элемент. Монотонный стек позволяет находить следующий строго больший элемент справа за один проход.
Как префиксные суммы отвечают на запрос отрезка двумя значениями
префиксные суммы отвечают на запрос отрезка двумя значениями. Префиксная сумма P(k) хранит сумму первых k элементов, причём P(0)=0.
Как обновить сумму окна, не пересчитывая все элементы
обновить сумму окна, не пересчитывая все элементы. Если окно фиксированной длины сдвинуть на одну позицию, из него уйдёт один элемент и придёт один новый.
Как префиксное дерево различает общее начало и целое слово
префиксное дерево различает общее начало и целое слово. В префиксном дереве рёбра помечены символами, а путь от корня задаёт прочитанное начало строки.
Когда упорядоченность позволяет двигать два указателя навстречу
Когда упорядоченность позволяет двигать два указателя навстречу. Для поиска пары в упорядоченном массиве можно поставить указатели на его концы.
Фильтр Блума: возможное совпадение и невозможность обычного удаления
Фильтр Блума: возможное совпадение и невозможность обычного удаления. Фильтр Блума помечает несколько позиций битового массива для каждого добавленного элемента.
Дерево Фенвика: обновления и префиксные суммы по битам индекса
Дерево Фенвика: обновления и префиксные суммы по битам индекса. Дерево Фенвика хранит специально выбранные суммы блоков и поддерживает добавление к одному элементу вместе с запросом префиксной суммы за логарифмическое число шагов.
LFU: частота обращений и правило разрешения равенства
LFU: частота обращений и правило разрешения равенства. LFU вытесняет наименее часто использованный элемент среди находящихся в кэше.
LRU: как последнее обращение меняет следующего кандидата на удаление
LRU: как последнее обращение меняет следующего кандидата на удаление. LRU вытесняет элемент, к которому дольше всего не обращались среди находящихся в кэше.
Таблица минимумов: почему перекрытие блоков допустимо не всегда
Таблица минимумов: почему перекрытие блоков допустимо не всегда. Sparse Table заранее хранит ответы для блоков длины 1,2,4,8 и так далее.
Представление словаря и снимок: какие изменения будут видны
Различаем динамические keys, values, items и сохранённый список пар, выбираем безопасный обход при удалении ключей и проверяем поверхностность снимка.
Обратный словарь: почему одинаковые значения теряют записи
Проверяем возможность однозначно обратить соответствие, прослеживаем замену при повторном ключе и строим группы исходных ключей для неуникальных значений.
Кортеж: неизменные места могут содержать изменяемый список
Различаем создание одноэлементного кортежа, замену его элемента и изменение вложенного объекта; предсказываем результат операций без смешения двух уровней.
Класс и экземпляр: почему две карточки хранят разные данные
Создаём два экземпляра одного класса, прослеживаем инициализацию self.attr и отличаем новое создание объекта от второго имени прежнего экземпляра.
Атрибут класса и поле экземпляра: присваивание может скрыть общее значение
Прослеживаем поиск обычного атрибута у экземпляра и класса, различаем общее значение, локальное скрытие и мутацию общего списка, проверяем удаление скрывающего поля.
remove, pop и del: удаляем значение или место
Выбираем удаление из списка по значению или индексу, прослеживаем первый повтор, возвращённый элемент и изменение последующих индексов, различаем ошибки отсутствия.
Сравнение кортежей: решает первое различие, а не все координаты
Прослеживаем лексикографический порядок последовательностей, сравниваем общий префикс и связываем порядок полей составного ключа с главным критерием.
Объединение HyperLogLog сливает регистры, а не складывает оценки
Объяснить идемпотентное объединение совместимых HyperLogLog-эскизов по покоординатному максимуму и границы оценки мощности пересекающихся множеств.
Частые вопросы
Как работать с темой «Структуры данных»?
Выберите объяснение из списка, восстановите ход примера своими словами и ответьте на проверочный вопрос. Если к теме подключён инструмент, им можно проверить свои данные.
Можно ли вернуться к более простой теме?
Да. Откройте учебную карту или ссылки на необходимые основы перед списком материалов. Уровень по классу помогает выбрать сложность и не ограничивает доступ.