Quick Overview

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

Return valid task order from prerequisites

Company: Netflix

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Onsite

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”).

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

Read the full Netflix Software Engineer interview experience this question came from

Part 1: Return one valid execution order of all tasks

You are given n tasks labeled 0 to n-1 and a list of dependency pairs (a, b), meaning task a must be completed before task b. For this problem, you may assume the dependency graph is acyclic. Return any valid execution order that includes every task exactly once and satisfies all dependencies. If n is 0, return an empty list.

Constraints

  • 0 <= n <= 100000
  • 0 <= len(dependencies) <= 200000
  • 0 <= a, b < n for every dependency (a, b)
  • All dependency pairs are distinct
  • The dependency graph is guaranteed to be acyclic for this part

Examples

Input: (4, [(0, 1), (1, 2), (2, 3)])

Expected Output: [0, 1, 2, 3]

Explanation: There is only one valid order because each task depends on the previous one.

Input: (4, [(0, 2), (1, 2), (2, 3)])

Expected Output: [0, 1, 2, 3]

Explanation: Tasks 0 and 1 can swap places, but both must appear before 2, and 2 must appear before 3. This is one valid answer.

Hints

  1. Count how many prerequisites each task has.
  2. Start with every task whose prerequisite count is 0, and remove tasks layer by layer.

Part 2: Return an empty list if the dependency graph contains a cycle

You are given n tasks labeled 0 to n-1 and a list of dependency pairs (a, b), meaning task a must be completed before task b. Return one valid execution order of all tasks if such an order exists. If the dependency graph contains a cycle, it is impossible to finish every task, so return an empty list.

Constraints

  • 0 <= n <= 100000
  • 0 <= len(dependencies) <= 200000
  • 0 <= a, b < n for every dependency (a, b)
  • All dependency pairs are distinct

Examples

Input: (3, [(0, 1), (1, 2)])

Expected Output: [0, 1, 2]

Explanation: This graph is acyclic, so a full ordering exists.

Input: (3, [(0, 1), (1, 2), (2, 0)])

Expected Output: []

Explanation: The dependencies form a cycle, so no valid ordering exists.

Hints

  1. A topological ordering exists only if you can repeatedly remove a task with indegree 0.
  2. After processing, compare how many tasks you placed in the order versus n.

Part 3: Return the lexicographically smallest valid execution order

You are given n tasks labeled 0 to n-1 and a list of dependency pairs (a, b), meaning task a must be completed before task b. Return the lexicographically smallest valid execution order among all possible topological orders. If the graph contains a cycle, return an empty list.

Constraints

  • 0 <= n <= 100000
  • 0 <= len(dependencies) <= 200000
  • 0 <= a, b < n for every dependency (a, b)
  • All dependency pairs are distinct

Examples

Input: (4, [(0, 2), (1, 2)])

Expected Output: [0, 1, 2, 3]

Explanation: Initially tasks 0, 1, and 3 are available. Choosing the smallest available task each time gives the lexicographically smallest order.

Input: (6, [(2, 3), (1, 3), (0, 4)])

Expected Output: [0, 1, 2, 3, 4, 5]

Explanation: This is the smallest order that respects all three dependencies.

Hints

  1. When several tasks are ready at the same time, always choose the smallest label first.
  2. A min-heap is a good way to repeatedly extract the smallest available task.

Part 4: Return all valid topological orders

You are given n tasks labeled 0 to n-1 and a list of dependency pairs (a, b), meaning task a must be completed before task b. Return all valid execution orders of the tasks. Because the number of valid orders can be exponential, assume n is small. Return the list of orders in lexicographic order. If the graph contains a cycle, return an empty list. If n is 0, return [[]], since there is exactly one ordering of zero tasks.

Constraints

  • 0 <= n <= 10
  • 0 <= len(dependencies) <= n * (n - 1) / 2
  • 0 <= a, b < n for every dependency (a, b)
  • All dependency pairs are distinct

Examples

Input: (3, [(0, 2), (1, 2)])

Expected Output: [[0, 1, 2], [1, 0, 2]]

Explanation: Task 2 must be last. Tasks 0 and 1 can appear in either order.

Input: (3, [])

Expected Output: [[0, 1, 2], [0, 2, 1], [1, 0, 2], [1, 2, 0], [2, 0, 1], [2, 1, 0]]

Explanation: With no dependencies, every permutation is valid.

Hints

  1. Use backtracking: at each step, try every currently available task with indegree 0.
  2. After exploring one choice, undo the indegree updates before trying the next choice.

Loading coding console...