Skip to main content

19. Course Schedule

mediumAsked at Activision

Decide if a set of courses with prerequisites is schedulable — Activision uses this to gauge cycle-detection in directed graphs before chat-moderation dependency-chain questions.

By Alex Chen, Founder, InterviewChamp.AI · Last verified

Problem

Given numCourses and a list of prerequisite pairs [a, b] meaning take b before a, return true if you can finish all courses. Equivalent to detecting a cycle in a directed graph.

Constraints

  • 1 <= numCourses <= 2000
  • 0 <= prerequisites.length <= 5000
  • All pairs distinct

Examples

Example 1

Input
numCourses=2, prerequisites=[[1,0]]
Output
true

Example 2

Input
numCourses=2, prerequisites=[[1,0],[0,1]]
Output
false

Approaches

1. DFS three-color

Mark nodes white/gray/black; if DFS revisits a gray node, cycle exists.

Time
O(V+E)
Space
O(V+E)
// recurse from each white node; gray on entry, black on exit

Tradeoff:

2. Kahn's BFS topological sort

Maintain in-degrees; repeatedly pop zero-in-degree nodes. If you can pop all nodes, no cycle exists.

Time
O(V+E)
Space
O(V+E)
function canFinish(n, prereq) {
  const adj = Array.from({length:n}, () => []);
  const indeg = new Array(n).fill(0);
  for (const [a,b] of prereq) { adj[b].push(a); indeg[a]++; }
  const q = [];
  for (let i=0;i<n;i++) if (!indeg[i]) q.push(i);
  let taken = 0;
  while (q.length) {
    const c = q.shift();
    taken++;
    for (const nx of adj[c]) if (--indeg[nx] === 0) q.push(nx);
  }
  return taken === n;
}

Tradeoff:

Activision-specific tips

Activision prefers Kahn's topo sort here because it scales cleanly to live moderation pipelines where you flag dependency cycles in escalation rules.

Solve it now

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

Output

Press Run or Cmd+Enter to execute

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →