Skip to main content

207. Course Schedule

mediumAsked at HP

HP's firmware release pipeline enforces strict build-dependency ordering — drivers must compile before OS modules that depend on them, and cyclic dependencies block production releases. Course Schedule is the canonical cycle-detection-in-a-directed-graph problem that mirrors this real constraint. HP uses it to evaluate topological-sort and DFS fluency.

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

Source citations

Public interview reports confirming this problem appears in HP loops.

  • Glassdoor (2025-Q4)— HP backend SWE onsite feedback cites Course Schedule as a standard graph question in rounds 2-3.
  • Blind (2025-10)— HP interview prep threads include Course Schedule as a must-practice graph problem for systems-software roles.

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 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: Courses 0 and 1 depend on each other — a cycle exists.

Approaches

1. DFS cycle detection (three-color marking)

Build an adjacency list. DFS from each unvisited node using three states: unvisited (0), in-progress (1), done (2). A back edge (reaching a node in state 1) signals a cycle.

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 fully 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. Three-color marking is the standard DFS cycle-detection technique and maps directly to the intuition of 'in-progress' vs 'complete'.

2. Kahn's algorithm (BFS topological sort)

Compute in-degrees. Start BFS from nodes with in-degree 0. Decrement neighbors' in-degrees; add those that reach 0. If all nodes are processed, 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) {
    const node = queue.shift();
    processed++;
    for (const neighbor of adj[node]) {
      if (--inDegree[neighbor] === 0) queue.push(neighbor);
    }
  }
  return processed === numCourses;
}

Tradeoff: Iterative BFS — avoids recursion stack overflow. If not all nodes are processed (processed < numCourses), a cycle was detected. HP systems roles favor this approach for large dependency graphs.

HP-specific tips

HP interviewers appreciate the parallel to real dependency management: frame your solution as 'detecting circular firmware dependencies.' Know both DFS and Kahn's — HP may ask for both, or specifically ask for the iterative version to avoid call-stack concerns. The three-color state (unvisited / in-progress / done) is cleaner than a two-flag approach and worth explaining explicitly.

Common mistakes

  • Using a visited boolean instead of three states — can't distinguish an in-progress node (cycle indicator) from a fully processed one.
  • Building the edge direction backward — prerequisites[i] = [a, b] means b → a (take b before a); confirm direction before coding.
  • Not iterating over all nodes in the outer loop — disconnected components will be missed.
  • In Kahn's, forgetting to check processed === numCourses at the end — the cycle manifests as unprocessed nodes.

Follow-up questions

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

  • Return one valid course order if it exists — topological sort output (LC 210).
  • What if prerequisites form a weighted graph with priority? How would you extend the algorithm?
  • How would you detect which specific courses form the cycle?

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 is the difference between 'in-progress' and 'done' states?

In-progress means we are currently in the DFS call stack for this node. If we reach it again from a descendant, that's a back edge — a cycle. Done means the node and all its descendants have been fully explored safely.

Why does Kahn's algorithm detect cycles?

Nodes in a cycle can never reach in-degree 0 (they always depend on each other), so they are never added to the queue and never processed. If processed < numCourses, some nodes were stuck.

Which approach is preferred for HP?

For systems roles at HP, Kahn's iterative BFS is safer (no stack overflow risk). For backend-SWE roles, DFS with three-color marking demonstrates deeper graph intuition.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →