Порядок инициализации модулей и поиск цикла
Условие
Сервис состоит из модулей с зависимостями (как провайдеры в DI-контейнере или пакеты в монорепе). Напиши loadOrder(deps): deps объект имя → массив имён зависимостей. Верни порядок инициализации, в котором каждый модуль идёт после всех своих зависимостей. Если есть цикл, верни { cycle: [...] }: имена модулей цикла в порядке обхода, начиная с того, на котором цикл замкнулся, и с ним же в конце (например ['a', 'b', 'a']).
Чтобы ответ был однозначным: обходи модули в порядке ключей deps, зависимости в порядке массива, DFS с выводом модуля после его зависимостей. Зависимость, которой нет среди ключей, считается модулем без зависимостей.
Примеры
loadOrder({"app":["db","cache"],"db":["config"],"cache":["config"],"config":[]}) // ["config", "db", "cache", "app"]
loadOrder({"a":["b"],"b":["a"]}) // {"cycle":["a","b","a"]}
loadOrder({"users":["auth"],"auth":["tokens"],"tokens":["users"],"logger":[]}) // {"cycle":["users","auth","tokens","users"]}
Как подойти
Подсказки: 2
- Три состояния вершины: не посещена, в обходе, готова.
- Встретили вершину «в обходе»: это цикл, он лежит в стеке от неё до вершины стека.
Решите в тренажёре
Редактор с автотестами прямо в браузере. Можно решить спокойно, вслух или под таймером, как на собесе.