Skip to main content

27. Course Schedule

mediumAsked at Booking

Detect a cycle in a dependency graph — Booking's platform team applies topological-sort cycle detection when validating that hotel amenity feature flags have no circular dependencies in their configuration graph.

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

Problem

There are numCourses courses labeled 0 to numCourses - 1. You are given an array prerequisites where prerequisites[i] = [a, b] means you must take course b before a. Return true if you can finish all courses (no circular dependency).

Constraints

  • 1 <= numCourses <= 2000
  • 0 <= prerequisites.length <= 5000
  • prerequisites[i].length == 2
  • All prerequisite pairs are unique

Examples

Example 1

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

Explanation: Take 0, then 1 — no cycle.

Example 2

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

Explanation: 0 requires 1 and 1 requires 0 — cycle.

Approaches

1. DFS cycle detection (coloring)

Three-color DFS: white (unvisited), grey (in-progress), black (done). A grey node encountered during DFS means a cycle.

Time
O(V + E)
Space
O(V + E)
function canFinish(numCourses, prerequisites) {
  const graph = Array.from({ length: numCourses }, () => []);
  for (const [a, b] of prerequisites) graph[b].push(a);

  const state = new Array(numCourses).fill(0); // 0=white,1=grey,2=black

  function dfs(node) {
    if (state[node] === 1) return false; // cycle
    if (state[node] === 2) return true;  // already processed
    state[node] = 1;
    for (const next of graph[node]) {
      if (!dfs(next)) return false;
    }
    state[node] = 2;
    return true;
  }

  for (let i = 0; i < numCourses; i++) {
    if (!dfs(i)) return false;
  }
  return true;
}

Tradeoff:

2. BFS topological sort (Kahn's algorithm)

Count in-degrees; enqueue zero-in-degree nodes; process and reduce neighbour in-degrees. If all nodes are processed, no cycle exists.

Time
O(V + E)
Space
O(V + E)
function canFinish(numCourses, prerequisites) {
  const inDeg = new Array(numCourses).fill(0);
  const graph = Array.from({ length: numCourses }, () => []);

  for (const [a, b] of prerequisites) {
    graph[b].push(a);
    inDeg[a]++;
  }

  const queue = [];
  for (let i = 0; i < numCourses; i++) {
    if (inDeg[i] === 0) queue.push(i);
  }

  let processed = 0;
  while (queue.length) {
    const node = queue.shift();
    processed++;
    for (const next of graph[node]) {
      inDeg[next]--;
      if (inDeg[next] === 0) queue.push(next);
    }
  }

  return processed === numCourses;
}

Tradeoff:

Booking-specific tips

Booking runs A/B experiments with feature-flag dependency trees — cycle detection in a DAG is a live operational concern for them. Know both DFS and Kahn's; interviewers sometimes ask which scales better for very wide, shallow dependency graphs (Kahn's queue is more cache-friendly).

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 Booking interview questions under real-loop conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →