Граф зависимостей с кешем на запрос: задача с собеседования

Условие

Смоделируйте разрешение зависимостей FastAPI. deps это словарь «имя -> список зависимостей», target это эндпоинт. Каждая зависимость вычисляется один раз за запрос (кеш), сначала её зависимости в порядке списка. Зависимости с yield (их имена в generators) после ответа закрываются в порядке, обратном порядку их запуска. Верните [порядок вызова, порядок закрытия], эндпоинт тоже входит в порядок вызова последним.

Примеры

resolve({"endpoint":["user","session"],"user":["session","token"],"session":[],"token":[]}, "endpoint", ["session"]) // [["session", "token", "user", "endpoint"], ["session"]]
resolve({"endpoint":[]}, "endpoint", []) // [["endpoint"], []]
resolve({"e":["a","b"],"a":["c"],"b":["c"],"c":[]}, "e", ["a", "c"]) // [["c", "a", "b", "e"], ["a", "c"]]

Как подойти

Подсказки: 2

DFS: сначала зависимости, потом сама функция.
Закрытие в обратном порядке запуска, только для генераторов.

Решите в тренажёре

Редактор с автотестами прямо в браузере. Можно решить спокойно, вслух или под таймером, как на собесе.

Решить в тренажёре

Предыдущий вопрос

Разбор и проверка query-параметров

Следующий вопрос

Подмена зависимостей в тестах

Урок по теме

FastAPI и Pydantic: маршруты, Depends, async и lifespan

Ещё по теме «FastAPI и Pydantic»

Все вопросы модуля