Course Schedule IV

Course Schedule IV

What is this problem about?

The Course Schedule IV interview question is a graph-based reachability problem. You are given a total number of courses and a list of direct prerequisites [a, b], which means course a is a prerequisite for course b. Additionally, you are given a list of queries [u, v], and for each query, you must determine if course u is a prerequisite of course v. A prerequisite can be direct or indirect (transitive).

Why is this asked in interviews?

Companies like Uber and Meta use the Course Schedule IV coding problem to test a candidate's understanding of graph reachability and transitive closure. It evaluates whether you can efficiently answer multiple queries about connections in a Directed Acyclic Graph (DAG). While a single reachability check is easy, answering many queries requires precomputation using algorithms like Floyd-Warshall or multiple BFS/DFS traversals.

Algorithmic pattern used

This problem is solved using Transitive Closure logic. There are two main ways to implement this graph interview pattern:

1. Floyd-Warshall Algorithm: Create a 2D boolean matrix isPre[i][j]. Initialize it with direct prerequisites. Then, use three nested loops to find all indirect prerequisites: isPre[i][j] = isPre[i][j] || (isPre[i][k] && isPre[k][j]).
2. Multiple BFS/DFS: For each course, perform a traversal to find all reachable nodes and store them in a bitset or a set of reachable nodes.

Example explanation

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

1. Direct: 0 is pre of 1, 1 is pre of 2.
2. Transitive: Since 0 -> 1 and 1 -> 2, then 0 is a prerequisite of 2.
3. Query [0, 2]: Returns true.
4. Query [2, 0]: Returns false (prerequisites only work in one direction).

Common mistakes candidates make

• O(Q * (V+E)) Complexity: Running a full BFS/DFS for every query, which is too slow if there are many queries.
• Ignoring Transitivity: Only checking for direct prerequisites and missing the indirect ones.
• Cycle Handling: While the problem usually implies a DAG, not being prepared to discuss what happens if a cycle exists.

Interview preparation tip

If the number of nodes is small (e.g., $N \le 100$), Floyd-Warshall is the easiest to implement. For larger $N$, using a BFS for each node combined with bitsets can be more efficient.