210. Course Schedule II
mediumAsked at CiscoCourse Schedule II at Cisco is the natural follow-up to Course Schedule — instead of returning true/false for satisfiability, you return the actual topological order. The interviewer is checking whether you reach for Kahn's algorithm because the dequeue order IS the topological order.
By Alex Chen, Founder, InterviewChamp.AI · Last verified
Source citations
Public interview reports confirming this problem appears in Cisco loops.
- Glassdoor (2026-Q1)— Cisco SDE-II onsite reports list Course Schedule II as a 30-minute graph round, often as an extension after Course Schedule.
- Blind (2025-09)— Cisco interview thread cites this as the canonical topological-sort question.
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 that 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 <= 20000 <= prerequisites.length <= numCourses * (numCourses - 1)prerequisites[i].length == 20 <= ai, bi < numCoursesai != biAll the pairs are distinct.
Examples
Example 1
numCourses = 2, prerequisites = [[1,0]][0,1]Example 2
numCourses = 4, prerequisites = [[1,0],[2,0],[3,1],[3,2]][0,2,1,3]Explanation: Multiple valid orders exist; e.g., [0,1,2,3] also works.
Example 3
numCourses = 1, prerequisites = [][0]Approaches
1. DFS post-order with cycle detection
Do a DFS three-color cycle check (same as Course Schedule I). When a node finishes (all descendants processed), prepend it to the result. The reverse post-order is a topological order.
- Time
- O(V + E)
- Space
- O(V + E)
function findOrderDFS(numCourses, prereqs) {
const graph = Array.from({ length: numCourses }, () => []);
for (const [a, b] of prereqs) graph[a].push(b);
const WHITE = 0, GRAY = 1, BLACK = 2;
const color = new Array(numCourses).fill(WHITE);
const result = [];
function dfs(node) {
if (color[node] === GRAY) return false;
if (color[node] === BLACK) return true;
color[node] = GRAY;
for (const next of graph[node]) {
if (!dfs(next)) return false;
}
color[node] = BLACK;
result.push(node);
return true;
}
for (let i = 0; i < numCourses; i++) {
if (!dfs(i)) return [];
}
return result;
}Tradeoff: The trick: since we built edges a -> b meaning 'a depends on b', the DFS finishes b BEFORE a — so post-order push gives us prerequisites-first ordering directly (no reverse needed). If you built edges the other direction (b -> a), you'd need to reverse the result.
2. Kahn's algorithm (optimal, iterative)
Compute in-degrees. Push all in-degree-zero nodes to a queue. Dequeue, append to result, decrement in-degree of neighbors, push any that hit zero. If you process fewer than numCourses nodes, there was a cycle.
- Time
- O(V + E)
- Space
- O(V + E)
function findOrder(numCourses, prereqs) {
const graph = Array.from({ length: numCourses }, () => []);
const indeg = new Array(numCourses).fill(0);
for (const [a, b] of prereqs) {
graph[b].push(a);
indeg[a]++;
}
const queue = [];
for (let i = 0; i < numCourses; i++) if (indeg[i] === 0) queue.push(i);
const result = [];
while (queue.length) {
const node = queue.shift();
result.push(node);
for (const next of graph[node]) {
if (--indeg[next] === 0) queue.push(next);
}
}
return result.length === numCourses ? result : [];
}Tradeoff: Iterative — no recursion depth worries. The dequeue order IS the topological order, which is the entire algorithm. Cisco interviewers prefer this for Course Schedule II because the result accumulates naturally as you process.
Cisco-specific tips
Cisco interviewers prefer Kahn's for this problem specifically because the output accumulates AS YOU GO — no post-processing, no reversal, no separate result array on the recursion. State out loud: 'I use Kahn's because the order I dequeue nodes IS the topological order — so I just append to result as I dequeue.' That sentence is the entire interview signal.
Common mistakes
- Building edges in the wrong direction — `[a, b]` means b is a prereq of a, so the dependency edge goes b -> a (Kahn's wants you traversing FROM prereqs TO dependents).
- Forgetting the cycle-detection final check (`result.length === numCourses`) — without it, you return a partial order on cyclic input.
- Using DFS but pushing nodes ON ENTRY instead of on EXIT — that gives reverse topological order, not topological order.
Follow-up questions
An interviewer at Cisco may pivot to one of these next:
- Alien Dictionary (LC 269) — topological sort on derived character ordering.
- Minimum Height Trees (LC 310) — repeatedly peel leaves (degree-1 nodes), same flavor.
- Parallel Courses (LC 1136) — minimum number of semesters; Kahn's with level tracking.
- What if multiple valid orders exist and you want the lex-smallest? (Use a min-heap instead of a queue.)
Solve it now
Free. No sign-up. Python and JavaScript run instantly in your browser.
FAQ
Why is Kahn's preferred over DFS here?
Three reasons. (1) The dequeue order IS the topological order — no post-processing. (2) It's iterative, no recursion depth concerns. (3) The cycle check is built in: if the loop ends with fewer nodes processed than numCourses, you had a cycle. DFS works but requires careful 'push on exit, not on entry' discipline to get the order right.
Are there multiple valid orderings?
Yes. Any topological sort of a DAG is valid. LeetCode accepts any one. If the interviewer asks 'why might two engineers produce different orders?' the answer is 'because they start from different in-degree-zero nodes — Kahn's queue order depends on insertion order.'
Free learning resources
Curated free links for this problem.
Practice these live with InterviewChamp.AI
Drill Course Schedule II and other Cisco interview questions under real-loop conditions with instant feedback on your reasoning, complexity claims, and code.
Practice these live with InterviewChamp.AI →