Determine feasible task ordering
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 dependency pairs (a, b) meaning task a requires task b to be completed first. Implement functions to
(
1) determine whether all tasks can be completed and
(
2) return any valid execution order if it exists. Analyze time and space complexity and discuss how your solution behaves on large sparse versus dense dependency graphs.
Quick Answer: This question evaluates knowledge of graph algorithms and dependency management, emphasizing concepts such as topological ordering and cycle detection and the ability to determine feasibility and produce a valid execution sequence.
You are given `n` tasks labeled `0..n-1` and a list of dependency pairs `(a, b)`, where each pair means task `a` requires task `b` to be completed first.
Implement a function `taskOrder(n, dependencies)` that returns **any valid execution order** of all tasks if one exists, or an **empty list** if it is impossible to complete all tasks (i.e., the dependencies contain a cycle).
The returned list both answers part (1) — all tasks can be completed **iff** the returned list is non-empty (or `n == 0`) — and part (2) — the list itself is a valid order.
**Approach:** Model the tasks as a directed graph with an edge `b -> a` for every pair `(a, b)` (b must come before a). Run Kahn's algorithm (BFS topological sort): repeatedly pick a task with in-degree 0, append it to the order, and decrement the in-degree of its dependents. If you emit all `n` tasks, the order is valid; otherwise a cycle exists and you return an empty list.
To make the output deterministic, seed the queue with the in-degree-0 tasks in ascending index order and always pop from the front (FIFO).
**Examples:**
- `n = 2`, `dependencies = [[1, 0]]` -> `[0, 1]` (task 1 needs task 0 first).
- `n = 4`, `dependencies = [[1, 0], [2, 0], [3, 1], [3, 2]]` -> `[0, 1, 2, 3]` (diamond).
- `n = 2`, `dependencies = [[1, 0], [0, 1]]` -> `[]` (mutual dependency cycle).
**Complexity on sparse vs. dense graphs:** Let `V = n` and `E = len(dependencies)`. The algorithm is `O(V + E)` time and `O(V + E)` space. On a large **sparse** graph (`E` close to `V`) it is effectively linear in the number of tasks and very memory-light. On a **dense** graph (`E` close to `V^2`, e.g. a near-total ordering) both adjacency storage and the per-edge in-degree decrements grow quadratically, so time and space are dominated by `E ~ V^2`; an adjacency-matrix variant would waste `O(V^2)` space even when sparse, which is why an adjacency list is preferred.
Constraints
- 1 <= n <= 10^5
- 0 <= len(dependencies) <= 10^5
- Each dependency is a pair [a, b] with 0 <= a, b < n and a != b
- There may be duplicate dependency pairs; the answer must still be a valid topological order
- Return an empty list when the tasks cannot all be completed (the dependency graph has a cycle)
Examples
Input: (2, [[1, 0]])
Expected Output: [0, 1]
Explanation: Task 1 requires task 0 first, so 0 must precede 1.
Input: (4, [[1, 0], [2, 0], [3, 1], [3, 2]])
Expected Output: [0, 1, 2, 3]
Explanation: Diamond DAG: 0 is the root, 1 and 2 depend on 0, and 3 depends on both 1 and 2. Kahn's algorithm in ascending order yields 0,1,2,3.
Hints
- Build a directed graph where the edge points from the prerequisite to the dependent: for pair (a, b), add b -> a. Then any task with in-degree 0 has no remaining prerequisites and can run now.
- Use Kahn's algorithm (BFS topological sort): start from all in-degree-0 tasks, and each time you 'complete' a task, decrement the in-degree of its dependents and enqueue any that reach 0.
- If you manage to output fewer than n tasks, some tasks are stuck in a cycle and can never be completed — return an empty list. For deterministic output, seed and process the queue in ascending index order.