📖 9 min read
Last updated on

Course Schedule — Coding Interview Walkthrough

By intervu.dev

Hero Image for Course Schedule — Coding Interview Walkthrough

You’re in a coding interview. The interviewer says: “You have a list of courses and their prerequisites. Can you finish all of them?” You know it’s a graph problem. You know you need cycle detection. But the moment you start coding, they’re watching whether you get the edge direction right, whether you reach for two states or three, and whether you can explain why a visiting state matters when they ask the follow-up about Course Schedule II.

This walkthrough breaks down exactly how to structure your approach, what to say out loud, and where candidates lose points even when they get the right answer.

The Problem

You are given numCourses courses labeled 0 to numCourses - 1, and a list of prerequisite pairs. Each pair [a, b] means you must take course b before you can take course a. Return true if it’s possible to finish all courses, or false if it’s not.

A situation where it’s not possible would be if two courses require each other, a circular dependency that makes it impossible to ever start.

Example

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

Output true

Here, course 1 requires course 0. You can take 0 first, then 1. There’s no cycle, so it’s possible to complete everything.

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

Output false

Now course 1 requires 0 and course 0 requires 1. They’re mutually dependent, so you return false. (LeetCode #207)

Already comfortable with the solution? Practice it in a mock interview ->

Two directed graphs side by side: Left shows 1→0 (no cycle, returns True). Right shows 0↔1 mutual dependency (cycle, returns False).

What Interviewers Are Actually Testing

This problem isn’t really about scheduling. It’s a cycle detection problem dressed up in a practical scenario.

SkillWhat Interviewers Observe
Graph modelingCan you represent prerequisites as a directed graph (adjacency list)?
Cycle detection intuitionDo you recognize this as a topological sort / DFS cycle detection problem?
State trackingDo you understand why you need three states (unvisited, visiting, visited)?
Edge case handlingDo you handle disconnected graphs, courses with no prerequisites, empty input?
Algorithm choiceCan you articulate the tradeoffs between DFS and Kahn’s BFS algorithm?
CommunicationDo you explain your approach before jumping into code?

Step 1: Clarifying Questions

Before writing any code, pause and ask these questions:

  1. “Can there be courses with no prerequisites at all?” Yes, and these are trivially completable. Your traversal must cover all numCourses nodes, not just those mentioned in the prerequisite list.

  2. “Can the prerequisites list be empty?” If prerequisites = [], the answer is always true. Confirming this lets you handle it as a clean base case.

  3. “Are there duplicate prerequisite pairs?” LeetCode guarantees no duplicates, but asking shows you’re thinking about input hygiene.

  4. “Is the graph guaranteed to be connected?” No, and this is critical. If you only traverse from one starting node, you may miss entire disconnected components.

  5. “Should I return the valid ordering, or just whether one exists?” This problem only asks for a boolean. But asking shows you’re aware of Course Schedule II, which is a natural follow-up.

Step 2: A First (Non-Optimal) Idea

A candidate’s first instinct is often to simulate the process: find a course with no prerequisites, “take” it, remove it from the dependency list, and repeat.

def canFinish(numCourses, prerequisites):
    in_degree = [0] * numCourses
    for _, pre in prerequisites:
        in_degree[pre] += 1  # This logic is already wrong — tracking wrong direction

    completed = 0
    changed = True
    while changed:
        changed = False
        for i in range(numCourses):
            if in_degree[i] == 0:
                in_degree[i] = -1  # Mark as "taken"
                completed += 1
                changed = True
                # ... update dependents (complex to implement correctly)
    return completed == numCourses

This approach is conceptually valid but hard to implement cleanly. The inner loop rescans all courses on every pass, giving O(V^2) time complexity. It’s also error-prone: candidates frequently get the dependency direction backwards.

More importantly, it doesn’t translate into a recognizable algorithm. Interviewers want to see you reach for DFS or topological sort, established patterns with clear correctness arguments.

Step 3: The Key Insight

The “aha” moment: “can we finish all courses?” is exactly equivalent to “does this directed graph contain a cycle?” If there’s a cycle, no valid ordering exists. If there’s no cycle, a topological order always exists.

The elegant way to detect cycles with DFS uses three node states:

  • 0 (Unvisited): We haven’t explored this node yet.
  • 1 (Visiting): We’re currently in a DFS path that includes this node.
  • 2 (Visited): We’ve fully explored this node and confirmed it has no cycles.

If during DFS we encounter a node already in state 1 (currently on our path), we’ve found a back edge, which means a cycle. If we finish exploring a node with no cycle, we mark it state 2 so future DFS calls skip it entirely.

Here’s how the three states evolve during DFS, both when there’s no cycle and when a cycle gets caught:

DFS three-state trace showing cycle detection vs no-cycle case

Step 4: Optimal Strategy (DFS Three-State Cycle Detection)

  1. Build an adjacency list: For each pair [a, b], add b to the neighbor list of a (meaning “to take a, you need b”).
  2. Initialize a state array of size numCourses, all set to 0 (unvisited).
  3. Define has_cycle(node):
    • If state[node] == 1: return True (back edge found, cycle).
    • If state[node] == 2: return False (already verified, skip).
    • Set state[node] = 1 (currently visiting).
    • Recurse into all neighbors. If any returns True, propagate it.
    • Set state[node] = 2 (fully visited, no cycle from here).
    • Return False.
  4. Iterate over all nodes 0 to numCourses - 1. Call has_cycle(i) for each unvisited node.
  5. Return True if no cycle was found across any component.

Python Implementation

from typing import List
from collections import defaultdict

class Solution:
    def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool:
        # Build adjacency list: course -> list of prerequisites
        graph = defaultdict(list)
        for course, prereq in prerequisites:
            graph[course].append(prereq)

        # 0 = unvisited, 1 = visiting (in current DFS path), 2 = visited (safe)
        state = [0] * numCourses

        def has_cycle(node: int) -> bool:
            if state[node] == 1:
                return True   # Back edge detected — cycle found
            if state[node] == 2:
                return False  # Already confirmed safe — skip

            state[node] = 1  # Mark as currently being explored

            for neighbor in graph[node]:
                if has_cycle(neighbor):
                    return True  # Propagate cycle detection upward

            state[node] = 2  # Mark as fully explored — no cycle from here
            return False

        # Check every node — graph may be disconnected
        for course in range(numCourses):
            if state[course] == 0:
                if has_cycle(course):
                    return False

        return True

The defaultdict(list) handles courses with no prerequisites cleanly. The explicit state array is cleaner than using a visited set because it distinguishes the three states needed for cycle detection.

Time Complexity

OperationComplexity
Building the adjacency listO(E), one pass over prerequisites
DFS traversal (each node visited once)O(V)
Processing all edges across DFSO(E)
Overall TimeO(V + E)
Overall SpaceO(V + E), graph storage + recursion stack

Here, V = numCourses and E = len(prerequisites). Each node is visited at most once (the state == 2 check prevents re-processing), and each edge is traversed at most once.

Common Interview Mistakes

  1. Using only two states instead of three Many candidates use a simple visited boolean. This can’t distinguish “currently on the DFS path” from “already fully processed,” causing false cycle detections or missing real ones. You need the visiting state.

  2. Getting the edge direction backwards If the problem says [a, b] means “a requires b,” some candidates add b -> a instead of a -> b. Draw the graph explicitly before coding.

  3. Only traversing from node 0 If you start DFS only from course 0, you’ll miss disconnected components. Always iterate over all nodes.

  4. Forgetting courses with no prerequisites Courses not in prerequisites still exist in the graph. They just have no outgoing edges. Your code must not crash when graph[node] is empty.

  5. Coding immediately without drawing the graph On a whiteboard, sketch the graph for the examples before writing code. This catches edge-direction mistakes early.

  6. Not explaining the three-state logic verbally If you write the state array without explaining why three values are needed, the interviewer may assume you memorized the solution.

  7. Confusing this with undirected graph cycle detection Undirected cycle detection only needs two states. Directed graphs require three. If you conflate the two, you’ll give an incorrect solution.

What a Strong Candidate Sounds Like

“This is a cycle detection problem on a directed graph. I’ll model the prerequisites as an adjacency list, then run DFS across all nodes. The key is tracking three states: unvisited, currently-visiting, and fully-visited. If I hit a node that’s currently on my active DFS path, I’ve found a back edge, which means a cycle. If I finish exploring a node without finding a cycle, I mark it fully-visited so I never process it again. I need to run this from every node since the graph might be disconnected. Time complexity is O(V + E).”

Example Interview Dialogue

Interviewer: “You have numCourses courses and a list of prerequisite pairs. Can you finish all courses?”

Candidate: “Before I start: a pair [a, b] means I must take b before a, right? And should I return just true/false, or the actual order?”

Interviewer: “Correct on the direction. Just the boolean.”

Candidate: “Got it. So this is asking whether the directed graph has a cycle. I’ll build an adjacency list and do DFS with three states to detect back edges. I need to run DFS from every node since the graph may not be connected.”

[Draws example graph, then writes solution]

Interviewer: “What if I asked you to return the actual order in which to take the courses?”

Candidate: “That’s Course Schedule II, topological sort. I’d collect nodes into a result list as I mark them fully-visited. The order I add them gives a valid topological ordering. Alternatively, I could use Kahn’s algorithm with in-degree tracking and a queue, that’s BFS-based and also O(V + E).”

Interviewer: “Could you hit a recursion limit on large inputs?”

Candidate: “Yes. If the graph is a long chain with 10^5 nodes, Python’s default recursion depth of ~1000 would break. I’d either increase the limit with sys.setrecursionlimit, or convert the DFS to an iterative approach using an explicit stack.”

  1. Course Schedule II (LeetCode 210). The direct follow-up: return the actual course order. Requires storing the topological sort result.

  2. Alien Dictionary (LeetCode 269). Derive a topological ordering from character relationships. Same DFS cycle detection with more complex graph construction.

  3. Longest Increasing Path in a Matrix (LeetCode 329). DFS with memoization on a DAG. Deepens understanding of state caching in graph traversal.

  4. Sequence Reconstruction (LeetCode 444). Verify that a topological order is unique. Same directed graph model applied to a uniqueness problem.

  5. Sort Items by Groups Respecting Dependencies (LeetCode 1203). A harder topological sort problem with two levels of dependency.

From the Intervu walkthrough collection:

Practice This in a Mock Interview

Reading a walkthrough and solving a problem under interview pressure are very different skills. You won’t have access to notes, and you’ll need to model the graph from scratch, recall the three-state DFS trick without hints, and handle follow-up questions about topological sort variants.

Start a mock interview for Course Schedule on Intervu.

Further reading:

Practice Like It's the Real Interview

Get instant feedback on your approach, communication, and code — powered by AI.

Start a Mock Interview →