Skip to main content

207. Course Schedule

mediumAsked at AMD

Determine if you can finish all courses given a list of prerequisites. This is cycle detection in a directed graph — AMD tests it because dependency ordering is fundamental to task graph scheduling, GPU compute graph compilation, and LLVM IR pass ordering in their compiler toolchain.

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

Source citations

Public interview reports confirming this problem appears in AMD loops.

  • Glassdoor (2026-Q1)— AMD SWE candidates report Course Schedule appearing in medium rounds with a follow-up about GPU task graph scheduling.
  • Blind (2025-10)— AMD interview threads highlight topological sort and cycle detection as high-frequency graph topics reflecting compiler work.

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 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 0 first, then 1.

Example 2

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

Explanation: Circular dependency — each requires the other.

Approaches

1. DFS cycle detection (coloring)

Build an adjacency list. DFS with three states: 0=unvisited, 1=in-progress, 2=done. If you visit an in-progress node, there's 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=new, 1=active, 2=done
  function dfs(node) {
    if (state[node] === 1) return false; // cycle
    if (state[node] === 2) return true;  // already validated
    state[node] = 1;
    for (const neighbor of graph[node]) {
      if (!dfs(neighbor)) return false;
    }
    state[node] = 2;
    return true;
  }
  for (let i = 0; i < numCourses; i++) {
    if (!dfs(i)) return false;
  }
  return true;
}

Tradeoff: O(V+E). The three-color state avoids re-visiting already-validated subtrees. Clearly maps to the 'gray node = back edge = cycle' convention from textbook graph theory.

2. BFS Topological Sort (Kahn's algorithm)

Compute in-degrees. Start BFS from nodes with in-degree 0. Decrement neighbors' in-degrees; when a neighbor reaches 0, enqueue it. If all nodes are processed, 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]) {
      if (--inDegree[neighbor] === 0) queue.push(neighbor);
    }
  }
  return processed === numCourses;
}

Tradeoff: O(V+E). Iterative — no call-stack risk for large graphs. The processed count check elegantly detects cycles without explicit cycle tracking.

AMD-specific tips

AMD's ROCm compute graph API and LLVM pass manager both schedule tasks using topological ordering. Mention the real-world connection: 'a GPU compute graph is a DAG of kernels; the scheduler needs a topological order to dispatch them. A cycle means deadlock.' Kahn's algorithm is particularly natural here because it mirrors how a real scheduler processes nodes with no pending dependencies (in-degree 0). AMD interviewers appreciate when candidates name the algorithm (Kahn's) rather than just describing it.

Common mistakes

  • Building the graph in the wrong direction — [a,b] means b is a prerequisite of a, so the edge goes from b to a.
  • Not handling disconnected components — the outer loop must visit every node.
  • DFS: returning false when state[node] === 2 instead of true — a fully processed node is safe.
  • Kahn's: comparing processed to prerequisites.length instead of numCourses — you need all nodes processed.

Follow-up questions

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

  • Course Schedule II (LC 210) — return the actual topological order.
  • Alien Dictionary (LC 269) — derive a topological order from lexicographic constraints.
  • How does AMD's ROCm HIP graph API use dependency graphs for kernel scheduling?

Solve it now

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

Output

Press Run or Cmd+Enter to execute

FAQ

Why does Kahn's algorithm detect cycles?

Nodes in a cycle always have in-degree > 0 among themselves (they depend on each other), so they're never enqueued. If processed < numCourses, unprocessed nodes form at least one cycle.

Which approach is better for GPU task scheduling?

Kahn's BFS is more natural for scheduling: nodes with in-degree 0 are ready to run immediately. In a parallel setting, all zero-in-degree nodes can be dispatched simultaneously.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →