How do I practice coding and algorithm questions?

Use PracHub's coding console to write, test, and debug your solutions in Python or JavaScript. View hints, test against sample inputs, and compare with official solutions.

What difficulty level is this coding question?

This is a medium difficulty Coding & Algorithms question, commonly asked during Onsite rounds at Netflix.

What role is this question designed for?

This question is commonly asked for Software Engineer candidates at Netflix during technical interviews.

Compute minimum semesters to finish courses

Q: Compute minimum semesters to finish courses

This question evaluates graph theory and scheduling competencies, including dependency resolution, cycle detection in directed graphs, and capacity-constrained task scheduling based on prerequisites.

Company: Netflix

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Onsite

You are given `n` courses labeled `1..n` and a list of prerequisite relations `prereq`, where each element is a pair `[a, b]` meaning you must complete course `a` before taking course `b`. ### Part A Return the **minimum number of semesters** needed to complete all courses if you may take **any number of courses per semester**, as long as prerequisites are satisfied. - If it is impossible to finish all courses (because prerequisites contain a cycle), return `-1`. **Input** - Integer `n` - List `prereq: List[List[int]]` **Output** - Integer minimum semesters, or `-1` **Constraints (reasonable interview constraints)** - `1 <= n <= 10^5` - `0 <= prereq.length <= 2*10^5` - Course labels are in `1..n` ### Part B (follow-up) Now you may take **at most `k` courses per semester**. Return the minimum number of semesters needed to complete all courses under this constraint, or `-1` if impossible. **Additional input** - Integer `k` with `1 <= k <= n` **Notes** - You may choose which available (prerequisites-satisfied) courses to take each semester.

Quick Answer: This question evaluates graph theory and scheduling competencies, including dependency resolution, cycle detection in directed graphs, and capacity-constrained task scheduling based on prerequisites.

Part 1: Minimum Semesters with Unlimited Courses per Semester

You are given n courses labeled 1 through n and a list of prerequisite relations prereq. Each relation [a, b] means course a must be completed before course b. In one semester, you may take any number of courses, but every course taken in that semester must have all of its prerequisites completed in earlier semesters. Return the minimum number of semesters needed to finish all courses. If the prerequisite graph contains a cycle, return -1.

Constraints

1 <= n <= 100000
0 <= len(prereq) <= 200000
1 <= a, b <= n
All prerequisite pairs are distinct.

Examples

Input: (3, [[1, 3], [2, 3]])

Expected Output:

Explanation: Courses 1 and 2 can be taken in semester 1, then course 3 in semester 2.

Input: (4, [[1, 2], [2, 3], [3, 4]])

Expected Output:

Explanation: This is a chain, so only one new course becomes available each semester.

Input: (3, [[1, 2], [2, 3], [3, 1]])

Expected Output:

Explanation: The courses form a cycle, so no valid completion order exists.

Input: (1, [])

Expected Output:

Explanation: Edge case: a single course with no prerequisites takes one semester.

Input: (4, [])

Expected Output:

Explanation: With no prerequisites, all courses can be taken in the first semester.

Hints

Courses with zero remaining prerequisites can all be taken in the current semester.
If you process the graph level by level with topological sorting, each level corresponds to one semester.

Part 2: Minimum Semesters with at Most k Courses per Semester

You are given n courses labeled 1 through n, a list of prerequisite relations prereq, and an integer k. Each relation [a, b] means course a must be completed before course b. In one semester, you may take at most k courses, and every course taken in that semester must have all prerequisites completed in earlier semesters. Return the minimum number of semesters needed to finish all courses, or -1 if it is impossible. For this exact version, assume n is small enough for a bitmask-based search.

Constraints

1 <= n <= 15
0 <= len(prereq) <= n * (n - 1) / 2
1 <= k <= n
1 <= a, b <= n
All prerequisite pairs are distinct.

Examples

Input: (4, [[1, 4], [2, 4]], 2)

Expected Output:

Explanation: Take courses 1 and 2 first to unlock 4, then take 3 and 4 in the second semester.

Input: (4, [[1, 2], [1, 3], [2, 4], [3, 4]], 2)

Expected Output:

Explanation: Take 1, then 2 and 3, then 4.

Input: (5, [], 2)

Expected Output:

Explanation: With no prerequisites, the answer is ceil(5 / 2) = 3.

Input: (3, [[1, 2], [2, 3], [3, 1]], 2)

Expected Output:

Explanation: A cycle makes it impossible to finish all courses.

Input: (1, [], 1)

Expected Output:

Explanation: Edge case: one course and capacity 1.

Hints

Represent the set of completed courses as a bitmask.
From each state, find all currently available courses. If there are more than k, try every subset of size k and use BFS or DP to find the fewest semesters.

Quick Overview

This question evaluates graph theory and scheduling competencies, including dependency resolution, cycle detection in directed graphs, and capacity-constrained task scheduling based on prerequisites.