“Know how to solve every problem that has been solved.” “What I cannot create, I do not understand.” — Richard Feynman

Course Schedule

Interview Prep

StandardGraphsgraphstopological-sortcycle-detection

The problem

You're handed a course catalog. Some courses require others first — the pair [a, b] reads "take b before a." The question: can you get through the whole catalog, or is it impossible? Only one thing can make it impossible: a loop of requirements — A needs B, B needs C, C needs A — where nobody can be taken first. So draw each course as a dot and each prerequisite as an arrow; the question becomes: do the arrows anywhere form a cycle?

A fair objection: a cyclic catalog is nonsense — no real university publishes "A requires B requires A." True, and that is exactly why the question exists. Nobody hands you pre-certified data; cycles arrive as bugs, typos, and misconfigurations, and this check is the validator that catches them. It runs constantly in real systems: make and cargo refuse dependency cycles, Excel raises circular-reference errors, module importers detect import loops, deadlock detectors hunt circular waits. Read the problem as "prove this dependency data is usable," not "imagine a broken catalog." One more sharpening: what you are looking for is not a path through the courses but an ordering of all of them consistent with every arrow — a topological order — and such an ordering exists precisely when there is no cycle.

The seventh-year senior

Meet the victim of the uncaught cycle. His degree audit shows three requirements left: Compilers, OS, SysProg. Somewhere in the catalog database, three prerequisite rows slipped through review: [Compilers, OS], [OS, SysProg], [SysProg, Compilers]. Registration opens at 7:00 a.m. and he is ready with the section numbers. Compilers, section 001 — the portal flashes "Registration blocked: prerequisite OS not satisfied." OS, section 002 — "prerequisite SysProg not satisfied." SysProg, the only section — "prerequisite Compilers not satisfied." Three requirements to graduate, and the system will not let him enroll in a single one of them. There is no button to click. Every semester the same seven minutes, the same three error messages. His advisor keeps telling him he's "one prerequisite away," which is true from every direction and helpful from none. He is now in year seven, he has taken every elective the university offers, and he is failing nothing — the data is failing him, because nobody at the registrar ever ran the check this page is about. That is what a cycle means, told as a life: a student for whom no legal course order exists. The algorithm below would have flagged the three bad rows before the catalog ever shipped.

Pattern: cycle detection in a DAG

A valid course ordering exists if and only if the prerequisite graph is a directed acyclic graph (DAG) — a cycle would mean some course is a (transitive) prerequisite of itself, which is impossible. Two textbook approaches: DFS with three-color marking detects back edges (= cycles), or Kahn's algorithm tries to peel off zero-indegree vertices and fails if any are left.

Both produce the topological order as a side effect if needed. The interviewer asks "can you finish" but the same code answers "what order should you take them in" with a one-line change.

Approach 1: DFS with three colors

Color each vertex WHITE (unvisited), GRAY (currently on the DFS stack), BLACK (fully processed). If a DFS edge ever points to a GRAY vertex, you've found a back edge — a cycle. 

def can_finish_dfs(num_courses: int, prereq: list[list[int]]) -> bool:
    graph = [[] for _ in range(num_courses)]
    for a, b in prereq:
        graph[b].append(a)        # b must come before a

    WHITE, GRAY, BLACK = 0, 1, 2
    color = [WHITE] * num_courses

    def visit(u: int) -> bool:
        color[u] = GRAY
        for v in graph[u]:
            if color[v] == GRAY:
                return False              # back edge — cycle
            if color[v] == WHITE and not visit(v):
                return False
        color[u] = BLACK
        return True

    return all(color[u] == BLACK or visit(u) for u in range(num_courses))

Approach 2: Kahn's algorithm (BFS-style)

Maintain in-degree counts. Repeatedly "complete" any course with zero remaining prerequisites; each completion decrements the in-degree of its dependents. If every course is eventually completed, the graph is acyclic; if some are left with positive in-degree, they're inside a cycle. 

from collections import deque

def can_finish_kahn(num_courses: int, prereq: list[list[int]]) -> bool:
    graph = [[] for _ in range(num_courses)]
    indeg = [0] * num_courses
    for a, b in prereq:
        graph[b].append(a)
        indeg[a] += 1

    q = deque(u for u in range(num_courses) if indeg[u] == 0)
    completed = 0
    while q:
        u = q.popleft()
        completed += 1
        for v in graph[u]:
            indeg[v] -= 1
            if indeg[v] == 0:
                q.append(v)
    return completed == num_courses

Trace (acyclic case)

num_courses = 4
prereq = [[1, 0], [2, 1], [3, 2]]   # 0 → 1 → 2 → 3 (linear chain)

graph = [[1], [2], [3], []]
indeg = [0, 1, 1, 1]

Initial queue: [0]
Step 1: pop 0, completed=1, decrement indeg of [1] → indeg=[0,0,1,1], queue=[1]
Step 2: pop 1, completed=2, decrement indeg of [2] → indeg=[0,0,0,1], queue=[2]
Step 3: pop 2, completed=3, decrement indeg of [3] → indeg=[0,0,0,0], queue=[3]
Step 4: pop 3, completed=4, no neighbors, queue=[]
return completed == 4 → True

Trace (cyclic case)

num_courses = 2
prereq = [[1, 0], [0, 1]]   # 0 → 1 → 0  (cycle)

graph = [[1], [0]]
indeg = [1, 1]

Initial queue: [] (no zero-indegree vertices)
Loop never executes. completed = 0.
return 0 == 2 → False

Complexity

Variations worth knowing