DSA interview question

Topological Sort with Kahn's Algorithm (BFS)

Hard · Data structures · Topics: graph, bfs, topological sort

The problem

The same course planner wants a topological order computed without recursion, and it would like to see the courses that are ready right now at each step. Kahn's algorithm does exactly that. A vertex with in-degree 0 has no remaining prerequisites, so it can be taken. Output it, "remove" its outgoing edges by decrementing its neighbours' in-degrees, and any neighbour whose in-degree drops to 0 becomes ready. A queue holds the ready vertices.

Example: 6 vertices, edges 5→2, 5→0, 4→0, 4→1, 2→3, 3→1 → [4, 5, 2, 0, 3, 1].

Function signature

vector<int> kahnTopoSort(int V, const vector<vector<int>>& adj);  // adj describes a DAG

Test cases

Input `(V, edges)`	Output (initial queue in index order)	Explanation
`(6, [[5,2],[5,0],[4,0],[4,1],[2,3],[3,1]])`	`[4, 5, 2, 0, 3, 1]`	4 and 5 start with in-degree 0
`(4, [[3,0],[1,0],[2,0]])`	`[1, 2, 3, 0]`	0 waits for all three
`(5, [[0,1],[1,2],[2,3],[3,4]])`	`[0, 1, 2, 3, 4]`
`(2, [[1,0]])`	`[1, 0]`
`(3, [])`	`[0, 1, 2]`

(Confirm: the input is a DAG; many orders are valid, and the one shown uses a FIFO queue seeded in index order.)

How interviewers phrase it

"Implement topological sort using Kahn's algorithm (BFS based)" (GeeksforGeeks).

Clarifying questions to ask

DAG guaranteed? (Yes. Without that, the output being shorter than V signals a cycle.)
Is any valid order fine? (Yes. With a min-heap instead of a queue, you get the lexicographically smallest order.)
How large? (Linear time is expected.)

Follow-ups to expect

"Why start with in-degree 0 vertices?"
"Why does decrementing in-degrees work?"
"How does it detect cycles?"
"Smallest lexicographic order?"
"Complexity?"

Practise questions like this with a real engineer

On Practick another engineer interviews you live for 60 minutes on a question from this bank. They have the full interviewer guide beside the call: the expected answer to every follow-up, hints to give if you stall, and a scoring rubric. You get the model solution once the session settles. It is free: interview someone for an hour and you have earned your own.

Book a free mock interview