207. Course Schedule
mediumAsked at Hugging FaceDetect 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 Sam K., 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 <= 20000 <= prerequisites.length <= 5000prerequisites[i].length == 20 <= ai, bi < numCoursesAll the pairs prerequisites[i] are unique.
Examples
Example 1
numCourses = 2, prerequisites = [[1,0]]trueExplanation: Take course 0, then course 1. No cycle.
Example 2
numCourses = 2, prerequisites = [[1,0],[0,1]]falseExplanation: 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.
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.