DAG Algorithms, Topological Sort, And Cycle Detection

What's being tested

Candidates must demonstrate correct application of topological sort over a directed acyclic graph (DAG), including deterministic ordering and reachable-node aggregation. Interviewers probe both cycle detection (detecting and reporting impossible orders) and efficient transitive aggregation (e.g., inherited permissions/roles) under time/space constraints.

Patterns & templates

• Kahn's algorithm (BFS in-degree queue) for O(V+E) topological orders; use a min-heap when lexicographic determinism is required.

• DFS with recursion stack for fast cycle detection and postorder topological output; track visit states {unseen, visiting, done}.

• Represent graphs with an adjacency list (Map<int, List<int>>) for memory-efficient traversal when E ~ V..10V.

• For transitive aggregation, propagate sets top-down (BFS) or merge child-to-parent using union-by-size to limit copying.

• Use a priority queue to produce deterministic alphabetical outputs when multiple nodes have zero in-degree.

• For permission models, treat "local deny" vs "inherited allow" by storing two flags per node and resolving precedence on aggregation.

• When scale is large (N > 1e6 edges), prefer iterative DFS/Kahn and avoid recursion to prevent stack overflow.

Common pitfalls

Pitfall: Forgetting disconnected components — run the algorithm starting from all zero in-degree nodes, not just an arbitrary root.

Pitfall: Returning any topological order when the problem requires deterministic lexicographic order — use a min-heap for zero in-degree selection.

Pitfall: Merging large sets naively per node — use union-by-size or bitsets when alphabet/domain is small to avoid O(N^2) behavior.

Practice these: the practice cards below cover the canonical variants — solve all of them and time yourself.