题目重点：从面经汇总明确的 task dependency framework 方向出发，设计最小任务接口，先验证未知依赖与环，再用 Kahn 算法执行，并讨论失败/重试与生产调度。
题意与假设
这道练习题保留了面经中值得训练的核心约束，并将需要澄清的条件单独列出。现场拿到变体时，先和面试官确认这些条件。
- 训练版 `tasks` 是 `task_id→零参 callable`，`dependencies[id]` 列先决任务；单线程、确定性插入顺序。题目未明确 API。
- 任务成功才算完成；任意任务抛异常即终止当前运行，不继续执行其后继。已经产生的外部副作用不会自动回滚。
- 依赖列表同一 prerequisite 重复只计一次；缺失 task 或环报 ValueError。
解题路线
- 先校验所有 task id 与 prerequisite id，建立每个节点 indegree 和前驱→后继表。若要求任务结果作为后继输入，Task 接口需再增加依赖结果映射；最小示例仅演示顺序执行。
- 把 indegree=0 的任务放 ready 队列；执行成功后逐个降低后继 indegree，降到 0 才入队。最终完成数小于任务数表明有环或未满足依赖。
- 生产版本将 ready 队列持久化，worker 领取任务需 lease/attempt id；区分失败可重试、永久失败、取消与跳过后继。并发执行时 indegree 变更与状态转移必须原子化；重试需幂等或结果去重。
手动走一遍
训练例 A、B 无依赖，C 依赖 A/B，D 依赖 C。ready 初始为 A/B；两者成功后 C 才可执行，随后 D。若 C 依赖 D，则 C↔D 成环，最终无法完成全部节点。
Python 参考实现
下面的代码按上文假设实现，适合本地运行并追加自己的测试用例。
代码区可横向滚动；使用键盘时，先聚焦代码区再按方向键查看。
from collections import defaultdict, deque
def run_tasks(tasks, dependencies):
"""tasks maps ID to zero-argument callable; deps maps ID to prerequisite IDs."""
indegree = {task_id: 0 for task_id in tasks}
children = defaultdict(list)
for task_id, prerequisites in dependencies.items():
if task_id not in tasks:
raise ValueError("unknown task")
for prerequisite in set(prerequisites):
if prerequisite not in tasks:
raise ValueError("unknown prerequisite")
indegree[task_id] += 1
children[prerequisite].append(task_id)
ready = deque(task_id for task_id in tasks if indegree[task_id] == 0)
order = []
while ready:
task_id = ready.popleft()
order.append(task_id)
for child in children[task_id]:
indegree[child] -= 1
if indegree[child] == 0:
ready.append(child)
if len(order) != len(tasks):
raise ValueError("dependency cycle")
completed = {}
for task_id in order:
completed[task_id] = tasks[task_id]()
return completed
复杂度
V 个任务、E 条去重依赖，建图和 Kahn 调度 O(V+E)，空间 O(V+E)，另加任务本身执行时间。单线程示例 ready 顺序由输入顺序决定，不能据此声称实现了生产级并行 scheduler。
易错点与追问
容易失分的边界
- 任务一提交就运行，尚未等待所有依赖成功。
- 未知依赖静默忽略，导致本应阻塞的任务提前运行。
- 重复依赖把 indegree 多算，永远无法 ready。
- 发生环时一直等待而不报错。
- 任务失败后直接把后继当成功 ready，或说已自动回滚外部副作用。
继续深挖
- 多个 worker 如何并行领取 ready 任务且不重复执行？
- 失败任务的后继是取消、跳过还是可在人工修复后继续？
- 依赖结果如何传给后继而不把大对象留在 scheduler 内存？
- 图运行中动态添加任务会改变何种不变量？
