Amazon VO 面试真题解析：Package Dependency Order（拓扑排序）

Hello from Carl.

There is a list of packages A, B, C, D, etc. and a list of dependencies:

• B -> A (package B depends on successful compilation of A)
• X -> A, B
• D -> X
• F -> B, D

[package a: depend package b]

Class Solution:

def ...

这道题本质上是在给定包依赖关系的情况下，找出一个可行的编译顺序。每个依赖可以看作有向边“被依赖包 → 当前包”，只要先完成所有前置包，就能编译后续包。典型做法是构建依赖图并进行拓扑排序：可以用 DFS 检测环并输出顺序，也可以用入度表配合队列从没有依赖的包开始逐层处理。题目示例中 B 依赖 A，X 依赖 A 和 B，D 依赖 X，F 依赖 B 和 D，因此必须先编译 A，再编译 B、X、D，最后到 F。