Skip to main content

207. Course Schedule

mediumAsked at eBay

eBay's seller onboarding pipeline has steps that depend on other steps — account verification must precede listing creation, which must precede payment setup. Detecting whether such a dependency graph has a cycle is the problem Course Schedule solves. It's a graph-cycle-detection problem that eBay uses to test topological sort and the three-color DFS cycle-detection pattern.

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

Source citations

Public interview reports confirming this problem appears in eBay loops.

  • Glassdoor (2025-11)— Cited in eBay SWE onsite reports as a graph cycle detection problem in round 2 or round 3.
  • Blind (2025-10)— eBay SWE interview threads recommend Course Schedule as a high-probability graph problem for mid-to-senior candidates.

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 before course ai. Return true if you can finish all courses. Otherwise, return false.

Constraints

  • 1 <= numCourses <= 2000
  • 0 <= prerequisites.length <= 5000
  • prerequisites[i].length == 2
  • 0 <= ai, bi < numCourses
  • All the pairs prerequisites[i] are unique.

Examples

Example 1

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

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

Example 2

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

Explanation: Course 0 requires course 1 and course 1 requires course 0 — a cycle makes completion impossible.

Approaches

1. DFS with three-color cycle detection

Build an adjacency list. For each unvisited node, DFS with three states: 0=unvisited, 1=in-current-path, 2=fully-processed. If DFS reaches a node in state 1, a cycle exists.

Time
O(V + E)
Space
O(V + E)
function canFinish(numCourses, prerequisites) {
  const adj = Array.from({ length: numCourses }, () => []);
  for (const [a, b] of prerequisites) adj[b].push(a);
  const state = new Array(numCourses).fill(0); // 0=unvisited, 1=visiting, 2=done
  function hasCycle(node) {
    if (state[node] === 1) return true;  // back edge → cycle
    if (state[node] === 2) return false; // already processed
    state[node] = 1;
    for (const neighbor of adj[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: O(V+E) time and space. The three-color approach cleanly distinguishes a back edge (cycle) from a cross edge (already-processed node). Easier to reason about than tracking parent nodes.

2. Topological Sort (Kahn's BFS / in-degree)

Compute in-degree for every node. Initialize a queue with all zero-in-degree nodes. Process: decrement in-degree of neighbors; enqueue any that reach zero. If the processed count equals numCourses, no cycle exists.

Time
O(V + E)
Space
O(V + E)
function canFinish(numCourses, prerequisites) {
  const adj = Array.from({ length: numCourses }, () => []);
  const inDegree = new Array(numCourses).fill(0);
  for (const [a, b] of prerequisites) { adj[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 > 0) {
    const node = queue.shift();
    processed++;
    for (const neighbor of adj[node]) {
      inDegree[neighbor]--;
      if (inDegree[neighbor] === 0) queue.push(neighbor);
    }
  }
  return processed === numCourses;
}

Tradeoff: O(V+E). BFS-based, avoids recursion depth concerns. The 'processed count' trick elegantly detects cycles — if any node remains in a cycle it will never reach in-degree 0 and won't be counted.

eBay-specific tips

eBay interviewers want you to name both approaches — DFS cycle detection and Kahn's topological sort — and state the trade-off: 'DFS is recursive (stack depth concern for 2000 nodes), Kahn's is iterative and explicit.' For the 'how does this scale to a dependency graph with millions of services?' follow-up: distributed topological sort, partition the DAG by in-degree, process levels in parallel.

Common mistakes

  • Using only two states (visited/unvisited) in DFS — can't distinguish a back edge (cycle) from a cross edge (previously fully processed node).
  • Forgetting to iterate over all nodes in the outer loop — disconnected components are missed.
  • In Kahn's, forgetting to increment processed before (not after) decrementing neighbors — causes off-by-one in the final count.
  • Building the adjacency list in the wrong direction — prerequisites[i] = [a, b] means b → a (b is a prerequisite of a).

Follow-up questions

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

  • Course Schedule II (LC 210) — return the actual topological order, not just a boolean.
  • Alien Dictionary (LC 269) — infer ordering from a sorted word list; builds on topological sort.
  • How would you detect all nodes participating in cycles, not just whether a cycle exists?

Solve it now

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

Output

Press Run or Cmd+Enter to execute

FAQ

What are the three states and what do they mean?

0 = unvisited (not yet reached). 1 = currently on the DFS stack (visiting). 2 = fully processed (all descendants explored). A back edge to state 1 is a cycle.

Why does Kahn's algorithm detect cycles?

Every node in a cycle always has at least one incoming edge from within the cycle, so its in-degree never reaches zero. It is never enqueued, so processed < numCourses at the end.

What is the time complexity in terms of prerequisites?

V = numCourses, E = prerequisites.length. Both approaches run in O(V + E).

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →