Порядок установки зависимостей
Условие
Объект «пакет → массив его зависимостей». Верни порядок установки, при котором каждая зависимость ставится раньше зависящего от неё пакета. При выборе из нескольких доступных бери тот, что раньше в порядке ключей. Циклическая зависимость - пустой массив.
Что проверяют тесты
порядок установки
вход не мутируется
цикл даёт пустой массив
без зависимостей
пустой вход
Как подойти
Задача, с которой начинается любой менеджер пакетов и любая система сборки. Реализация здесь наивная, O(n²), но читаемая и детерминированная; алгоритм Кана со счётчиком входящих степеней даёт O(V+E). Главное требование, которое легко нарушить, - не мутировать входной объект: в исходном решении из сборника зависимости удалялись прямо из аргумента, и повторный вызов возвращал пустой массив.
Подсказки: 3
- Это топологическая сортировка: бери пакет без незакрытых зависимостей.
- После установки вычёркивай пакет из списков остальных.
- Если доступных нет, а пакеты остались - в графе цикл.
Решите в тренажёре
Редактор с автотестами прямо в браузере. Можно решить спокойно, вслух или под таймером, как на собесе.