18. Course Schedule II

Q: Why does Kahn's produce a valid topological order?

Because we only emit a node when all its prerequisites are already emitted (in-degree dropped to 0). The output is therefore a linearization of the DAG.

Q: How do I make the order reproducible across runs?

Use a min-heap keyed by node id instead of a FIFO queue. Two nodes with in-degree 0 are then ordered deterministically. Foundry does this so builds emit identical task IDs every time.

mediumAsked at Palantir

Return the order in which you should take courses to finish them all; if impossible, return []. Palantir asks this as the natural follow-up to cycle detection — the actual execution order is what their Foundry scheduler emits when it serializes an ETL DAG into a runnable task list.

By Alex Chen, Founder, InterviewChamp.AI · Last verified 2026-05-20

Source citations

Public interview reports confirming this problem appears in Palantir loops.

Glassdoor (2026-Q1)— Palantir FDE — frame: 'return the execution plan, not just feasibility'.
Blind (2025-12)— Reported as Course Schedule's direct follow-up at the same interview.

Problem

There are a total of numCourses courses you have to take, labeled from 0 to numCourses - 1. You are given an array prerequisites where prerequisites[i] = [ai, bi] indicates you must take course bi first if you want to take course ai. Return the ordering of courses you should take to finish all courses. If there are many valid answers, return any of them. If it is impossible to finish all courses, return an empty array.

Constraints

1 <= numCourses <= 2000
0 <= prerequisites.length <= numCourses * (numCourses - 1)
prerequisites[i].length == 2
0 <= ai, bi < numCourses
ai != bi
All the pairs [ai, bi] are distinct.

Examples

Example 1

Input

numCourses = 2, prerequisites = [[1,0]]

Output

[0,1]

Example 2

Input

numCourses = 4, prerequisites = [[1,0],[2,0],[3,1],[3,2]]

Output

[0,2,1,3]

Explanation: Or [0,1,2,3] — both valid topological orders.

Example 3

Input

numCourses = 1, prerequisites = []

Output

[0]

Approaches

1. DFS postorder reversal

DFS the graph; emit each node after all its descendants. Reverse the emission order. Detect cycles via the gray-state check.

Time: O(V + E)
Space: O(V + E)

function findOrder(numCourses, prerequisites) {
  const graph = Array.from({length: numCourses}, () => []);
  for (const [a, b] of prerequisites) graph[b].push(a);
  const WHITE = 0, GRAY = 1, BLACK = 2;
  const color = new Array(numCourses).fill(WHITE);
  const out = [];
  function dfs(u) {
    if (color[u] === GRAY) return false;
    if (color[u] === BLACK) return true;
    color[u] = GRAY;
    for (const v of graph[u]) if (!dfs(v)) return false;
    color[u] = BLACK;
    out.push(u);
    return true;
  }
  for (let i = 0; i < numCourses; i++) if (!dfs(i)) return [];
  return out.reverse();
}

Tradeoff: Concise but recursive; deep DAGs may overflow the stack. The reversal step is the gotcha.

2. Kahn's algorithm (BFS topological sort)

Standard Kahn's: zero-in-degree queue, decrement neighbors, append to output. If output has fewer than numCourses nodes, there's a cycle.

Time: O(V + E)
Space: O(V + E)

function findOrder(numCourses, prerequisites) {
  const graph = Array.from({length: numCourses}, () => []);
  const inDegree = new Array(numCourses).fill(0);
  for (const [a, b] of prerequisites) {
    graph[b].push(a);
    inDegree[a]++;
  }
  const queue = [];
  for (let i = 0; i < numCourses; i++) if (inDegree[i] === 0) queue.push(i);
  const order = [];
  while (queue.length) {
    const u = queue.shift();
    order.push(u);
    for (const v of graph[u]) {
      if (--inDegree[v] === 0) queue.push(v);
    }
  }
  return order.length === numCourses ? order : [];
}

Tradeoff: Iterative, naturally emits in order, no reversal. The exact algorithm Palantir's scheduler uses internally. This is the canonical answer they're testing for.

Palantir-specific tips

Palantir wants Kahn's by name and the connection to scheduling specifically. State the invariant: a node enters the output only after all its dependencies have been emitted, so the resulting list is a valid execution order. Bonus signal: mention that if you need a DETERMINISTIC order (for reproducible builds), replace the FIFO queue with a min-heap keyed by node id — the same trick Foundry uses to make build outputs reproducible across runs.

Common mistakes

Returning the DFS postorder WITHOUT reversing — that's the wrong direction.
Returning a partial order when a cycle is detected — must return [], not the prefix.
Using queue.shift() in a hot loop with millions of edges — O(n) per shift; switch to a head-pointer or proper deque.

Follow-up questions

An interviewer at Palantir may pivot to one of these next:

What if you want the lexicographically smallest order? Use a min-heap instead of a queue.
What if some courses have a duration? Compute the minimum total time (LC 1136-style, parallel scheduling).
What if dependencies arrive online? Incremental topo sort — much harder.

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

FAQ

Why does Kahn's produce a valid topological order?

Because we only emit a node when all its prerequisites are already emitted (in-degree dropped to 0). The output is therefore a linearization of the DAG.

How do I make the order reproducible across runs?

Use a min-heap keyed by node id instead of a FIFO queue. Two nodes with in-degree 0 are then ordered deterministically. Foundry does this so builds emit identical task IDs every time.

Practice these live with InterviewChamp.AI

Drill Course Schedule II and other Palantir interview questions under real-loop conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →