← Netflix Interview Insights

Netflix·Software Engineer·Onsite - Coding / Algorithms·Senior

SeniorPrefer not to say
Jun 2026

Summary

Netflix onsite coding round, one problem but it kept expanding. They took a single topological sort question and pushed it through three distinct variants, each with its own runtime requirements. Not a brutal interview but you really had to know your complexity analysis cold.

Questions Asked (3)

Q1

Implement a standard topological sort on a directed acyclic graph. What is the time and space complexity?

Algorithms & Data Structures
Author's notes

This part felt fine.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Start by clarifying that a topological sort orders vertices of a DAG such that for every directed edge u→v, u comes before v. Then present either Kahn's algorithm (BFS-based) or DFS-based approach, explaining the steps and analyzing time and space complexity.

Pro tip: Mention that Kahn's algorithm can also detect cycles (if the result doesn't include all vertices), which is often a follow-up question. Also, note that the space complexity includes the output, so it's O(V+E) overall.

1. Define the problem

State that topological sort is a linear ordering of vertices in a DAG where for every edge u→v, u appears before v. It is only possible if the graph has no directed cycles.

2. Choose an algorithm

Select either Kahn's algorithm (BFS-based) or DFS-based approach. Briefly explain the chosen method: Kahn's uses in-degree counts and a queue; DFS uses post-order traversal and reverses the result.

3. Walk through the algorithm

For Kahn's: compute in-degrees, enqueue vertices with in-degree 0, then repeatedly dequeue, add to result, and decrement in-degrees of neighbors, enqueuing those that become 0. For DFS: perform DFS, and after visiting all neighbors, push the vertex onto a stack; finally pop from stack to get the order.

4. Analyze complexity

Time complexity is O(V+E) because each vertex and edge is processed once. Space complexity is O(V+E) due to storing the graph, in-degree array (or recursion stack), queue/stack, and the output list.

5. Discuss edge cases and applications

Mention that if the graph has a cycle, topological sort is impossible; Kahn's algorithm can detect this if the result size is less than V. Applications include task scheduling, dependency resolution, and build systems.

Key Points to Mention

  • Topological sort only works on DAGs; cycles make it impossible.
  • Kahn's algorithm uses in-degree and a queue; DFS-based uses post-order and a stack.
  • Time complexity: O(V+E) for both approaches.
  • Space complexity: O(V+E) including graph storage and auxiliary data structures.
  • Cycle detection: Kahn's algorithm can detect cycles if not all vertices are processed.
  • Real-world applications: scheduling, dependency resolution, course prerequisites.

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

Q2

Modify your topological sort so that when multiple nodes are available at the same step, they are selected in a specific order (e.g. lexicographic). How does this change the runtime?

Algorithms & Data StructuresTechnical Trade-offs
Author's notes

Swapping the queue for a min-heap was the obvious move and I got there, but I fumbled the runtime explanation for a second.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Explain that the modification replaces the queue with a priority queue (e.g., min-heap) to select the smallest (or specified order) available node at each step. Then analyze the runtime change from O(V+E) to O((V+E) log V) due to heap operations, and discuss trade-offs.

Pro tip: Mention that if the graph is dense, the log factor may be negligible, but for sparse graphs it's significant; also note that using a bucket queue can achieve O(V+E) if the order is based on a small integer key.

1. Identify the modification

Recognize that the standard topological sort uses a queue (FIFO) to process nodes with zero in-degree. To enforce a specific order, replace the queue with a priority queue that orders nodes according to the desired criterion (e.g., lexicographic).

2. Analyze the impact on operations

Each insertion and extraction from the priority queue takes O(log V) time instead of O(1). Since each node is inserted and extracted once, the total time for these operations becomes O(V log V).

3. Consider edge processing

Decrementing in-degrees and checking for zero still takes O(E) total, but when a node's in-degree becomes zero, it is inserted into the priority queue, adding O(log V) per insertion. Thus, the overall time becomes O((V+E) log V).

4. Discuss trade-offs and alternatives

Mention that the log factor may be acceptable for many applications, but if performance is critical, consider using a bucket queue (if keys are small integers) to achieve O(V+E) time, or note that the modification may not be worth it if the order is not strictly necessary.

Key Points to Mention

  • Standard topological sort uses a queue and runs in O(V+E) time.
  • Replacing the queue with a priority queue (e.g., min-heap) enforces the desired order.
  • Each heap operation takes O(log V), leading to O(V log V) for node processing.
  • Total runtime becomes O((V+E) log V) because each edge may cause a heap insertion when in-degree becomes zero.
  • Trade-off: increased time complexity for deterministic ordering.
  • Alternative: bucket queue can achieve O(V+E) if the ordering key is a small integer.

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

Q3

Now enumerate ALL valid topological orderings of the graph. Walk through your approach and explain the worst-case complexity.

Algorithms & Data StructuresTechnical Trade-offs
Author's notes

This is where things got uncomfortable.

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 a DAG. Then, use a backtracking algorithm with in-degree tracking to systematically generate all valid topological orderings, and analyze the worst-case complexity based on the number of orderings and graph size.

Pro tip: Mention that the number of topological orderings can be exponential, so the worst-case complexity is inherently exponential; this shows you understand the problem's inherent difficulty and can discuss trade-offs.

1. Clarify the problem and constraints

Confirm that the graph is directed and acyclic (DAG), and ask about the expected input size and whether all orderings need to be enumerated or just counted.

2. Choose an algorithm

Select a backtracking approach that maintains in-degrees of nodes and recursively picks nodes with zero in-degree, updating in-degrees as nodes are removed.

3. Walk through the algorithm

Explain step-by-step how to generate orderings: initialize in-degrees, find all nodes with in-degree 0, for each such node, add to ordering, decrement in-degrees of its neighbors, recurse, then backtrack.

4. Analyze complexity

Discuss that the worst-case time complexity is O(V * (V+E) * K) where K is the number of topological orderings, which can be exponential (e.g., O(V!) for a graph with no edges).

5. Discuss optimizations and trade-offs

Mention potential optimizations like using a queue or priority queue for deterministic order, or memoization if counting only, and note that enumeration is inherently expensive.

Key Points to Mention

  • Definition of topological ordering and conditions for existence (DAG).
  • Backtracking algorithm with in-degree tracking.
  • Worst-case complexity: exponential in the number of vertices, e.g., O(V!) for an empty graph.
  • Number of topological orderings can be computed via DP on subsets (O(2^V * V)) but enumeration requires output-sensitive complexity.
  • Trade-offs between enumeration and counting, and practical limits for large graphs.
  • Potential use of Kahn's algorithm as a basis for enumeration.

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