15 вопросов
Асимптотическая верхняя граница роста времени/памяти от размера ввода. O(1) - константа; O(n) - линейная; O(n^2) - квадратичная; O(log n) - логарифм; O(n log n) - сортировка. Игнорируем константы и младшие члены.
Массив бакетов; ключ хешируется в индекс. Коллизии: chaining (список в бакете) или open addressing. В среднем O(1) для вставки и поиска. Load factor влияет на производительность.
B-tree - сбалансированное дерево, порядок обхода, диапазонные запросы, используется в БД для индексов. HashMap - константный доступ по ключу, нет порядка, не для диапазонов. Выбор по сценарию.
Вставка/удаление в середине O(1) при известном узле; не нужна непрерывная память. Минусы: нет индекса по позиции (доступ O(n)), больше накладных расходов на указатели. Single/double linked.
Стек - LIFO, push/pop. Очередь - FIFO, enqueue/dequeue. Реализация массивом или списком. Применение: стек для вызовов и обхода, очередь для BFS и задач.
Дерево: левый потомок меньше узла, правый больше. Поиск, вставка, удаление в среднем O(log n). Несбалансированное дерево может выродиться в список - нужны AVL, красно-черные.
Полное бинарное дерево: родитель не меньше (max-heap) или не больше (min-heap) потомков. Хранение в массиве. Извлечение минимума/максимума O(log n). Используется для приоритетной очереди, heapsort.
BFS - обход в ширину (очередь), кратчайший путь в невзвешенном графе. DFS - в глубину (стек/рекурсия), топологическая сортировка, поиск циклов. Выбор по задаче.
Когда задача естественно сводится к той же подзадаче (дерево, разбиение). Базовый случай и рекурсивный шаг. Минусы: стек вызовов, риск переполнения. Хвостовая рекурсия может оптимизироваться в цикл.
QuickSort, MergeSort - O(n log n). BubbleSort, InsertionSort - O(n^2), для малых n. CountingSort, RadixSort - линейные при ограничениях на данные. Стабильность и in-place важны по задаче.
Поиск в отсортированном массиве за O(log n): сравнение с серединой, сужение диапазона. Варианты: lower_bound, upper_bound. Применение: поиск вставки, поиск в ответах (бинарный поиск по ответу).
Разбиение на перекрывающиеся подзадачи; сохранение результатов (мемоизация или таблица). Оптимальная подструктура и перекрывающиеся подзадачи. Примеры: Fibonacci, рюкзак, LCS, кратчайший путь.
HashMap для доступа по ключу + двусвязный список по порядку использования. При доступе - переместить в голову; при переполнении - удалить хвост. Операции O(1). Альтернатива: LinkedHashMap в Java.
Вероятностная структура: проверка "элемент точно не в множестве" или "возможно в множестве". Ложных отрицаний нет; возможны ложные срабатывания. Экономия памяти. Применение: кеш-промахи, дубликаты.
Фиксированное окно, скользящее окно, token bucket, leaky bucket. Счетчики в памяти или Redis. Выбор по требованию к гладкости и точности. Распределенный вариант - с центральным хранилищем или с допуском.