Bird
Raised Fist0

Consider the following buggy implementation of Kahn's Algorithm for course scheduling. Which line contains the subtle bug that can cause incorrect or infinite behavior?

medium🐞 Bug Identification Q14 of Q15
Topological Sort - Course Schedule II (Topological Order)
Consider the following buggy implementation of Kahn's Algorithm for course scheduling. Which line contains the subtle bug that can cause incorrect or infinite behavior?
ALine 6: graph[a].append(b) -- edge direction reversed
BLine 7: in_degree[a] += 1 -- incorrect in-degree increment
CLine 10: queue initialization -- wrong nodes enqueued
DLine 15: in_degree[nei] -= 1 -- decrementing in-degree incorrectly
Step-by-Step Solution
Solution:
  1. Step 1: Analyze edge construction

    Prerequisite pairs are (a, b) meaning b -> a edge; reversing to graph[a].append(b) flips direction.
  2. Step 2: Consequences of reversed edges

    In-degree counts and BFS queue become invalid, causing wrong order or infinite loop.
  3. Final Answer:

    Option A -> Option A
  4. Quick Check:

    Correct edge direction is critical for topological sort correctness [OK]
Quick Trick: Check edge direction carefully when building graph [OK]
Common Mistakes:
MISTAKES
  • Reversing edges when building adjacency list
  • Incrementing in-degree on wrong node
  • Forgetting to decrement in-degree
Trap Explanation:
PITFALL
  • Reversing edges looks plausible but breaks prerequisite ordering, a subtle but critical bug.
Interviewer Note:
CONTEXT
  • Tests if candidate can spot subtle graph construction bugs that break topological order.
Master "Course Schedule II (Topological Order)" in Topological Sort

3 interactive learning modes - each teaches the same concept differently

Want More Practice?

15+ quiz questions · All difficulty levels · Free

Free Signup - Practice All Questions
More Topological Sort Quizzes