Katkat
Back

Return valid task order from prerequisites

NetflixSoftware Engineer · Onsite
MediumSoftware EngineerOnsiteCoding & Algorithms

Last updated

This question evaluates proficiency in graph algorithms, notably topological sorting and cycle detection, as well as algorithmic complexity analysis and handling of dependency constraints.

You are given N tasks labeled 0..N-1 and a list of directed dependency pairs [(a,b), ...] meaning task a must be done before task b.

  1. Return one valid execution order of all tasks that satisfies all dependencies.
  2. If it is impossible (the graph has a cycle), return an empty list.

Follow-ups that may be asked:

  • If multiple valid orders exist, return the lexicographically smallest order.
  • Return all valid topological orders (if feasible for the input size).
  • State the time and space complexity of your approach.

Constraints can be assumed typical for interview settings (e.g., up to 1e5 nodes/edges for part 1; much smaller for “all orders”).