Skip to main content

207. Course Schedule

mediumAsked at Cohere

Detect 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 Alex Chen, 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 <= 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: 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.

Output

Press Run or Cmd+Enter to execute

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.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →