FastPrep
Problem · Graph

Topological Sort for Ads Tasks

● MediumNetflixPHONE SCREEN

You are given numTasks tasks labeled from 0 to numTasks - 1 and a list of prerequisite edges. Each edge [before, after] means task before must be completed before task after.

Return one valid order to complete all tasks. If more than one task is available at the same time, choose the smaller task id first so the result is deterministic. If it is impossible to complete all tasks because the dependency graph contains a cycle, return an empty array.

Examples
01 · Example 1
numTasks = 4
edges = [[0, 1], [0, 2], [1, 3], [2, 3]]
return = [0, 1, 2, 3]

Task 0 unlocks tasks 1 and 2. The smaller available id is chosen first.

02 · Example 2
numTasks = 2
edges = [[0, 1], [1, 0]]
return = []

The two tasks depend on each other, so no valid topological order exists.

Constraints
  • 0 <= before, after < numTasks
  • Use topological sorting with cycle detection.
  • When multiple tasks have in-degree zero, choose the smallest task id first.
More Netflix problems
drafts saved locally
public int[] findTaskOrder(int numTasks, int[][] edges) {
  // write your code here
}
numTasks4
edges[[0, 1], [0, 2], [1, 3], [2, 3]]
expected[0, 1, 2, 3]
checking account