Compute task order with prerequisites
Company: Snowflake
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: Medium
Interview Round: Technical Screen
Given an integer n representing tasks labeled 0..n-1 and a list of prerequisite pairs (a, b) meaning b must be completed before a, return any valid ordering of tasks that completes all tasks, or an empty list if no ordering exists. Design an efficient algorithm and data structures, explain how you detect cycles, and analyze time and space complexity. Follow-ups:
(
1) How would you produce all tasks that are part of at least one cycle?
(
2) How would you handle up to 100,000 tasks and 200,000 prerequisites?
Quick Answer: This question evaluates proficiency in graph algorithms—particularly topological ordering and cycle detection—along with the use of efficient data structures for representing dependencies and analyzing time and space complexity.
You are given an integer `n` representing tasks labeled `0` through `n - 1`, and a list of prerequisite pairs `prerequisites`, where each pair `[a, b]` means task `b` must be completed before task `a`.
Return any valid ordering of all `n` tasks such that every prerequisite is respected. If no such ordering exists (i.e. the prerequisite graph contains a cycle), return an empty list.
This is the classic topological sort problem (LeetCode 210, Course Schedule II). Model each task as a node and each pair `[a, b]` as a directed edge `b -> a`. A valid ordering is a topological order of this directed graph, which exists if and only if the graph is a DAG (no cycle).
**Approach (Kahn's algorithm / BFS):** Build an adjacency list and an indegree count for every node. Seed a queue with all nodes whose indegree is `0`. Repeatedly pop a node, append it to the output order, and decrement the indegree of each of its neighbors; when a neighbor's indegree drops to `0`, enqueue it. If the output contains all `n` nodes, it is a valid ordering; otherwise a cycle exists and we return `[]`.
The implementation here seeds and re-enqueues zero-indegree nodes in ascending label order, so it returns a stable, deterministic topological ordering.
**Follow-up 1 (tasks in a cycle):** The nodes left with indegree `> 0` after Kahn's algorithm terminates are exactly those that cannot be scheduled — every node in a cycle, plus any node reachable only through a cycle. To get *only* the nodes on at least one cycle, run Tarjan's/Kosaraju's strongly connected components and report every SCC of size `> 1`, plus any self-loop.
**Follow-up 2 (scale to 100k tasks / 200k edges):** Kahn's algorithm is `O(V + E)` time and `O(V + E)` space, which handles 100,000 tasks and 200,000 edges comfortably. Use adjacency lists (not an adjacency matrix, which would need 10^10 cells) and an iterative BFS/DFS to avoid recursion-depth limits.
Constraints
- 1 <= n <= 100000
- 0 <= prerequisites.length <= 200000
- prerequisites[i] = [a, b] with 0 <= a, b < n and a != b
- Pairs may be duplicated; the algorithm still terminates correctly (duplicates just inflate indegree consistently).
- Return any one valid ordering; if multiple exist, all are accepted.
Examples
Input: (2, [[1, 0]])
Expected Output: [0, 1]
Explanation: Task 0 must come before task 1, so the only valid order is [0, 1].
Input: (4, [[1, 0], [2, 0], [3, 1], [3, 2]])
Expected Output: [0, 1, 2, 3]
Explanation: Diamond dependency: 0 unlocks 1 and 2, and both 1 and 2 must precede 3. Processing zero-indegree nodes in ascending order yields [0, 1, 2, 3].
Input: (2, [[1, 0], [0, 1]])
Expected Output: []
Explanation: 0 requires 1 and 1 requires 0 — a 2-cycle. No node ever reaches indegree 0, so no valid ordering exists; return [].
Input: (1, [])
Expected Output: [0]
Explanation: A single task with no prerequisites; the only order is [0].
Input: (3, [])
Expected Output: [0, 1, 2]
Explanation: Three independent tasks with no prerequisites; all have indegree 0 and are emitted in ascending label order.
Input: (3, [[1, 0], [2, 1], [0, 2]])
Expected Output: []
Explanation: 0 -> 1 -> 2 -> 0 forms a 3-cycle, so every node has indegree >= 1 and none can be scheduled; return [].
Hints
- Model it as a directed graph: pair [a, b] ("b before a") is an edge b -> a. A valid task order is a topological order of this graph.
- Use Kahn's algorithm: compute every node's indegree, start from all indegree-0 nodes, and peel them off one at a time, decrementing neighbors' indegrees.
- Detect a cycle by counting how many nodes you successfully output. If fewer than n nodes are scheduled, the remaining nodes form (or depend on) a cycle, so return an empty list.
- Prefer an adjacency list and iterative BFS over recursion or an adjacency matrix so the solution scales to 100,000 nodes and 200,000 edges in O(V + E).