Skip to main content

31. Course Schedule

mediumAsked at Expedia

Detect whether a set of task dependencies contains a cycle — Expedia's booking-pipeline team uses the same topological-sort check to verify that booking-step dependencies never create a deadlock.

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

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] = [a_i, b_i] indicates that you must take course b_i first if you want to take course a_i. Return true if you can finish all courses, otherwise return false.

Constraints

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

Examples

Example 1

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

Explanation: Course 0 first, then course 1. No cycle.

Example 2

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

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

Approaches

1. DFS cycle detection

For each unvisited node, run DFS tracking the current recursion path. If we revisit a node on the current path, a cycle exists.

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);

  // 0 = unvisited, 1 = in stack, 2 = done
  const state = new Array(numCourses).fill(0);

  function hasCycle(node) {
    if (state[node] === 1) return true;
    if (state[node] === 2) return false;
    state[node] = 1;
    for (const neighbor of graph[node]) {
      if (hasCycle(neighbor)) return true;
    }
    state[node] = 2;
    return false;
  }

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

Tradeoff:

2. Kahn's algorithm (BFS topological sort)

Compute in-degrees. Enqueue all zero-in-degree nodes. Process the queue, reducing neighbors' in-degrees; enqueue any that reach zero. If all nodes process, no cycle exists.

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

  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);
  }

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

  return processed === numCourses;
}

Tradeoff:

Expedia-specific tips

Expedia's backend engineers care about recognizing this as a directed-graph cycle detection problem, not just a course scheduling puzzle. Name Kahn's algorithm explicitly — their team uses topological ordering to validate booking-step DAGs in their supply-chain pipeline. Mention both approaches and note that Kahn's is slightly easier to reason about in production because it avoids recursion-stack overflow on deep dependency chains.

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

Practice these live with InterviewChamp.AI →