Skip to content
Hello Python

Course Schedule

Interview ProblemInterviewMediumGraphQueueKahn's Algorithm

Checking your account…

Sign in to save your code and progress across devices. The lesson and problem statement remain public.

Loading the interactive Interview workspace.If it does not appear, the problem and learning material remain readable, but browser execution is unavailable.Reload Interview workspace

Problem

Implement Solution.canFinish(numCourses, prerequisites). Each pair [course, prerequisite] means prerequisite must be completed before course. Return whether every course can be completed.

Starter code

class Solution:
    def canFinish(self, numCourses, prerequisites):
        pass
Test cases

simple-chain

{
  "args": [
    2,
    [
      [
        1,
        0
      ]
    ]
  ]
}

Expected: true

two-node-cycle

{
  "args": [
    2,
    [
      [
        1,
        0
      ],
      [
        0,
        1
      ]
    ]
  ]
}

Expected: false

Wizard outline
  1. Step 1: Initialize Solution.canFinish

    Replace the empty starter with the first real state owned by Solution.canFinish. A small, named state is easier to verify than a complete algorithm. Establish it before adding the branch or loop that changes it.

  2. Step 2: Pass the Simple Chain case

    Complete the readable core algorithm for one representative Interview case. Finish the mock round with graph dependencies.

  3. Step 3: Harden the Two Node Cycle boundary

    Repair the reviewed boundary and pass the complete submission contract. Every dequeued course has all prerequisites satisfied. A DAG eventually dequeues every course; any directed cycle keeps its remaining indegrees positive, so the processed count is smaller than numCourses.

Footguns and prerequisites
  • Checking only duplicate edges does not detect longer cycles.
  • trees and graphs
Reviewed references
Practice prerequisites
  • Maintain an Indegree Frontier(opens in a new tab)

    Maintain an Indegree Frontier isolates a node enters a frontier exactly when all of its predecessors have been removed, and each edge decrements indegree once. That focused state discipline is required when implementing course schedule as a complete Interview Problem.

Recommended approach and implementation

Use Kahn's algorithm: build prerequisite-to-course edges and indegrees, then process every zero-indegree course with a queue.

Why it works: Every dequeued course has all prerequisites satisfied. A DAG eventually dequeues every course; any directed cycle keeps its remaining indegrees positive, so the processed count is smaller than numCourses.

from collections import deque

class Solution:
    def canFinish(self, numCourses, prerequisites):
        """
        Checkpoint 1: initialize the state owned by this Interview contract.
        Checkpoint 2: assemble the primary transition without hiding the boundary.
        """
        graph = [[] for _ in range(numCourses)]
        indegree = [0] * numCourses
        for course, prerequisite in prerequisites:
            graph[prerequisite].append(course)
            indegree[course] += 1
        queue = deque(course for course, degree in enumerate(indegree) if degree == 0)
        completed = 0
        while queue:
            prerequisite = queue.popleft()
            completed += 1
            for course in graph[prerequisite]:
                indegree[course] -= 1
                if indegree[course] == 0:
                    queue.append(course)
        return completed == numCourses