Skip to main content

207. Course Schedule

mediumAsked at Akamai

Determine if all courses can be completed given prerequisite dependencies. Akamai maps this to dependency resolution in edge configuration deployments — detecting a circular dependency (cycle in the DAG) is the difference between a successful config rollout and a cascading outage.

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

Source citations

Public interview reports confirming this problem appears in Akamai loops.

  • Glassdoor (2026-Q1)— Akamai SWE interview reports cite Course Schedule as a standard graph cycle detection question in algorithm rounds.
  • Blind (2025-10)— Akamai threads confirm topological sort and cycle detection problems appear in both phone screens and onsite coding rounds.

Problem

There are numCourses courses 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 course 1 and course 1 requires course 0.

Approaches

1. DFS cycle detection with three-color marking

Build an adjacency list. DFS from each unvisited node marking states: 0=unvisited, 1=in-progress (in current DFS path), 2=complete. A cycle exists if we encounter a node marked 1 (back edge). If a node is marked 2 we can skip it safely.

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=in-progress,2=done
  function hasCycle(node) {
    if (state[node] === 1) return true;  // back edge → cycle
    if (state[node] === 2) return false; // already verified
    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. The three-color scheme is the canonical approach for directed cycle detection. Akamai expects explicit naming of the three states.

2. Topological sort (Kahn's algorithm / BFS)

Compute in-degree for each node. Add all zero-in-degree nodes to a queue. Process the queue: reduce neighbors' in-degree; add to queue if it hits zero. If the total processed equals numCourses, there is no cycle.

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: Also O(V+E). Kahn's is iterative (avoids DFS call stack risk) and naturally produces a topological ordering if needed. Prefer this if the interviewer asks for the ordering in a follow-up.

Akamai-specific tips

Name the algorithms by name: 'I'll use DFS with three-color marking, which is the standard algorithm for directed cycle detection' or 'Kahn's algorithm for topological sort.' Akamai interviewers with CS theory backgrounds appreciate precise naming. Then connect to the deployment analogy: 'In Akamai's config system, a circular dependency means a configuration rule set that can never converge — exactly what this algorithm detects.'

Common mistakes

  • Using a simple boolean visited array instead of three-color — two states can't distinguish 'in current path' from 'already verified clean', causing false cycle reports.
  • Building the adjacency list in the wrong direction — prerequisites[i] = [a, b] means b → a (take b before a). Reversing produces wrong results.
  • Not iterating over all nodes in the outer loop — disconnected graph components won't be visited from a single start node.

Follow-up questions

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

  • Course Schedule II (LC 210) — return one valid topological ordering if possible.
  • How would you detect cycles in an undirected graph?
  • How would you parallelize course completion if independent courses can be taken simultaneously?

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 colors and not two?

In a directed graph, two states (visited/unvisited) cannot detect back edges. A node might be reachable via two different paths. The 'in-progress' state lets us distinguish 'on the current DFS path' (cycle!) from 'already fully explored' (safe to skip).

How does Kahn's algorithm detect cycles?

If a cycle exists, the nodes in the cycle will never reach in-degree zero (they always depend on each other). They stay off the queue and are never processed. If processed < numCourses, the remainder forms cycles.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →