How do you implement Topological Sorting for a Directed Acyclic Graph?
This problem asks to order vertices such that for every directed edge u->v, u comes before v. It tests Kahn's algorithm or DFS.
Why Interviewers Ask This
Interviewers ask this to test graph ordering skills. They want to see if you can handle dependencies and detect cycles implicitly. It demonstrates practical scheduling logic.
How to Answer This Question
Explain Kahn's algorithm: calculate in-degrees, enqueue nodes with zero in-degree, process and reduce neighbors' in-degrees. Or use DFS and add nodes to result in post-order. Discuss cycle detection.
Key Points to Cover
- In-degree calculation
- Zero in-degree queue
- Processing order
- Cycle detection
Sample Answer
I use Kahn's algorithm which relies on in-degrees. First, I calculate the in-degree for every node. I enqueue all nodes with an in-degree of zero. Then, I dequeue a node, add it to the result, and decrease the in-degree…
Common Mistakes to Avoid
- Not initializing in-degrees correctly
- Forgetting to check for cycles
- Incorrect neighbor updates
Sound confident on this question in 5 minutes
Answer once and get a 30-second AI critique of your structure, content, and delivery. First attempt is free — no signup needed.