Skip to main content

207. Course Schedule

mediumAsked at Juniper Networks

Detect a cycle in a directed graph to determine if courses can be completed. Juniper maps this directly to dependency resolution in Junos package management and routing protocol initialization — if module A requires B which requires A, the system deadlocks. Topological cycle detection is a core systems skill.

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

Source citations

Public interview reports confirming this problem appears in Juniper Networks loops.

  • Glassdoor (2025-Q4)— Listed in Juniper SWE onsite reports as a graph/DAG problem frequently asked in platform and systems teams.
  • Blind (2025-11)— Juniper interview prep threads cite Course Schedule as a must-know directed-graph cycle detection question.

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

Example 2

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

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

Approaches

1. Kahn's algorithm (BFS topological sort)

Compute in-degrees for all nodes. Enqueue all zero-in-degree nodes. Process BFS: for each dequeued node, reduce in-degree of its neighbors; enqueue any that hit 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 [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]) {
      inDegree[neighbor]--;
      if (inDegree[neighbor] === 0) queue.push(neighbor);
    }
  }
  return processed === numCourses;
}

Tradeoff: O(V+E). Kahn's algorithm is the canonical topological-sort approach. If processed === numCourses, every node was reachable with zero in-degree at some point, so no cycle exists.

2. DFS cycle detection with 3-color states

Use 0 (unvisited), 1 (in current DFS path), 2 (fully processed). A back edge — visiting a node with state 1 — indicates a cycle.

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; // cycle
    if (state[node] === 2) return true;  // already processed
    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). The 3-color DFS approach directly detects back edges. Both approaches are valid; Kahn's is often cleaner for iterative implementation.

Juniper Networks-specific tips

Name the algorithm — 'Kahn's topological sort' or '3-color DFS cycle detection.' Juniper interviewers expect you to know classical graph algorithm names. The 'processed === numCourses' check in Kahn's is the elegance: if any cycle exists, those nodes never reach in-degree 0 and are never processed. Connect to Junos: 'OSPF router initialization has module dependencies; a circular dependency would deadlock the routing daemon, which is exactly the cycle this algorithm detects.'

Common mistakes

  • Building the adjacency list with edge direction reversed — [a,b] means b must come before a, so the edge is b → a in the graph.
  • Not iterating over all nodes in the outer DFS loop — disconnected components would be missed.
  • Using only 2 states (visited/unvisited) in DFS — you can't distinguish back edges from cross edges without the 'currently visiting' state.
  • Returning true as soon as one component is done — all components must be cycle-free.

Follow-up questions

An interviewer at Juniper Networks may pivot to one of these next:

  • Course Schedule II (LC 210) — return the actual topological order.
  • Alien Dictionary (LC 269) — infer a topological order from sorted word lists.
  • How would you detect circular dependencies in a network device's software module initialization?

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 does processed === numCourses prove no cycle?

Only nodes with in-degree 0 are ever enqueued. In a cycle, every node in the cycle has at least one incoming edge from another cycle node, so none ever reach in-degree 0. They are never processed.

What does the 'visiting' state catch in 3-color DFS?

A back edge — an edge from a node to one of its ancestors in the current DFS call stack. This is the definition of a cycle in a directed graph.

Can there be self-loops?

The constraints say all pairs are unique and imply a course can't be a prerequisite of itself, but handle it defensively: a self-loop (a, a) has in-degree 1 from itself, so Kahn's correctly rejects it.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →