Snapchat OA 面试真题解析：Data Processing Pipeline Task Scheduling（拓扑排序）

Data Processing Pipeline: n tasks — tasks have ids [0,1,2,…,n-1].

Task Ti depends on task Tj — [Ti, Tj] — task Ti cannot start unless task Tj has finished.

Example: n = 5 tasks — list of dependencies dlist = [[1,0], [2,0], [3,4], [3,1], [4,2]]

• [1,0] — 1 depends on 0
• [2,0] — 2 depends on 0
• [3,4] — 3 depends on 4
• [3,1] — 3 depends on 1
• [4,2] — 4 depends on 2

Execution Order: 0 -> 1 / 2 -> 4 -> 3

这道题本质上是一个任务依赖调度问题：每个任务都有先修任务，只有当依赖完成后才能执行，因此需要把依赖关系建成有向图，并使用拓扑排序来求出可行的执行顺序。示例中 0 是所有任务的起点，完成 0 后 1 和 2 才能并行开始，随后 4 依赖 2，最后 3 同时依赖 1 和 4，所以执行链可以写成 0 -> 1/2 -> 4 -> 3。面试中通常要注意是否存在环，如果图中有环就说明无法完成全部任务。