В данном репозитории собраны решённые задачи с курса по Алгоритмам (Yandex.Practicum).
К каждой проектной задаче было написано подробное объяснение принципа работы, доказательство корректности, оценка временной и пространственной сложности. Также к каждой задаче были написанны собственные тесты.
- Поисковая система — дан массив документов и массив запросов, нужно найти для каждого запроса пять самых релевантных документов.
- Хеш-таблица — дан массив команд get, put, delete, все операции должны выполняться за O(1) в среднем. Коллизии были решены методом открытой адресации.
- Дорогая сеть — дан взвешенный граф, нужно узнать вес максимального остовного дерева, либо вывести ошибку.
- Железные дороги — дан граф из дорог двух типов R и B, из города с меньшим индексом можно добраться только в город с большим индексом и только используя один тип дорог, то-есть нельзя перемещаться из города A в город C дорогой R, а потом из города C в город H дорогой B. Нужно определить оптимальна ли карта или нет, оптимальной карта называется, если не существует пары городов A и B такой, что от A до B можно добраться как по дорогам типа R, так и по дорогам типа B.
- Расстояние по Левенштейну — дано две строки, нужно определить сколько между ними атомарных изменений.