Determine task order with prerequisites
Company: Adobe
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
You are given n tasks labeled 0..n−1 and a list of prerequisite pairs (a, b) meaning task b must be completed before task a. Determine one valid order in which to complete all tasks, or report that it is impossible if dependencies contain a cycle. Describe the algorithm, data structures, and complexity, and explain how you would detect cycles and handle multiple valid orders.
Quick Answer: This question evaluates a candidate's proficiency with graph-theoretic concepts like dependency modeling and cycle detection, and their ability to produce valid task orderings under constraints within the Coding & Algorithms domain.
You are given an integer `n` representing tasks labeled `0` to `n-1`, and a list of prerequisite pairs `prerequisites` where each pair `[a, b]` means task `b` must be completed before task `a`.
Return one valid order in which all tasks can be completed. If the dependencies contain a cycle (making a valid ordering impossible), return an empty list.
This is a topological sort. When multiple valid orderings exist, return the one that is lexicographically smallest (always pick the smallest-labeled task among those whose prerequisites are all satisfied), so the answer is deterministic.
Example:
- `n = 4`, `prerequisites = [[1,0],[2,0],[3,1],[3,2]]` -> `[0, 1, 2, 3]` (task 0 first, then 1 and 2, then 3).
- `n = 2`, `prerequisites = [[0,1],[1,0]]` -> `[]` (cycle: 0 needs 1 and 1 needs 0).
Constraints
- 0 <= n <= 10^5
- 0 <= prerequisites.length <= 10^5
- prerequisites[i] = [a, b] with 0 <= a, b < n
- A pair [a, b] means b must be completed before a
- Return [] if the prerequisite graph contains a cycle
Examples
Input: (4, [[1, 0], [2, 0], [3, 1], [3, 2]])
Expected Output: [0, 1, 2, 3]
Explanation: Task 0 has no prerequisites, so it goes first. Tasks 1 and 2 both depend only on 0; the smaller label 1 comes before 2. Task 3 depends on both 1 and 2, so it goes last.
Input: (2, [[1, 0]])
Expected Output: [0, 1]
Explanation: Task 1 requires task 0 first, giving the single valid order [0, 1].
Hints
- Model tasks as nodes in a directed graph. For each pair [a, b], task b must come before a, so add a directed edge b -> a and increment the in-degree of a.
- Use Kahn's algorithm (BFS topological sort): repeatedly take a task whose in-degree is 0, append it to the order, and decrement the in-degree of its dependents, adding any that reach 0.
- A cycle exists exactly when you cannot place all n tasks (the final order has fewer than n elements). In that case return an empty list.
- To make the result deterministic among multiple valid orderings, pick the smallest available task each step using a min-heap (priority queue) instead of a plain queue.