207. Course Schedule
mediumAsked at CohereDetect whether a set of course prerequisites can all be satisfied — i.e., detect a cycle in a directed graph. Cohere asks this because topological ordering of task dependencies mirrors pipeline DAG scheduling for multi-step RAG and agentic workflows.
By Sam K., Founder, InterviewChamp.AI · Last verified
Source citations
Public interview reports confirming this problem appears in Cohere loops.
- Glassdoor (2025-Q4)— Cohere SWE onsite reports include Course Schedule as a graph medium problem in algorithm rounds.
- Blind (2025-11)— Cohere candidate threads list cycle detection in directed graphs as a must-know pattern for engineering 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] = [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: Cycle: course 0 requires 1 and course 1 requires 0.
Approaches
1. DFS cycle detection (three-colour marking)
Mark each node as unvisited (0), in-progress (1), or done (2). DFS from each unvisited node; if we reach an in-progress node, 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 dfs(node) {
if (state[node] === 1) return false; // back edge = cycle
if (state[node] === 2) return true; // already cleared
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: O(V+E) — clear and direct. Three-colour marking correctly distinguishes back edges (cycles) from cross edges (previously-cleared subgraphs).
2. Kahn's algorithm (BFS topological sort)
Compute in-degrees. Enqueue nodes with in-degree 0. Process queue: decrement neighbours' in-degrees; enqueue new zero-in-degree nodes. 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 adj = Array.from({ length: numCourses }, () => []);
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 — no call-stack risk. Also naturally produces a topological order as a side effect, which is useful when Course Schedule II (return the order) is a follow-up.
Cohere-specific tips
Cohere builds multi-step inference pipelines where steps have data dependencies. Frame your answer: 'Course Schedule is equivalent to detecting whether a task-dependency DAG is acyclic — if it has a cycle, some tasks can never start.' Cohere interviewers frequently ask for Course Schedule II (return the topological order) as a follow-up, so be ready to extend Kahn's algorithm to capture the processing order in a result list.
Common mistakes
- Forgetting to build the adjacency list — edges go from prerequisite to course (b → a for [a, b]).
- Using only two states (visited/unvisited) — cannot distinguish a back edge from a cross edge, producing false positives.
- In Kahn's algorithm, not counting processed nodes — a count of numCourses confirms all nodes were reachable without a cycle.
- Reversing the edge direction — build adj[b].push(a) for prerequisite pair [a, b], not adj[a].push(b).
Follow-up questions
An interviewer at Cohere may pivot to one of these next:
- Course Schedule II (LC 210) — return the topological ordering.
- Alien Dictionary — infer ordering of characters from a sorted word list using topological sort.
- How would you schedule dependent inference steps in a multi-stage RAG pipeline?
Solve it now
Free. No sign-up. Python and JavaScript run instantly in your browser.
FAQ
Why three colours instead of two?
Two colours (visited/unvisited) cannot tell whether a visited node is currently on the DFS stack (back edge = cycle) or was processed earlier (cross edge = no cycle). The in-progress state makes this distinction.
Which approach should I code first?
Kahn's is iterative and naturally extends to producing the order — prefer it. DFS is more concise if the interviewer only wants a true/false answer.
What if numCourses is large but prerequisites is sparse?
Both approaches are O(V+E), so sparse graphs run quickly. Mention this is true of real pipeline DAGs, which tend to be sparse.