Topological Sort / Course Schedule for Ads

Requirements

• Input: a set of tasks / courses / ads-processing jobs and prerequisite pairs before -> after.
• Return either whether all tasks can be completed, one valid execution order, or all valid execution orders depending on the variant.
• Detect cycles and explain what should be returned when a cycle exists.
• Follow-up: sort multiple valid results deterministically, usually lexicographically or by original input order.
• Follow-up: print all valid topological orders and state the exponential worst-case runtime.
• Follow-up: parallel courses / batched execution, where all currently unblocked nodes can run together.

Examples

numTasks = 4
edges = [[0, 1], [0, 2], [1, 3], [2, 3]]
valid order = [0, 1, 2, 3] or [0, 2, 1, 3]
parallel batches = [[0], [1, 2], [3]]

Notes

• Kahn's algorithm is the cleanest default: build adjacency and in-degree, queue all in-degree-zero nodes, pop, decrement neighbors, and fail if visited count is smaller than n.
• DFS topo also works, but cycle-state bugs are easier under pressure. Use three colors: unvisited, visiting, visited.
• Deterministic ordering requires a min-heap or sorted queue instead of a plain FIFO queue.
• All-orders printing is backtracking over the current zero-in-degree set. The complexity is O(V + E) per emitted order, with up to factorially many outputs.
• Parallel-course follow-up returns BFS waves over zero-in-degree frontiers. If durations are introduced, the level duration is either the max duration in the current wave or a DAG longest-path calculation, depending on whether courses can start as soon as each prerequisite completes.
• A common L4 phone-screen framing gives each task an individual completion time and asks for the minimum time to finish every task. Solve it as a Kahn/BFS wave that propagates the longest finish-time along prerequisite chains (a DAG longest-path); detect cycles first, run your own tests, and be ready to describe the DFS-with-memo equivalent as the follow-up.
• The minimum-semesters framing (relations[i] = [prev, next], take any number of unblocked courses per semester, return the minimum semester count, -1 if a cycle exists) is just the wave count: run Kahn level by level and count levels; if the processed-node count is less than n, return -1.

Preparation### Alternate canonical variant — bounded courses per semester (≤ k)

A harder variant caps each semester at at most k courses (constraints are small, n ≤ 15). Greedy by in-degree is not optimal here — choosing which k of the currently-unblocked courses to take changes future semesters. Solve with bitmask DP over completed-course sets: dp[mask] = minimum semesters to reach mask; for each reachable mask, compute the set of courses whose prerequisites are all inside mask, then enumerate every size-≤k subset of that available set as the next semester. State space 2^n, transitions enumerate subsets of the available frontier.

• Implement Kahn's algorithm in 10 minutes with cycle detection and tests.
• Add a deterministic min-heap variant.
• Add allOrders() with backtracking and restore in-degree after each recursive branch.
• Practice explaining why all-orders is not polynomial in the output size.