собеседования

SRT Алгоритм Двоичный поиск Находит границу «нет → да» в упорядоченных данных за log₂ n проверок. O(log n) 2 задачи SRT Приём Двоичный поиск по ответу Если проверить ответ легче, чем найти, и проверка монотонна, — ищем ответ делением пополам. O(log D · стоимость проверки) 2 задачи SRT Алгоритм Экспоненциальный поиск Шаги 1, 2, 4, 8, … пока не перескочишь, потом двоичный поиск: когда граница неизвестна или ответ близко. 2⌊log₂ i⌋ + 1 вопрос до позиции i 1 задача SRT Алгоритм Интерполяционный поиск Прикинуть место по значениям на краях: log log n проб на равномерных ключах и до n — на неудобных. ≈ log₂ log₂ n в среднем, n в худшем 1 задача SRT Алгоритм Простые сортировки Вставки, выбор и пузырёк: квадратичные, но вставки работают внутри библиотечных сортировок. O(n²) 2 задачи SRT Алгоритм Сортировка слиянием Делит пополам, сортирует половины и сливает: n log n на любом входе, устойчиво, годится для внешней памяти. O(n log n) 2 задачи SRT Алгоритм Быстрая сортировка Разбиение вокруг опорного: в среднем n log n на месте, в худшем n² — и как от худшего защищаются. O(n log n) 2 задачи SRT Алгоритм Пирамидальная сортировка Куча прямо в массиве: n log n в худшем случае без лишней памяти — страховка introsort и сортировка ядра Linux. O(n log n) 2 задачи SRT Алгоритм Сортировка подсчётом и поразрядная Без сравнений: посчитать ключи или разложить их по цифрам — O(n + k) и O(d·n) вместо n log n. O(n + k) и O(d·(n + b)) 2 задачи SRT Приём Нижние границы сравнений Почему нельзя быстрее: подсчёт исходов и игра против судьи; сортировка, второй в турнире, минимум с максимумом, слияние. сортировка — ⌈log₂ n!⌉ сравнений 1 задача SRT Алгоритм Быстрый выбор k-й по величине без сортировки: разбиение и одна ветка вместо двух — O(n) в среднем, медиана медиан — всегда. O(n) в среднем 1 задача SRT Алгоритм Top-k: k лучших Куча из k с худшим наверху: поток читается один раз, почти каждый элемент отсеивается одним сравнением. O(n log k) 2 задачи SRT Алгоритм Перемешивание Фишера — Йетса Честная случайная перестановка за O(n): каждая из n! — с вероятностью 1/n!, и почему «обмен с любым» нечестен. O(n) 2 задачи DS Структура данных Динамический массив Массив, который растёт сам: доступ по индексу за O(1), добавление в конец — за O(1) амортизированно. O(1) амортизированно на append 2 задачи DS Структура данных Связный список Узлы со ссылками на соседей: вставка и удаление у известного узла за O(1), путь к k-му — k шагов. O(1) у известного узла 2 задачи DS Структура данных Стек и очередь Стек: последним пришёл — первым ушёл. Очередь: первым пришёл — первым ушёл. Каждая операция — O(1). O(1) на push и pop, enqueue и dequeue 2 задачи DS Приём Монотонный стек Стек с упорядоченными значениями: ближайший больший элемент и наибольший прямоугольник за O(n). O(n) 2 задачи DS Структура данных Хеш-таблица Поиск, вставка и удаление по ключу в среднем за O(1): ключ превращается в номер ячейки массива. O(1) в среднем 2 задачи DS Структура данных Фильтр Блума Отвечает «точно нет» или «возможно, да» о членстве в множестве, тратя около 10 бит на элемент. O(k) 2 задачи DS Структура данных Двоичная куча Минимум под рукой, добавление и извлечение за O(log n): дерево в массиве, на котором живут календари событий. O(log n) 2 задачи DS Структура данных Двоичное дерево поиска Меньшие налево, большие направо: поиск, порядок и k-й элемент за высоту дерева — от log n до n. O(h): от O(log n) до O(n) 2 задачи DS Структура данных АВЛ-дерево Дерево поиска, где высоты веток у узла различаются не больше чем на 1: высота до ~1,44·log₂ n. O(log n) на поиск, вставку и удаление 2 задачи DS Структура данных Красно-чёрное дерево Дерево поиска с узлами двух цветов: высота до 2·log₂(n + 1), не больше трёх поворотов на операцию. O(log n) на поиск, вставку и удаление 2 задачи DS Структура данных Декартово дерево Ключ и случайный приоритет: глубина O(log n) в среднем, split и merge, массив с разворотом куска за O(log n). O(log n) в среднем на поиск, вставку, удаление, split и merge 1 задача DS Структура данных Список с пропусками Связный список с экспресс-линиями по броскам монетки: поиск и вставка за O(log n) в среднем, без поворотов. O(log n) в среднем на поиск, вставку, удаление и ранг 1 задача DS Структура данных Бор (префиксное дерево) Слова с общим началом идут общим путём: поиск слова и всех продолжений — за длину запроса. O(L) на вставку и поиск слова длины L 2 задачи DS Структура данных LRU-кэш Словарь плюс двусвязный список: get и put за O(1), выселяется тот, к кому дольше всех не обращались. O(1) на get и put 2 задачи GRA Приём Как хранить граф Матрица, списки, массив рёбер и CSR: память, скорость и какие вопросы каждая запись задаёт дёшево. соседи вершины: O(n) у матрицы, O(deg) у списков и CSR; есть ли ребро: O(1) у матрицы, O(deg) у списков 2 задачи GRA Алгоритм Поиск в ширину Обходит граф слоями и находит пути с наименьшим числом рёбер за O(V + E). O(V + E) 2 задачи GRA Алгоритм Поиск в глубину Идёт вглубь, отмечает вход и выход каждой вершины и по ним находит циклы за O(V + E). O(V + E) 2 задачи GRA Алгоритм Топологическая сортировка Выстраивает вершины графа без циклов так, чтобы все рёбра смотрели вперёд, за O(V + E). O(V + E) 2 задачи GRA Алгоритм Компоненты сильной связности Группы вершин, где из любой можно дойти до любой: Тарьян за один обход, Косараю за два, O(V + E). O(V + E) 2 задачи GRA Алгоритм Мосты и точки сочленения Улицы и перекрёстки, без которых граф распадается: один поиск в глубину с числами tin и low, O(V + E). O(V + E) 2 задачи GRA Алгоритм Алгоритм Дейкстры Кратчайшие пути от одной вершины во взвешенном графе без отрицательных рёбер. O((V + E) log V) 3 задачи GRA Алгоритм A* Дейкстра с подсказкой «сколько ещё до финиша»: волна тянется к цели, а путь остаётся кратчайшим. O((V + E) log V) 2 задачи GRA Алгоритм Двунаправленный поиск Две волны Дейкстры навстречу друг другу: где остановиться, сколько экономится и как подружить с A*. O((V + E) log V) 2 задачи GRA Алгоритм Алгоритм Беллмана — Форда Кратчайшие пути с отрицательными рёбрами и поиск отрицательного цикла: V раундов по всем рёбрам. O(V · E) 2 задачи GRA Алгоритм Алгоритм Флойда — Уоршелла Кратчайшие пути между всеми парами вершин за O(n³): динамика по разрешённым пересадкам. O(n³) 2 задачи GRA Алгоритм Паросочетания в двудольном графе Наибольшее число пар в двудольном графе: Кун, Хопкрофт — Карп, теоремы Кёнига и Холла. O(E √V) 2 задачи STR Алгоритм Наивный поиск подстроки Образец прикладывают к каждой позиции текста: n · m сравнений в худшем случае, около n — на обычном тексте. O(n · m) 2 задачи STR Алгоритм Префикс-функция и КМП Все вхождения образца за O(n + m) без шагов назад по тексту; префикс-функция находит и период строки. O(n + m) 2 задачи STR Алгоритм Алгоритм Рабина — Карпа Хеш окна катится по тексту, буквы сравниваются только при совпадении хеша; тысячи образцов — за один проход. O(n + m) в среднем 1 задача STR Алгоритм Редакционное расстояние Наименьшее число вставок, удалений и замен между двумя строками — таблица m × n и выравнивание по ней. O(m · n) 2 задачи STR Алгоритм Код Хаффмана Оптимальный префиксный код по частотам знаков: два самых редких дерева склеиваются, пока не останется одно. O(n log n) 2 задачи DP Приём Динамическое программирование Сводим задачу к подзадачам, решаем каждую один раз и храним ответы в таблице. состояния × переходы 2 задачи DP Алгоритм Задача о рюкзаке Лучший набор вещей под ограничение по весу: таблица n × W и путь по ней назад. O(n·W) 3 задачи DP Алгоритм Наибольшая возрастающая подпоследовательность Самая длинная растущая цепочка элементов в исходном порядке: пасьянс и двоичный поиск за n log n. O(n log n) 2 задачи DP Алгоритм Наибольшая общая подпоследовательность Самая длинная цепочка, общая двум последовательностям: таблица m × n, путь назад, Хиршберг. O(m · n) 2 задачи PAR Приём Жадные алгоритмы Лучший шаг сейчас без оглядки назад: когда это оптимально, когда почти, и как это доказать. обычно O(n log n): сортировка или куча 2 задачи PAR Приём Перебор с возвратом Строить решение по шагу, сразу проверять и отступать из тупика: судоку, ферзи, раскраски. O(bᵈ) в худшем случае 2 задачи PAR Приём Разделяй и властвуй Разрезать, решить части так же, склеить; сколько это стоит — по уровням дерева рекурсии и основной теореме. T(n) = a·T(n/b) + f(n) 2 задачи PAR Алгоритм Ближайшая пара точек Две ближайшие точки из n за n log n: разрез, полоса шириной 2d и семь соседей; сеткой — за n в среднем. O(n log n) 2 задачи PAR Приём Встреча посередине Перебрать две половины по отдельности и встретиться в отсортированной таблице: 2·2^(n/2) шагов вместо 2ⁿ. O(2^(n/2) · n) 2 задачи NUM Алгоритм Алгоритм Евклида Наибольший общий делитель двух чисел за O(log n) делений с остатком. O(log min(a, b)) 2 задачи NUM Алгоритм Быстрое возведение в степень aⁿ за O(log n) умножений: квадраты по битам показателя. O(log n) умножений 2 задачи GEO Приём Векторы и ориентация Знак векторного произведения — поворот налево или направо; на нём стоит почти вся вычислительная геометрия. O(1) на один поворот 2 задачи GEO Алгоритм Пересечение отрезков Где встречаются два отрезка — точно, в дробях; и как найти все встречи среди тысяч отрезков без перебора пар. O(1) на пару; O(n²) перебором для n отрезков 2 задачи GEO Алгоритм Точка в многоугольнике Луч из точки пересекает границу нечётное число раз — точка внутри; число оборотов — то же со знаками. O(n) на точку 2 задачи NUM~ Алгоритм Бисекция и метод Ньютона Корень уравнения: деление отрезка пополам надёжно, касательные Ньютона — быстро. бисекция — log₂((b − a)/ε) шагов; Ньютон — около log₂ от числа знаков 2 задачи NUM~ Алгоритм Градиентный спуск Ищет минимум функции шагами против градиента — в сторону самого крутого спуска. O(κ · log(1/ε)) шагов 2 задачи SYS Алгоритм Консистентное хеширование Распределяет ключи по серверам так, что при добавлении сервера переезжает лишь его доля. O(log(N·v)) на поиск сервера 1 задача SYS Алгоритм Рандеву-хеширование Каждый ключ уходит к серверу с наибольшим хешем пары «ключ, сервер»: равномерно, без таблиц, отказ сдвигает только ключи упавшего. O(N) на ключ 2 задачи SYS Алгоритм Резервуарная выборка k случайных элементов из потока неизвестной длины за один проход и O(k) памяти. O(n) 2 задачи SYS Структура данных Дерево Меркла Хеши хешей: отпечаток всего набора, поиск расхождений за несколько сравнений и доказательство из log n хешей. O(n) на построение, O(log n) на доказательство и его проверку 2 задачи SYS Алгоритм Ограничение частоты запросов Не больше N запросов в единицу времени: окно, журнал, два счётчика и ведро с токенами. O(1) на запрос (журнал — O(N)) 2 задачи SYS Структура данных Инвертированный индекс и BM25 Словарь «слово → документы, где оно есть»: запрос читает несколько коротких списков вместо всех текстов. O(сумма длин списков слов запроса); «И» галопом — O(m·log(n/m)) 2 задачи SYS Структура данных LSM-дерево Записи копятся в памяти и ложатся на диск отсортированными прогонами; фоновые слияния держат число прогонов малым. запись O(1) амортизированно в памяти плюс O(L·T/B) на перезапись при слиянии; чтение — по прогону на уровень 2 задачи SYS Приём Повтор с джиттером Пауза перед повтором растёт вдвое и выбирается случайно: клиенты расходятся во времени и не бьют по серверу волнами. O(1) на решение о паузе 2 задачи SYS Алгоритм Raft Реплицированный журнал на ненадёжных серверах: лидер, сроки, большинство; выдерживает падение меньшей половины. один круг сообщений до большинства на запись 2 задачи SYS Алгоритм Часы Лэмпорта и векторные часы Логические часы: одно число Лэмпорта согласовано с «случилось раньше», вектор по процессам отличает «раньше» от «параллельно». O(1) на событие у Лэмпорта, O(n) у векторных 2 задачи SYS Алгоритм Два случайных выбора Спросить двух случайных и выбрать менее занятого: самая полная корзина — ln ln n вместо ln n / ln ln n. O(d) на решение: узнать нагрузку d серверов 2 задачи SYS Алгоритм LFU и ARC Кэши, которые помнят частоту: LFU за O(1) на корзинах счётчиков и ARC, который сам делит места между свежими и частыми. O(1) на запрос у обоих 2 задачи ML Алгоритм k-средних Делит точки на k групп так, чтобы точки были поближе к центру своей группы. O(n · k · d) за шаг 2 задачи ML Алгоритм DBSCAN Собирает в кластеры плотные области точек любой формы, а одинокие точки помечает как шум. O(n·Q + Σ|N(p)|) 2 задачи ML Алгоритм k ближайших соседей Отвечает так, как ответило большинство из k самых похожих известных примеров. O(n · d) на вопрос 2 задачи ML Алгоритм Решающее дерево Отвечает цепочкой вопросов «признак ≤ порог?»; каждый вопрос выбран так, чтобы неопределённость упала сильнее всего. O(h · F · n log n) построение; O(h) ответ 2 задачи ML Алгоритм Наивный Байес Считает, как часто каждый признак встречается в каждом классе, и складывает логарифмы этих частот. O(N) обучение, O(L·m) ответ 2 задачи ML Алгоритм Линейная регрессия Подбирает коэффициенты модели так, чтобы сумма квадратов промахов по данным была наименьшей. O(n·d² + d³) 2 задачи ML Алгоритм Логистическая регрессия Оценивает вероятность ответа «да»: взвешенная сумма признаков, пропущенная через сигмоиду. O(n·d² + d³) на шаг Ньютона 3 задачи ML Алгоритм Метод главных компонент Находит направления наибольшего разброса данных и описывает каждую точку немногими числами вдоль них. O(n·d² + d³) 2 задачи RND Приём Лас-Вегас и Монте-Карло Всегда верный, но иногда долгий против всегда быстрого, но иногда неверного — и как превратить одно в другое. O(k · стоимость одной попытки) 2 задачи TEC Приём O-большое Как растёт работа вместе с данными: O, Ω и Θ, правила оценки кода и где асимптотика обманывает. оценка — по тексту программы 1 задача TEC Приём Быстрый ввод и вывод Миллион чисел за десятки миллисекунд вместо секунды: чтение целиком, буфер и одна запись вывода. O(размер входа) 1 задача TEC Приём Как честно измерить скорость Повторы, прогрев, медиана и минимум, timeit и testing.Benchmark — и типичные способы обмануть себя замером. повторов столько, чтобы замер шёл хотя бы десятую долю секунды 1 задача TEC Приём Префиксные суммы Сумма любого отрезка за O(1) после одного прохода; двумерный вариант считает сумму любого прямоугольника картинки. O(n) на построение, O(1) на запрос 2 задачи TEC Приём Два указателя Два индекса движутся только вперёд и заменяют перебор пар или отрезков одним проходом за O(n). O(n) 2 задачи TEC Приём Сколько операций в секунду Шаги алгоритма, делённые на скорость языка, — и вы знаете, уложится ли программа, ещё до того, как её написали. оценка — секунды в уме 1 задача TEC Приём Сложность по замерам Рост времени по замерам: наклон, проверка отношением, экспоненты — и где замер врёт. O(B) на попытку 1 задача TEC Приём Скользящее окно Окно ширины w ползёт по данным: ответ правится по входящему и уходящему элементу за O(1) вместо O(w). O(n) 2 задачи TEC Приём Мемоизация Запомнить ответ функции для каждого набора аргументов, чтобы не считать его заново: экспонента превращается в многочлен. O(число разных аргументов × работа на один вызов) 2 задачи TEC Приём Числа, которые стоит знать Кэш, память, диск и сеть отличаются в сотни раз — прикидка по этим числам показывает, что ускорять. прикидка — минута на салфетке 1 задача TEC Приём Амортизационный анализ Оценка всей последовательности операций, а не каждой: суммой, монетами и потенциалом — и где она не спасает. оценка на последовательность 2 задачи TEC Приём Как выбрать структуру данных Сначала список операций, потом структура: стоимость каждой операции в Python и Go на одной карте. зависит от выбора 1 задача TEC Приём Битовые трюки Число как набор флажков: маски, младшая единица, подсчёт единиц и перебор подмножеств без рекурсии. O(1) на операцию над словом 1 задача