题目重点：Nvidia NG SDE Onsite 面经要求实现 graph 的 insert/configure/validate，检查 cycle、dependency order 和结构限制；本文拆清数据模型、验证顺序与增量更新。
题意与假设
这道练习题保留了面经中值得训练的核心约束，并将需要澄清的条件单独列出。现场拿到变体时，先和面试官确认这些条件。
- 训练图为有向图，节点表示计算 op，边 u→v 表示 v 依赖 u 的输出；node_id 全局唯一。题目只说 graph，不保证一定是计算图或边方向如此。
- insert 先建立节点及声明的输入依赖；configure 更新节点参数或边，但不假设每次更新后图一定合法，validate 负责给出可读错误。
- 训练版结构检查包括重复 ID、缺失依赖、输入输出类型不匹配和不允许的环；面试官若给出其他 requirements，以题面规则替换。
解题路线
- 用 nodes[id] 保存 op、参数、输入/输出类型及依赖 ID。将“可存储的草稿图”和“通过 validate 的可执行图”分开，避免 configure 中途的半成品被执行。
- validate 第一遍检查引用存在、输入位置和类型，避免遍历时因为缺节点而报不清楚的错误；随后建立入度和后继邻接表。
- 用 Kahn 拓扑排序：把入度 0 节点入队，每处理一个节点减少其后继入度。若最终处理数小于节点数，则存在环。得到的拓扑序也可作为依赖执行顺序。
- 结构限制按独立规则模块校验，例如指定 op 的入边数量、只允许特定节点做输出、参数范围。configure 后至少重新验证被改节点及其后继；若改了边，环检测可能影响更大范围，保守时全图验证。
手动走一遍
插入 A(source)、B(conv,依赖 A)、C(activation,依赖 B)，拓扑序为 A→B→C。若 configure(A) 增加对 C 的依赖，形成 A→B→C→A，Kahn 排序无法处理完全部 3 个节点，validate 返回 cycle；若 B 引用不存在的 D，则应先返回 missing dependency，而非误报 cycle。
规模与取舍
全图 validate 的引用、类型和拓扑检查为 O(V+E)，空间 O(V+E)。insert/configure 的原始状态修改可近似 O(受影响字段数)，但若要求操作后立即保持有效图，每次更新还可能触发 O(V+E) 验证；增量检测要有失效范围与缓存版本。
易错点与追问
容易失分的边界
- 边方向没有讲清，就把拓扑执行顺序反过来。
- 只用 DFS 标记 visited 不区分 visiting 与 finished，无法正确识别回边。
- 发现环后仍返回部分拓扑序并当成可执行计划。
- 只在 insert 时 validate，configure 修改依赖或类型后沿用旧的“合法”缓存。
继续深挖
- 如果图规模巨大且 configure 频繁，讨论局部受影响子图与周期性全量校验的取舍。
- 执行时如何处理同一节点被多个下游消费、失败重试与结果缓存？这些超出题目明确接口，先问是否需要。
- 错误返回可同时携带 rule、node_id 与冲突边，便于候选人和调用方定位结构问题。
