Check Whether Every Course Can Be Completed Under Prerequisite Rules
Company: ByteDance
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
There are `n` courses, labeled `0` to `n - 1`. Each pair `[a, b]` in `prerequisites` means that course `b` must be completed before course `a` can be taken. Courses are taken one at a time, and each course is taken once.
Return `True` if it is possible to complete all `n` courses while respecting every prerequisite, and `False` otherwise.
### Function Signature
```python
def can_finish_all(n: int, prerequisites: list[list[int]]) -> bool:
```
### Rules
- A course can be taken only after every course it depends on has been completed.
- The answer is `True` exactly when some order of all `n` courses, with each course appearing once, places `b` before `a` for every pair `[a, b]`. Otherwise the answer is `False`.
- A course that appears in no pair has no prerequisites and can be taken at any time.
- If even one course can never be completed, the answer is `False`, even when every other course can be completed.
### Constraints
- `1 <= n <= 2000`
- `0 <= len(prerequisites) <= 5000`
- Each pair is `[a, b]` with `0 <= a < n`, `0 <= b < n` and `a != b`.
- No pair appears more than once.
### Examples
**Example 1**
```text
Input: n = 4, prerequisites = [[1, 0], [2, 0], [3, 1], [3, 2]]
Output: True
```
Courses 1 and 2 each need course 0, and course 3 needs both 1 and 2. Taking the courses in the order 0, 1, 2, 3 respects every pair.
**Example 2**
```text
Input: n = 3, prerequisites = [[0, 1], [1, 2], [2, 0]]
Output: False
```
Course 0 needs 1, course 1 needs 2, and course 2 needs 0, so none of them can be taken first.
**Example 3**
```text
Input: n = 5, prerequisites = [[1, 0], [2, 1], [3, 4], [4, 3]]
Output: False
```
Courses 0, 1 and 2 can be taken in that order, but course 3 needs 4 and course 4 needs 3, so neither of those two can ever be taken.
Overview: A graph feasibility problem: given n courses and pairs stating which course must be completed before another, decide whether every course can be finished. It tests modeling dependencies as a directed graph, recognizing circular requirements, and handling courses that fall into separate, disconnected groups.
Read the full ByteDance Software Engineer interview experience this question came from
There are `n` courses, labeled `0` to `n - 1`. Each pair `[a, b]` in `prerequisites` means that course `b` must be completed before course `a` can be taken. Courses are taken one at a time, and each course is taken exactly once.
Return `True` (`true` in JavaScript, Java and C++) if it is possible to complete all `n` courses while respecting every prerequisite, and `False` (`false`) otherwise.
### Function Signature
```python
def can_finish_all(n: int, prerequisites: list[list[int]]) -> bool:
```
### Rules
- A course can be taken only after every course it depends on has been completed.
- The answer is `True` exactly when some order of all `n` courses, with each course appearing once, places `b` before `a` for every pair `[a, b]`. Otherwise the answer is `False`.
- A course that appears in no pair has no prerequisites and can be taken at any time.
- If even one course can never be completed, the answer is `False`, even when every other course can be completed.
### Constraints
- `1 <= n <= 2000`
- `0 <= len(prerequisites) <= 5000`
- Each pair is `[a, b]` with `0 <= a < n`, `0 <= b < n` and `a != b`.
- No pair appears more than once. A pair `[a, b]` and its reverse `[b, a]` are different pairs, so both may appear (see Example 2).
- Every value fits in a 32-bit signed integer; nothing can exceed `2^31 - 1`.
### Examples
**Example 1**
```text
Input: n = 4, prerequisites = [[1, 0], [2, 0], [3, 1], [3, 2]]
Output: True
```
Courses 1 and 2 each need course 0, and course 3 needs both 1 and 2. Taking the courses in the order 0, 1, 2, 3 respects every pair.
**Example 2**
```text
Input: n = 5, prerequisites = [[1, 0], [2, 1], [3, 4], [4, 3]]
Output: False
```
Courses 0, 1 and 2 can be taken in that order, but course 3 needs 4 and course 4 needs 3, so neither of those two can ever be taken. One course that can never be completed is enough to make the answer `False`.
Constraints
- 1 <= n <= 2000
- 0 <= len(prerequisites) <= 5000
- Each pair is [a, b] with 0 <= a < n, 0 <= b < n and a != b.
- No pair appears more than once (a pair [a, b] and its reverse [b, a] are different pairs and may both appear).
- Every value fits in a 32-bit signed integer.
Examples
Input: (1, [])
Expected Output: True
Explanation: Minimum valid input: a single course with no prerequisites can be taken immediately.
Input: (5, [])
Expected Output: True
Explanation: Degenerate: five isolated courses and an empty prerequisites list; any order works.
Hints
- Picture each pair [a, b] as an arrow from course b to course a; the question becomes whether all n courses can be lined up so that every arrow points forward.
- Courses that appear in no pair never block the answer, but a single group of courses that can never be completed anywhere makes the answer False, as in Example 2.
- Ask what arrangement of pairs makes it impossible for any course in some group to be the first one of that group taken.