Netflix·Software Engineer·Technical Phone Screen·Intermediate

IntermediatePrefer not to say

May 2026Remote

Summary

Netflix coding round, one question the whole time. Graph stuff, specifically topological sort. Not the hardest topic but I definitely fumbled some of the implementation details under pressure.

Questions Asked (1)

Given a directed acyclic graph, return a valid topological ordering of its nodes. Handle the case where a cycle exists. You can use either a BFS-based in-degree approach or DFS with post-order traversal.

Algorithms & Data Structures

Author's notes

I went with the in-degree BFS approach because I'd drilled it recently and felt more confident there.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Start by clarifying the graph representation and whether the graph is guaranteed acyclic. Then implement Kahn's algorithm (BFS with in-degree) or DFS with cycle detection, explaining the trade-offs. Finally, discuss time and space complexity and how to handle cycles by returning an error or empty list.

Pro tip: Mention that Kahn's algorithm can detect cycles by comparing the number of processed nodes to the total; if they differ, a cycle exists. This shows you understand both topological sorting and cycle detection in one pass.

1. Clarify assumptions and edge cases

Ask about graph representation (adjacency list/matrix), whether the graph is guaranteed acyclic, and expected output for cycles (e.g., empty list or error).

2. Choose an algorithm and explain it

Select either Kahn's algorithm (BFS with in-degree) or DFS with post-order, and briefly describe how it works, including cycle detection.

3. Walk through an example

Trace the algorithm on a small DAG to demonstrate correctness, and then on a graph with a cycle to show how the cycle is detected.

4. Analyze complexity and trade-offs

State time and space complexity (O(V+E) for both approaches) and discuss when one might be preferred over the other.

5. Handle cycles explicitly

Explain how your chosen method detects cycles and what you return or throw in that case, ensuring the solution meets the requirement.

Key Points to Mention

Definition of topological ordering and its applications (e.g., task scheduling, dependency resolution).
Kahn's algorithm: compute in-degrees, use a queue, decrement in-degrees of neighbors.
DFS approach: use a recursion stack or color marking (white/gray/black) to detect cycles.
Cycle detection: in Kahn's, if processed nodes < total nodes, a cycle exists; in DFS, a back edge indicates a cycle.
Time and space complexity: O(V+E) time, O(V) space for both algorithms.
Edge cases: empty graph, single node, disconnected components, self-loops.

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