Код Middle ETL, ELT и Airflow обновлено
Порядок выполнения задач DAG
Условие
Напишите topo_order(tasks, deps): tasks список имён задач, deps список пар [a, b] «a должна выполниться до b». Верните порядок выполнения: на каждом шаге из задач, у которых все предшественники уже выполнены, берите лексикографически наименьшую. Если в графе есть цикл, верните None.
Примеры
topo_order(["extract", "load", "check", "mart"], [["extract", "load"], ["load", "check"], ["check", "mart"]]) // ["extract", "load", "check", "mart"]
topo_order(["b", "a", "c"], []) // ["a", "b", "c"]
topo_order(["a", "b"], [["a", "b"], ["b", "a"]]) // null
Как подойти
Подсказки: 2
- Входящие степени и очередь с приоритетом (
heapq). - Цикл: в итоговом порядке меньше задач, чем всего.
Решите в тренажёре
Редактор с автотестами прямо в браузере. Можно решить спокойно, вслух или под таймером, как на собесе.