поисковики

Статьи

SRT Алгоритм Экспоненциальный поиск Шаги 1, 2, 4, 8, … пока не перескочишь, потом двоичный поиск: когда граница неизвестна или ответ близко. 2⌊log₂ i⌋ + 1 вопрос до позиции i 1 задача SRT Алгоритм Top-k: k лучших Куча из k с худшим наверху: поток читается один раз, почти каждый элемент отсеивается одним сравнением. O(n log k) 2 задачи DS Структура данных Бор (префиксное дерево) Слова с общим началом идут общим путём: поиск слова и всех продолжений — за длину запроса. O(L) на вставку и поиск слова длины L 2 задачи GRA Алгоритм PageRank Важность страниц по ссылкам: случайный читатель, степенной метод и коэффициент затухания. O((V + E) · log(1/ε) / log(1/d)) 1 задача STR Структура данных Суффиксный массив Отсортированные хвосты текста: поиск двоичным поиском, повторы и число разных кусков по соседям. O(n log n) 2 задачи STR Алгоритм Преобразование Барроуза — Уилера Перестановка, которая сжимает текст и служит по нему указателем: обратный поиск, LF и выравнивание ридов. O(m) на подсчёт образца, O(m + k·s) на k мест 2 задачи STR Алгоритм Редакционное расстояние Наименьшее число вставок, удалений и замен между двумя строками — таблица m × n и выравнивание по ней. O(m · n) 2 задачи GEO Приём Кривые Гильберта и geohash Пронумеровать плоскость так, чтобы соседи на карте стояли рядом в одномерном индексе: Z-порядок, geohash, Гильберт. O(k) на номер 1 задача SYS Структура данных Инвертированный индекс и BM25 Словарь «слово → документы, где оно есть»: запрос читает несколько коротких списков вместо всех текстов. O(сумма длин списков слов запроса); «И» галопом — O(m·log(n/m)) 2 задачи SYS Алгоритм MinHash и LSH Подпись из K минимумов хешей: доля совпавших — оценка сходства Жаккара; полосы LSH сводят похожие пары в одни корзины. O(K·S) на подписи, O(n·b) на корзины, плюс проверка кандидатов 2 задачи ML Алгоритм Наивный Байес Считает, как часто каждый признак встречается в каждом классе, и складывает логарифмы этих частот. O(N) обучение, O(L·m) ответ 2 задачи

Задачи

Лучшие абзацы Подсказки по роману Сжатый список вхождений Что читать дальше В одном предложении Словарь опечаток

Часто рядом

собеседования 6 в проде 6 сжатие 5 классика 5 поиск 3 двоичный поиск 3 базы данных 3 поиск в тексте 3 биоинформатика 3 потоковая обработка 2 ранжирование 2 матрица 2