Interview OS
Back to Coding Prep

Coding

Course Schedule

Graphs · Medium

GraphsMedium

Overview

Course Schedule: given prerequisite pairs, decide whether all courses can be finished. It reduces to detecting a cycle in a directed graph — solved cleanly with a topological sort (Kahn's algorithm) over indegrees.

How it works

Graphs
InputBuildSortOutputPrereq edgesgraphAdj + indegindeg[]Topo (Kahn)queueCycle?
ClientDataServiceEdge

Step by step, with examples

  1. 1

    Prereq edges

    • Decide if all courses are finishable.
  2. 2

    Adj + indeg

    • Model prerequisites as a directed graph.
  3. 3

    Topo (Kahn)

    • Peel off zero-indegree nodes.
  4. 4

    Cycle?

    • No cycle means it is schedulable.
    • Example: false if cycle

Problem

Given numCourses and prerequisite pairs, determine if you can finish all courses (i.e., the dependency graph has no cycle).

Approach

  • Build adjacency list + in-degree array
  • Kahn's BFS topological sort
  • Finishable iff every node is processed

Solution

function canFinish(numCourses, prerequisites) {
  const adj = Array.from({length:numCourses}, () => []);
  const indeg = Array(numCourses).fill(0);
  for (const [a,b] of prerequisites){ adj[b].push(a); indeg[a]++; }
  const q = [];
  for (let i=0;i<numCourses;i++) if(!indeg[i]) q.push(i);
  let done = 0;
  while(q.length){
    const c = q.shift(); done++;
    for(const nx of adj[c]) if(--indeg[nx]===0) q.push(nx);
  }
  return done === numCourses;
}

Complexity

Time O(V + E), Space O(V + E).

Where this content comes from

For full transparency, this content is curated and verified from these sources:

Curated company-tagged problem banksRecurring interview pattern librariesOppZen-authored drills & solutions