Parallel Courses

Parallel Courses

What is this problem about?

The Parallel Courses problem asks you to find the minimum number of semesters to take all n courses, given prerequisite dependencies. In each semester, you can take all courses whose prerequisites have been completed. This Parallel Courses coding problem is equivalent to finding the longest path in a DAG (topological sort with level tracking). The graph and topological sort interview pattern is the core.

Why is this asked in interviews?

Uber, Amazon, TikTok, and Google ask this because it's a clean application of topological sorting to schedule optimization. The minimum semesters = the length of the longest dependency chain (critical path). If a cycle exists, return -1.

Algorithmic pattern used

BFS-based topological sort with level tracking. Compute in-degrees. Start BFS from all courses with in-degree 0. Each BFS level = one semester. Count semesters until all courses are processed. If not all courses processed (cycle), return -1.

Example explanation

n=3, prerequisites=[(1,3),(2,3)]. Courses 1,2 have no prerequisites. Course 3 requires 1 and 2.

• Semester 1: take {1,2}. Remove edges to 3. In-degree[3]=0.
• Semester 2: take {3}. Total = 2 semesters.

Common mistakes candidates make

• Not detecting cycles (return -1 when remaining courses > 0 after BFS).
• Counting nodes processed per BFS level incorrectly.
• Using DFS topological sort (harder to count levels).
• Off-by-one in semester count.

Interview preparation tip

Parallel Courses is BFS topological sort where each level represents a time unit. The minimum semesters = BFS depth. The maximum courses you can take per semester is unlimited (unlike Parallel Courses II). Practice BFS topological sort until you can implement it fluently: initialize in-degrees, process level by level, detect cycles. This pattern appears in course scheduling, project planning, and dependency resolution.