Amazon NG 面试真题：TaskScheduler 任务调度器完整分析（拓扑排序）

最近 Amazon NG 面试出 OOD 的频率真的太高了，认真复盘一下这道真题。

一、核心算法考点：拓扑排序（有向无环图 DAG）

这是本题最核心的考点，底层是 Kahn 拓扑排序算法（入度 + BFS）。

1. 图建模

• 任务 = 图节点
• 依赖关系「A 依赖 B」→ 有向边 B → A（B 先执行，A 后执行）
• 构建邻接表 graph，以及每个节点的入度字典 indegree

2. Kahn 算法流程

• 初始化队列：放入所有入度为 0、没有依赖的任务
• BFS 循环：弹出队首节点，遍历它的后继任务，后继入度减 1；入度归零就入队
• 收集执行顺序 order 作为返回结果

3. 边界判定（隐含考点）

如果最终 order 的长度不等于任务总数，说明图中存在环依赖，需要抛出异常。原题代码里这一步没写完，是常考的补全点。

参考实现

from collections import defaultdict, deque

class CyclicDependencyError(Exception):
    pass

class TaskScheduler:
    def __init__(self):
        self.graph = defaultdict(list)     # B -> [依赖 B 的任务]
        self.indegree = {}

    def add_task(self, task, depends_on=()):
        self.indegree.setdefault(task, 0)
        for dep in depends_on:
            self.indegree.setdefault(dep, 0)
            self.graph[dep].append(task)
            self.indegree[task] += 1

    def schedule(self):
        indegree = dict(self.indegree)     # 拷贝一份，schedule 可重复调用
        queue = deque(t for t, d in indegree.items() if d == 0)
        order = []
        while queue:
            task = queue.popleft()
            order.append(task)
            for nxt in self.graph[task]:
                indegree[nxt] -= 1
                if indegree[nxt] == 0:
                    queue.append(nxt)
        if len(order) != len(indegree):
            raise CyclicDependencyError("tasks contain a dependency cycle")
        return order

时间 O(V + E)，空间 O(V + E)。

讨论：这算 OOD 还是 LC 算法题的升级？

你觉得这种题算是 OOD，还是 LC 算法题的升级版？

个人理解是两者都考：

• 算法内核：拓扑排序。
• OOD 外壳：类的接口设计（add_task / schedule）、状态是否可以重复调度、异常类型如何定义、以后要不要支持任务优先级或并行执行。

欢迎交流你的看法！