Skip to main content

207. Course Schedule

mediumAsked at Hugging Face

Detect whether all courses can be finished given prerequisite constraints — a cycle detection problem on a directed graph. Hugging Face uses this to test DAG reasoning, which applies directly to dependency resolution in ML pipeline DAGs where a circular dependency between data preprocessing and model training steps would deadlock the entire run.

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

Source citations

Public interview reports confirming this problem appears in Hugging Face loops.

  • Glassdoor (2025-12)— Cited in Hugging Face SWE onsite reports as a graph topology and cycle-detection problem.
  • Blind (2025-09)— Hugging Face interview threads note Course Schedule as a medium graph problem with strong ML pipeline relevance.

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 course 0, then course 1. No cycle.

Example 2

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

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

Approaches

1. Topological sort (Kahn's BFS)

Build an adjacency list and in-degree array. Start BFS with all nodes of in-degree 0. Each time a node is processed, decrement its neighbors' in-degrees; add them to the queue when they 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 [course, pre] of prerequisites) {
    adj[pre].push(course);
    inDegree[course]++;
  }
  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]) {
      inDegree[neighbor]--;
      if (inDegree[neighbor] === 0) queue.push(neighbor);
    }
  }
  return processed === numCourses;
}

Tradeoff: O(V+E) time and space. Kahn's algorithm is intuitive and gives a valid topological order as a side effect. Use this when you also need the ordering (Course Schedule II).

2. DFS cycle detection (three-color)

DFS with three states: unvisited (0), in-current-path (1), fully-processed (2). A cycle exists if DFS visits a node currently in the path (state 1).

Time
O(V+E)
Space
O(V+E)
function canFinish(numCourses, prerequisites) {
  const adj = Array.from({ length: numCourses }, () => []);
  for (const [course, pre] of prerequisites) adj[pre].push(course);
  const state = new Array(numCourses).fill(0); // 0=unvisited,1=visiting,2=done
  function dfs(node) {
    if (state[node] === 1) return false; // cycle
    if (state[node] === 2) return true;  // already verified
    state[node] = 1;
    for (const neighbor of adj[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: Also O(V+E). The three-color approach is standard for directed cycle detection. The in-path state (1) is the key — it distinguishes a back edge (cycle) from a cross edge (already processed node).

Hugging Face-specific tips

Hugging Face interviewers love the ML pipeline analogy: 'This is exactly how we validate that a dataset processing pipeline has no circular dependencies — each preprocessing step is a node and each dependency is a directed edge. A cycle means the pipeline would deadlock.' Choose Kahn's BFS if you want to also return the valid ordering; choose DFS if cycle detection alone is the goal. Be explicit about which you're using and why.

Common mistakes

  • Building the adjacency list in the wrong direction — prerequisites[i] = [a, b] means b → a (b must come before a).
  • In DFS, using a single boolean visited array instead of three states — can't distinguish back edges from cross edges.
  • In Kahn's, initializing the queue with in-degree 1 instead of 0.
  • Forgetting to handle isolated nodes (nodes with no edges) — they should be counted as processed.

Follow-up questions

An interviewer at Hugging Face may pivot to one of these next:

  • Course Schedule II (LC 210) — return the actual topological order.
  • Course Schedule III (LC 630) — maximize the number of courses taken given deadlines.
  • How would you detect cycles in a distributed ML pipeline DAG where steps run across multiple machines?

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 Kahn's and DFS for this problem?

Both are O(V+E). Kahn's uses BFS and in-degree counting — useful when you want the ordering. DFS uses three-color state — simpler to implement for pure cycle detection.

Why do we need three colors in DFS instead of just visited/unvisited?

Two colors can't distinguish a back edge (pointing to an ancestor = cycle) from a cross edge (pointing to an already-completed subtree = no cycle). The in-path color (gray) captures this.

Can there be multiple valid topological orderings?

Yes — whenever two nodes have no dependency between them, either can come first. The number of valid orderings grows with the number of parallel independent paths.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →