How do you perform topological sort on a directed acyclic graph?
Reported in Multiverse Computing European engineering loops. Graph algorithm for task scheduling, build systems, and course prerequisites.
Interview scenario
Context for Multiverse Computing candidates:
Detect cycle if present; otherwise return valid ordering of nodes.
Model answer
Try answering aloud first
Cover trade-offs, structure, and a concrete example before revealing the baseline response.
How to frame this at Multiverse Computing: Connect your answer to measurable impact, clarity of thought, and trade-offs the team cares about. Below is a strong baseline response you can adapt with your own project examples.
Kahn's algorithm (BFS): compute in-degree for each node; enqueue nodes with in-degree 0; dequeue, append to order, decrement neighbors' in-degree; enqueue newly zero nodes. If order length < V, cycle exists.
DFS approach: post-order stack—after visiting all descendants, push node. Reverse stack for topological order. Track visiting/visited states for cycle detection (back edge).
Time O(V + E), space O(V). Applications: Maven/Gradle task order, course prerequisites, instruction scheduling in compilers.
Follow-up: longest path in DAG for critical path method; parallel topological levels for batch execution.
Discussion
Comments (0)
Share how this question came up in your loop, or add tips for others preparing.
Log in to comment on this question.