Find a Valid Task Execution Order with Dependencies
Company: Salesforce
Role: Software Engineer
Category: Coding & Algorithms
Interview Round: Onsite
You are building the task scheduler for a CI/build system. There are `n` build tasks labeled from `0` to `n - 1`. Some tasks cannot start until certain other tasks have finished.
The dependencies are given as a list of pairs `dependencies`, where each pair `[a, b]` means **task `a` depends on task `b`** — that is, task `b` must be completed *before* task `a` can start.
Return **any valid order** in which all `n` tasks can be executed so that every dependency is respected. If it is impossible to finish all tasks (because the dependencies contain a cycle), return an **empty list**.
If there are multiple valid orderings, returning any one of them is accepted.
### Input
- `n`: an integer, the number of tasks (tasks are labeled `0 .. n - 1`).
- `dependencies`: a list of pairs `[a, b]`, each meaning task `a` requires task `b` to be finished first.
### Output
- A list of `n` distinct integers — a valid execution order of all tasks — or an empty list `[]` if no valid order exists.
### Examples
**Example 1**
```
Input: n = 2, dependencies = [[1, 0]]
Output: [0, 1]
Explanation: Task 1 depends on task 0, so task 0 must run first.
```
**Example 2**
```
Input: n = 4, dependencies = [[1, 0], [2, 0], [3, 1], [3, 2]]
Output: [0, 1, 2, 3]
Explanation: Task 0 has no dependencies and runs first. Tasks 1 and 2 each
depend only on task 0. Task 3 depends on both 1 and 2, so it runs last.
[0, 2, 1, 3] would also be accepted.
```
**Example 3**
```
Input: n = 2, dependencies = [[1, 0], [0, 1]]
Output: []
Explanation: Task 0 and task 1 depend on each other, forming a cycle, so no
valid order exists.
```
### Constraints
- `1 <= n <= 10^5`
- `0 <= len(dependencies) <= 10^5`
- `dependencies[i].length == 2`
- `0 <= a, b < n` and `a != b`
- All pairs `[a, b]` in `dependencies` are distinct.
Quick Answer: This question evaluates a candidate's ability to model dependency relationships as a directed graph and produce a valid ordering of nodes. It tests knowledge of topological sorting and cycle detection, skills commonly assessed in coding interviews to gauge graph traversal and algorithmic reasoning. The task reflects practical application of graph theory to scheduling-style problems.
You are building the task scheduler for a CI/build system. There are `n` build tasks labeled from `0` to `n - 1`. Some tasks cannot start until certain other tasks have finished.
The dependencies are given as a list of pairs `dependencies`, where each pair `[a, b]` means **task `a` depends on task `b`** — that is, task `b` must be completed *before* task `a` can start.
Return **any valid order** in which all `n` tasks can be executed so that every dependency is respected. If it is impossible to finish all tasks (because the dependencies contain a cycle), return an **empty list**.
If there are multiple valid orderings, returning any one of them is accepted. (This checker uses the smallest-numbered-available-task-first ordering to make outputs deterministic, so implementing Kahn's algorithm with a min-heap will match the expected results exactly.)
### Input
- `n`: an integer, the number of tasks (tasks are labeled `0 .. n - 1`).
- `dependencies`: a list of pairs `[a, b]`, each meaning task `a` requires task `b` to be finished first.
### Output
- A list of `n` distinct integers — a valid execution order of all tasks — or an empty list `[]` if no valid order exists.
### Examples
**Example 1**
```
Input: n = 2, dependencies = [[1, 0]]
Output: [0, 1]
Explanation: Task 1 depends on task 0, so task 0 must run first.
```
**Example 2**
```
Input: n = 4, dependencies = [[1, 0], [2, 0], [3, 1], [3, 2]]
Output: [0, 1, 2, 3]
Explanation: Task 0 has no dependencies and runs first. Tasks 1 and 2 each
depend only on task 0. Task 3 depends on both 1 and 2, so it runs last.
```
**Example 3**
```
Input: n = 2, dependencies = [[1, 0], [0, 1]]
Output: []
Explanation: Task 0 and task 1 depend on each other, forming a cycle, so no
valid order exists.
```
### Constraints
- `1 <= n <= 10^5`
- `0 <= len(dependencies) <= 10^5`
- `dependencies[i].length == 2`
- `0 <= a, b < n` and `a != b`
- All pairs `[a, b]` in `dependencies` are distinct.
Constraints
- 1 <= n <= 10^5
- 0 <= len(dependencies) <= 10^5
- dependencies[i].length == 2
- 0 <= a, b < n and a != b
- All pairs [a, b] are distinct
Examples
Input: (2, [[1, 0]])
Expected Output: [0, 1]
Explanation: Task 1 depends on task 0, so 0 runs first.
Input: (4, [[1, 0], [2, 0], [3, 1], [3, 2]])
Expected Output: [0, 1, 2, 3]
Explanation: 0 has no dependency; 1 and 2 depend on 0; 3 depends on both 1 and 2, so it runs last.
Input: (2, [[1, 0], [0, 1]])
Expected Output: []
Explanation: Tasks 0 and 1 depend on each other, forming a cycle, so no valid order exists.
Input: (1, [])
Expected Output: [0]
Explanation: A single task with no dependencies runs by itself.
Input: (3, [])
Expected Output: [0, 1, 2]
Explanation: No dependencies, so any order works; the smallest-first order is 0, 1, 2.
Input: (3, [[0, 1], [1, 2], [2, 0]])
Expected Output: []
Explanation: 0 -> 1 -> 2 -> 0 forms a 3-cycle, so scheduling is impossible.
Input: (5, [[4, 3], [3, 2], [2, 1], [1, 0]])
Expected Output: [0, 1, 2, 3, 4]
Explanation: A strict chain 0 before 1 before 2 before 3 before 4.
Input: (6, [[1, 0], [2, 0], [3, 1], [4, 2], [5, 3], [5, 4]])
Expected Output: [0, 1, 2, 3, 4, 5]
Explanation: A diamond-shaped DAG; smallest-available-first gives 0,1,2,3,4,5.
Hints
- Model this as a directed graph: for each pair [a, b], task b must come before task a, so add an 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 neighbors, pushing any that hit 0.
- If the produced order contains fewer than n tasks, the graph has a cycle, so return an empty list. Using a min-heap instead of a plain queue yields the lexicographically smallest valid order deterministically.