Задачник Базовый курс EN

На чём держится

скетч

Статьи

DS Структура данных Фильтр Блума Отвечает «точно нет» или «возможно, да» о членстве в множестве, тратя около 10 бит на элемент. O(k) 2 задачи SYS Структура данных Count-Min Sketch Частоты элементов потока в фиксированной памяти: минимум из d счётчиков, ошибка только вверх. O(d) на элемент и на запрос 2 задачи SYS Структура данных HyperLogLog Число разных элементов потока в килобайте памяти: длинные серии нулей в хешах и среднее по регистрам. O(1) на элемент, O(m) на оценку 2 задачи SYS Алгоритм MinHash и LSH Подпись из K минимумов хешей: доля совпавших — оценка сходства Жаккара; полосы LSH сводят похожие пары в одни корзины. O(K·S) на подписи, O(n·b) на корзины, плюс проверка кандидатов 2 задачи

Задачи

Оценка по хешам Две оценки Слова в главах

Часто рядом

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