Course Schedule

Course Schedule

What is this problem about?

The Course Schedule interview question is a classic dependency problem. You are given a total number of courses and a list of prerequisites where each prerequisite [a, b] means you must take course b before course a. You need to determine if it is possible to finish all courses. In graph terms, this is equivalent to checking if a directed graph contains a cycle.

Why is this asked in interviews?

This is one of the most popular graph interview patterns, asked by nearly every top-tier company including Amazon, Salesforce, and Microsoft. It evaluates your understanding of directed graphs and dependency resolution. It's a fundamental test of whether you can identify a problem as a cycle detection task and implement a robust traversal algorithm.

Algorithmic pattern used

This problem is solved using Topological Sort, which can be implemented in two ways:

1. Kahn's Algorithm (BFS): Calculate the "in-degree" (number of prerequisites) for each course. Start with courses that have 0 in-degree and remove them from the graph, reducing the in-degree of their neighbors. If you can remove all courses, there's no cycle.
2. DFS-based Cycle Detection: Use a recursive traversal with a "visiting" state to detect back-edges. If you visit a node that is already in the current recursion stack, a cycle exists.

Example explanation

Courses: 2, Prerequisites: [[1, 0]] (Take 0 before 1)

1. Build adjacency list: 0 -> 1.
2. In-degrees: {0: 0, 1: 1}.
3. Start with course 0 (in-degree 0).
4. Remove 0, update 1's in-degree to 0.
5. Take course 1.
6. All 2 courses taken. Possible!

Courses: 2, Prerequisites: [[1, 0], [0, 1]]

1. Adjacency: 0 -> 1, 1 -> 0. (Cycle detected).
2. In-degrees: {0: 1, 1: 1}.
3. No course has in-degree 0. Impossible!

Common mistakes candidates make

• Ignoring Disconnected Components: Failing to run the traversal on all nodes, which might miss a cycle in a separate part of the graph.
• Recursive Stack Overflow: Not considering that a deep dependency chain might require an iterative approach or an increased recursion depth.
• In-degree management: Forgetting to update neighbor counts correctly after removing a node in Kahn's algorithm.

Interview preparation tip

Always clarify if the graph is directed or undirected. Dependency problems are almost always Directed Acyclic Graphs (DAGs). Memorize Kahn's algorithm; it's often more intuitive to explain than the DFS states.