Microsoft·Software Engineer·Technical Phone Screen·Intermediate

IntermediatePrefer not to say

Jun 2026

Summary

Microsoft SWE interview that went deep on graph algorithms. The core problem was topological sort and they wanted a real implementation, not just a conceptual answer.

Questions Asked (1)

Given a directed graph as an adjacency list with V vertices and an edge list, determine if a valid topological ordering exists and return one if it does. Be ready to implement this using either an in-degree queue approach or DFS post-order, and explain how you'd handle disconnected components and cycle detection.

Algorithms & Data StructuresTechnical Trade-offs

Author's notes

I went with Kahn's algorithm because tracking in-degrees felt cleaner to explain out loud.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Start by clarifying the problem constraints and then present Kahn's algorithm (in-degree queue) as the primary solution, explaining how it naturally detects cycles and handles disconnected components. Alternatively, describe the DFS post-order approach with cycle detection using recursion stack, and compare trade-offs. Walk through a small example to illustrate.

Pro tip: Mention that Kahn's algorithm can be easily modified to return the lexicographically smallest topological order using a min-heap, which is a common follow-up at Microsoft. Also, note that if the graph has multiple connected components, both approaches handle them seamlessly by initializing the queue with all in-degree zero vertices or iterating over all vertices in DFS.

1. Clarify requirements and constraints

Ask about input size, whether the graph is guaranteed to be a DAG, and if any specific ordering (e.g., lexicographical) is required. Confirm the expected output format.

2. Choose an algorithm and explain the approach

Select either Kahn's algorithm (BFS with in-degree queue) or DFS post-order. Explain the steps: compute in-degrees, use a queue for Kahn's, or use DFS with visited and recursion stack for cycle detection.

3. Handle disconnected components and cycle detection

For Kahn's, initialize the queue with all vertices having in-degree zero; if the queue empties before processing all vertices, a cycle exists. For DFS, iterate over all unvisited vertices and use a recursion stack to detect back edges.

4. Implement the solution

Write clean code with appropriate data structures (e.g., adjacency list, queue, arrays for in-degree/visited). Ensure edge cases like empty graph or single vertex are handled.

5. Analyze complexity and test

State time and space complexity (O(V+E) for both). Walk through a small example, including a graph with a cycle and one with disconnected components, to verify correctness.

Key Points to Mention

Kahn's algorithm: compute in-degrees, use queue, if processed count < V then cycle exists.
DFS post-order: reverse post-order gives topological sort; use recursion stack for cycle detection.
Disconnected components: both algorithms handle them by initializing with all in-degree zero vertices or iterating over all vertices.
Cycle detection: Kahn's detects cycle if not all vertices are processed; DFS detects back edge to recursion stack.
Time and space complexity: O(V+E) time, O(V) space for both approaches.
Trade-offs: Kahn's is iterative and easier to modify for lexicographical order; DFS is recursive and may risk stack overflow for large graphs.

AI-generated suggestions, not part of the candidate's original notes. May be inaccurate — verify before relying on them.