Дана мапа: библиотека → список библиотек, от которых она зависит. Верните все библиотеки
в порядке импорта: библиотеку можно импортировать только после всех её зависимостей.
Если подходящих порядков несколько, верните любой.
В реальных проектах случаются циклические зависимости — тогда верните ErrCycle.
var ErrCycle = errors.New("dependency cycle")
// ImportOrder возвращает все библиотеки так, что каждая идёт после своих зависимостей.
func ImportOrder(deps map[string][]string) ([]string, error)
Пример
deps := map[string][]string{
"serviceA": {"utilB", "utilC", "base"},
"utilB": {"base"},
"base": {"core"},
"appX": {"serviceA"},
"appY": {"configLib"},
}
// один из правильных ответов:
// core base utilB utilC serviceA appX configLib appY
Требования
- В ответе каждая библиотека ровно один раз: и ключи мапы, и все упомянутые в
зависимостях (у
core, utilC, configLib своих ключей нет).
- Зависимость может быть указана дважды, библиотека может зависеть сама от себя (это
цикл).
- При цикле —
nil, ErrCycle (проверяется через errors.Is).
- До 2·10⁵ библиотек и 10⁶ рёбер. Ожидается O(V + E). Решение «пока есть
неразобранные, проходим по всем и печатаем готовые» — O(V·E), не пройдёт.
Разбор и эталонное решение — после своей попытки: на собеседовании подсказок не будет.
Сначала попробуй сам — подсказки не дают готовый ответ.