Deterministic Task Execution Order
Company: Google
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: easy
Interview Round: Onsite
## Deterministic Task Execution Order
A build system runs `n` tasks labeled `0, 1, ..., n - 1`. Some tasks depend on others: a dependency `[a, b]` means task `a` must finish **before** task `b` can start. You must produce an order in which every task can be executed so that all dependencies are respected.
Because many valid orders may exist, the build system requires a **unique, deterministic** order: whenever more than one task is ready to run (all of its prerequisites are already done), always run the ready task with the **smallest label** next.
Write a function that takes:
- `n` (the number of tasks, labeled `0` through `n - 1`), and
- `edges`: a list of dependency pairs `[a, b]` meaning `a` must come before `b`,
and returns a list of all `n` task labels giving the deterministic valid order described above. If the dependencies contain a cycle (no valid order exists), return an empty list `[]`.
### Notes and edge cases
- A task with no dependencies is ready from the start.
- The input may contain duplicate edges; treat a repeated `[a, b]` the same as a single `[a, b]`.
- You may assume every label in `edges` is in the range `[0, n - 1]`.
- If `n == 0`, return `[]`.
### Example
```
n = 6
edges = [[5, 2], [5, 0], [4, 0], [4, 1], [2, 3], [3, 1]]
# In-degree 0 at start: {0? no(5,4), 1? no, 2? no(5), 3? no(2), 4 yes, 5 yes}
# Ready = {4, 5} -> pick smallest -> 4. Now 4 done.
# Ready = {5} (0 still needs 5; 1 still needs 4 done but also 3) -> pick 5.
# After 5: 2 ready (needs 5), 0 ready (needs 5 and 4, both done). Ready = {0, 2} -> pick 0.
# Ready = {2} -> pick 2. Then 3 ready -> pick 3. Then 1 ready -> pick 1.
# Output: [4, 5, 0, 2, 3, 1]
```
If instead `edges = [[0, 1], [1, 2], [2, 0]]`, the three tasks form a cycle, so the output is `[]`.
Quick Answer: This question evaluates a candidate's ability to model task dependencies as a directed graph and produce a valid execution order, a core graph algorithms and coding topic. It tests topological sorting combined with tie-breaking logic to select the smallest-label ready task, plus cycle detection when no valid order exists. This is a practical application question commonly used to assess algorithmic problem-solving in coding interviews.
A build system runs `n` tasks labeled `0, 1, ..., n - 1`. Some tasks depend on others: a dependency `[a, b]` means task `a` must finish **before** task `b` can start. Produce an order in which every task can be executed so that all dependencies are respected.
Because many valid orders may exist, the build requires a **unique, deterministic** order: whenever more than one task is ready (all of its prerequisites are done), always run the ready task with the **smallest label** next.
Write a function taking:
- `n` (number of tasks, labeled `0` through `n - 1`), and
- `edges`: a list of dependency pairs `[a, b]` meaning `a` must come before `b`,
and returning a list of all `n` task labels giving that deterministic valid order. If the dependencies contain a cycle (no valid order exists), return an empty list `[]`.
**Notes / edge cases**
- A task with no dependencies is ready from the start.
- The input may contain duplicate edges; treat a repeated `[a, b]` the same as a single `[a, b]`.
- Every label in `edges` is in the range `[0, n - 1]`.
- If `n == 0`, return `[]`.
**Example**
```
n = 6
edges = [[5, 2], [5, 0], [4, 0], [4, 1], [2, 3], [3, 1]]
# Ready = {4, 5} -> 4; then 5; then {0, 2} -> 0; then 2; then 3; then 1
# Output: [4, 5, 0, 2, 3, 1]
```
With `edges = [[0, 1], [1, 2], [2, 0]]` the three tasks form a cycle, so the output is `[]`.
Constraints
- 0 <= n <= 10^5
- 0 <= edges.length <= 2 * 10^5
- edges[i] == [a, b] with 0 <= a, b <= n - 1
- Edges may be duplicated; a self-loop [a, a] would form a cycle.
- Return [] when a valid ordering does not exist (a cycle) or when n == 0.
Examples
Input: (6, [[5, 2], [5, 0], [4, 0], [4, 1], [2, 3], [3, 1]])
Expected Output: [4, 5, 0, 2, 3, 1]
Explanation: Ready = {4,5} -> pick 4; ready = {5} -> pick 5; now 0 and 2 unlock, ready = {0,2} -> pick 0; then 2, which unlocks 3; then 1. The smallest-label rule breaks each tie.
Input: (3, [[0, 1], [1, 2], [2, 0]])
Expected Output: []
Explanation: 0 -> 1 -> 2 -> 0 is a cycle: every task always has an unfinished prerequisite, so no task ever reaches in-degree 0 and the result is [].
Input: (0, [])
Expected Output: []
Explanation: There are no tasks, so the deterministic order is the empty list.
Input: (1, [])
Expected Output: [0]
Explanation: A single task with no prerequisites is ready immediately.
Input: (3, [])
Expected Output: [0, 1, 2]
Explanation: With no dependencies all three tasks are ready from the start, so the smallest-label rule outputs them in ascending order.
Input: (3, [[0, 1], [0, 1], [0, 2]])
Expected Output: [0, 1, 2]
Explanation: The duplicate [0, 1] must be treated as one edge; if it double-counted 1's in-degree, task 1 would never unlock. 0 runs first, then 1 and 2 in ascending order.
Input: (4, [[3, 0], [3, 1], [0, 2], [1, 2]])
Expected Output: [3, 0, 1, 2]
Explanation: Only 3 starts ready; finishing 3 unlocks {0,1} -> pick 0 then 1; 2 needs both 0 and 1, so it runs last.
Hints
- This is topological sorting. Compute each task's in-degree (number of unfinished prerequisites) and start with every task whose in-degree is 0.
- To always pick the smallest ready label, keep the ready set in a min-heap (priority queue) instead of a plain FIFO queue — a plain BFS queue gives *a* valid order but not the deterministic smallest-label one.
- When you finish a task, decrement the in-degree of each successor; push a successor onto the heap the moment its in-degree hits 0.
- If you finish fewer than n tasks, some tasks were stuck in a cycle — return an empty list. De-duplicate edges (or use a set of successors) so a repeated [a, b] does not over-count an in-degree.