A topological order exists only for a directed acyclic graph. Kahn’s algorithm repeatedly removes nodes whose incoming dependencies are satisfied.
Before you start
You should know arrays, loops and basic complexity notation. Start with a small input you can trace by hand. State what each variable means and which invariant is maintained, then use that invariant to explain correctness before discussing performance or writing a more compact solution.
The practical goal is to reason through this situation: Start with zero-indegree tasks and decrement dependents after selecting each task. Read the walkthrough first, then try the interview exercise before opening its answer. The important part is explaining the decision and its consequences, rather than remembering a definition alone.
Step-by-step walkthrough
Step 1: Count incoming dependencies
Initialize indegrees for every node, including isolated ones.
Step 2: Process ready nodes
Remove zero-indegree nodes and decrement their dependents.
Step 3: Check full completion
Fewer processed nodes than total means no complete topological order exists.
Worked scenario
Start with zero-indegree tasks and decrement dependents after selecting each task.
For A→C and B→C, A and B start ready; C becomes ready only after both are removed. Either A,B,C or B,A,C is valid. Adding C→A creates a cycle; returning only the ready prefix would misleadingly imply a full solution.
Common mistake
Returning a partial ordering without checking count can conceal a cycle.
Verify the behavior
Verify every edge respects output order and require all nodes to be present.
Interview exercise
Verify completion.
Answer and reasoning
If fewer than all nodes are processed, remaining dependencies contain a cycle or unsatisfied structure and no full order exists.
Continue learning
Compare the scenario with the Data Structures and Algorithms interview questions and test your understanding with the Data Structures and Algorithms MCQs. For terminology and implementation details, consult the reference material.