面试题库 › Java 后端 › 课程表:根据任务依赖判断能否全部完成

课程表:根据任务依赖判断能否全部完成

难度 ★★☆在 2 场真实面经中被问到 方向:Java 后端考点:图论

哪些公司问过

拼多多2

常见岗位:C++ 后端、Java 后端

答案要点

  1. 建模为有向图,依赖 B 先于 A 对应边 B 指向 A
  2. 能全部完成等价于图中无环
  3. Kahn 算法:入度为 0 入队,出队计数,计数等于节点数则无环
  4. DFS 三色标记,遇到访问中的节点即有环
  5. 时间空间均为 O(V + E);输出顺序记录出队序列,最少轮数按层 BFS

易错点

面试官常见追问

完整的口述示范答案、每个追问的参考回答,在启面刷题中心查看;也可以让 AI 面试官用语音按这道题连环追问你。

相关面试题