题干与适用场景
请实现一个内存中的 TaskScheduler。调用方提交任务 ID、依赖 ID 列表和函数；依赖全部成功后任务才可以被领取执行。调度器需要提供 submit、ready、complete、fail 和 cancel 等操作，并能报告无法运行的循环依赖。请说明并发上限、重复提交、失败传播、关闭和重启边界。
这道题把图遍历与可运行接口放在同一个约束里。候选人需要先澄清任务状态和失败契约，再把入度维护、就绪队列和状态转移落实到代码。Python 的 TopologicalSorter 将“没有未完成前驱的节点”作为可处理节点，并把检测到的循环作为可诊断结果；这些语义可以帮助定义题目的状态机，但实现不能只调用现成排序函数，因为任务会动态完成、失败和取消。
面试官考察点
- 能否把
pending、ready、running、succeeded、failed、blocked、cancelled区分开。 - 能否把依赖图的入度和反向邻接表维护成不变量，而不是每次扫描全部任务。
- 能否在依赖完成时只释放受影响的下游节点，保证每条边只处理有限次。
- 能否先定义循环、失败和取消的传播规则，再选择返回值和错误类型。
- 能否限制 worker 并发、保证同一任务只被领取一次，并处理重复提交的版本语义。
- 能否给出时间复杂度、空间复杂度和一组覆盖交错时序的测试。
回答前需要澄清的问题
- 任务提交是一次性静态 DAG，还是允许任务动态加入？默认任务必须在开始调度前提交，运行期间只允许提交尚未被引用的新版本。
- 依赖失败后，下游是
blocked、自动取消，还是允许人工重试？本题默认下游进入blocked，重试必须显式创建新版本。 - 取消一个任务是否级联到所有后代？默认只取消该任务；后代在观察到必需依赖取消后进入
blocked，不隐式删除无关分支。 - 函数失败是否自动重试？默认不自动重试；重试策略由调用方提交新版本并保证副作用幂等。
ready()返回一个任务还是一批任务？默认返回最多maxConcurrency - running个确定顺序的任务。
30 秒回答框架
我会为每个任务保存状态、未完成依赖数和依赖它的反向邻接表。提交完成后先做一次三色 DFS 或 Kahn 检测，发现循环就返回包含节点路径的诊断。入度为零的任务进入就绪队列；领取时原子地从 ready 改成 running，完成成功后遍历反向邻接表，把下游未完成依赖数减一，降到零就入队。失败或取消按预先声明的规则把后代标记为 blocked。所有状态转移受同一把锁或单线程事件循环保护，并用版本号拒绝旧提交。
分步骤深入解答
第一步：定义状态和边界
任务状态只允许沿着有限方向前进：pending 到 ready，再到 running，最后到 succeeded 或 failed；取消可以发生在 pending 或 ready，运行中的取消只记录合作式停止请求。blocked 表示任务本身没有执行，但至少一个必需依赖不可能成功。任何终态都不能回到 ready，否则同一函数可能被执行两次。
每个任务记录 generation。同一 ID 的重复提交要么明确拒绝，要么生成新版本并让旧版本失效；本题选择后者，但只有尚未运行的旧版本可以被替换。已经 running 的版本不能被静默覆盖，应返回冲突或等待它进入终态。
第二步：建立入度和反向邻接表
任务表保存 remainingDeps，反向表保存 dependents[dependencyId]。提交一个任务时，先确认依赖存在或按契约创建占位节点，再把每条边登记一次。初始化阶段把入度为零的任务放入就绪队列，之后只在依赖状态发生变化时更新计数。
下面的伪代码展示核心数据结构：
Task:
id, generation, dependencies, dependents
remainingDeps, state, fn, error
submit(task):
validateUniqueDependencies(task)
registerEdges(task)
if task.remainingDeps == 0:
task.state = READY
readyQueue.push(task.id)若允许缺失依赖，不能把它当成已完成。应保存 waiting 状态，直到依赖提交；否则入度会被错误地减到零。若不允许缺失依赖，则在提交时返回可定位的 UnknownDependency。
第三步：在开始前报告循环
静态图可以使用 Kahn 算法：复制入度，把零入度节点加入队列，移除它们的出边；若处理数量小于节点总数，剩余节点至少属于一个环。为了让面试答案可操作，应同时返回一条具体路径，例如 A → B → C → A，而不是只返回“存在循环”。
如果选择 DFS，使用白、灰、黑三色标记：从灰节点再次遇到灰节点时，沿父指针截取环。检测必须发生在任务进入 running 前；运行期间动态加入边会让已领取任务的语义变得含糊，最简单的契约是禁止修改已开始的图。
第四步：领取任务并限制并发
ready() 计算可用槽位，按稳定的提交序号从队列取出任务，并在同一临界区把状态改为 running。返回后即使 worker 尚未开始执行，其他调用也不能再次领取它。complete(id, generation) 必须校验版本和状态，旧 worker 的迟到回调只能返回冲突，不得再次释放下游。
并发上限可以由固定 worker 数或信号量表达。队列长度不等于活动任务数；只有 running 计入上限。若调用方一次请求的批次大于剩余槽位，应只返回可用数量或明确返回 CapacityExceeded，不能偷偷增加并发。
第五步：传播成功、失败和取消
成功完成后，遍历该任务的直接下游，把仍为 pending 或 ready 的节点的 remainingDeps 减一；降到零就入队。失败时，本题将直接下游和其后代标记为 blocked，并保存第一个阻塞原因；也可以选择“允许替代依赖”，但必须把它写入契约而不是在代码里隐式判断。
取消只影响尚未执行的版本。若运行中的函数支持 AbortSignal，调度器可以发出取消请求，但只有函数确认退出后才把状态置为 cancelled。后代在看到必需依赖是 failed 或 cancelled 时进入 blocked，而不是假装依赖成功。
第六步：处理重复提交和幂等回调
以 (taskId, generation) 作为外部操作的幂等键。重复的 complete、fail 或 cancel 请求返回当前终态，不重复减少下游入度。新提交若替换旧的 pending 版本，应先从反向表撤销旧边，再登记新边并重新计算可达状态；这比直接覆盖对象安全，因为旧边残留会让下游永远等待。
若系统不需要更新语义，拒绝重复 ID 会更简单。面试中应说明选择依据：静态构建器可以拒绝重复，长期运行的工作流则通常需要 generation、审计和重试版本。
第七步：关闭、重试与恢复
close() 先拒绝新提交，再停止 ready() 领取，最后等待 running 任务回调或达到明确的超时。队列中的任务应根据契约取消或保留，不能仅清空内存结构而丢失原因。重试创建新 generation，并重新检查依赖快照；直接把 failed 改回 ready 会绕过失败原因和并发回调。
纯内存实现不能在进程崩溃后恢复。若要持久化，需要保存任务、版本、状态、依赖和租约；恢复 worker 通过条件更新抢占任务，并让函数具备幂等性。恢复只能提供至少一次执行，不能承诺恰好一次副作用。
第八步：复杂度与测试
初始化图的时间复杂度是节点数加边数，记作 O(V + E)。每次完成任务只遍历它的出边，因此整批传播总成本仍为 O(V + E)；就绪队列若使用堆，领取为 O(log V)。空间复杂度为 O(V + E)。
测试至少覆盖空图、多个独立分支、长链、环、缺失依赖、同一节点被两个依赖同时完成、失败传播、取消后代、重复回调、重复提交、并发槽位为零、关闭期间领取和旧 generation 的迟到回调。可用一个小型状态模型对拍每次可执行集合，并记录每个任务最多一次 running 转换。
高质量示范回答
我会先冻结任务图，然后对每个任务保存状态、generation、未完成依赖数和反向邻接表。构建阶段用 Kahn 加父指针检测循环并返回一条环路径；没有依赖的任务进入带稳定序号的就绪队列。ready() 在锁内按剩余并发槽位领取，并立即把任务改成 running。成功回调只接受匹配 generation 的一次性终态，沿反向边递减下游计数，降到零才入队。失败和取消不会冒充成功，而是把受影响后代置为 blocked。重复回调幂等，重试创建新版本；关闭先拒绝新任务，再停止领取并等待运行中的回调。整个批次是 O(V + E)，并发和副作用边界都由测试验证。
常见错误
- 只做一次拓扑排序，却没有说明动态完成和失败后的状态变化。
- 每次寻找就绪任务都扫描全部节点，忽略反向邻接表和入度不变量。
- 发现环时只返回布尔值，无法指出哪组任务阻塞了发布。
- 任务完成回调不带版本号，旧 worker 会重复释放下游。
- 把依赖失败当成依赖成功，导致下游在前置条件不满足时执行。
- 把取消运行中函数描述成强制中止，却没有合作式信号或资源回收契约。
- 通过增加 worker 数解决队列积压，结果把并发上限和下游容量一起打穿。
- 重试直接复用旧状态，遗漏幂等、副作用和租约恢复边界。
追问及应对
如果任务图很大，如何避免一次性把所有节点放进内存？
把任务元数据和边存入持久化存储，按租户或分区加载可运行窗口；内存只保留活动节点和游标。领取使用条件更新或短租约，完成时仍校验 generation。需要说明跨分区依赖、分页一致性和租约过期后的重复执行。
如何允许失败分支继续运行，但阻止依赖失败的节点？
把边标注为必需或可选，任务只有所有必需依赖成功且可选依赖已终态时才进入 ready。可选依赖失败应写入输入摘要和指标，不能静默丢弃；这会扩大状态机和测试矩阵。
如何支持动态加入依赖？
只允许在任务仍为 pending 时追加边，并在同一临界区增加入度；已经 ready 或 running 的任务拒绝修改。若业务必须支持运行中变更，应创建新 generation，等待旧版本终态后再按新图执行。
取消一个共享依赖时，怎样避免误伤其他分支？
取消只改变该依赖节点的终态，传播器沿反向边逐个判断必需关系。没有该依赖的分支继续运行；共享依赖的所有必需下游进入 blocked。审计记录需要保留取消者、时间和传播路径。
多 worker 进程如何保证同一任务只执行一次？
用持久化存储中的原子领取或租约字段抢占任务，并把 generation 放进条件。租约过期后允许再次领取，因此函数必须幂等或提供补偿。内存锁只能保护单进程，不能作为跨进程唯一保证。
面试官要求给出可观察指标，你会选什么？
记录循环任务数、阻塞任务数、就绪等待时间、运行时长、领取冲突、租约过期、重复回调和每条边的传播延迟。按任务类型和租户分层，避免只看平均值掩盖尾部积压；指标还应能区分图配置错误和执行函数失败。
如何证明不会把任务领取两次？
把“检查状态、减少槽位、写入 running”放在同一临界区或原子条件更新中，并为回调携带 generation。模型测试枚举两个并发 ready() 调用，断言每个版本最多一次 pending → running；重复完成只返回已知终态。