Check feasibility of AI course schedule
Company: Uber
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: hard
Interview Round: Onsite
You are designing a learning path for `n` AI-related courses, labeled from `0` to `n - 1`.
Some courses have prerequisites. For example, to take course `b`, you may first need to finish course `a`. This can be represented as a directed edge `a -> b`.
You are given:
- An integer `n`, the number of courses.
- A list `prerequisites` of pairs `[a, b]`, where each pair means: **to take course `b`, you must first complete course `a`**.
You need to determine whether it is possible to finish **all** courses.
Formally, model the courses as a directed graph:
- Each course is a node.
- Each prerequisite pair `[a, b]` is a directed edge from `a` to `b`.
If the graph contains a cycle (e.g., `0 -> 1 -> 2 -> 0`), then there is no way to complete all courses because each course in the cycle depends on another in the cycle.
### Task
Write an algorithm that:
- Returns `true` if it is possible to complete all `n` courses given the prerequisites.
- Returns `false` if it is **not** possible (i.e., if there is at least one cycle in the prerequisite graph).
**Constraints** (typical interview constraints; you may assume something like):
- `1 <= n <= 10^5`.
- `0 <= prerequisites.length <= 10^5`.
- `0 <= a, b < n` for every pair `[a, b]`.
Your algorithm should run in **O(n + m)** time, where `m = prerequisites.length`, and use **O(n + m)** extra space.
You may use any standard graph traversal technique (e.g., DFS or BFS/topological sort).
Quick Answer: This question evaluates competency in analyzing directed graphs and dependency resolution, focusing on cycle detection and the feasibility of ordering prerequisites for course completion.
Return true if all courses can be completed, false if prerequisites contain a cycle.
Constraints
- Inputs are Python literals matching the function signature.
- Return a deterministic exact-match value.
Examples
Input: (2, [[0,1]])
Expected Output: True
Explanation: Acyclic.
Input: (2, [[0,1],[1,0]])
Expected Output: False
Explanation: Cycle.
Input: (3, [])
Expected Output: True
Explanation: No prerequisites.
Hints
- Use deterministic tie-breaking for prompts with multiple valid outputs.
- For design-style APIs, simulate operations with explicit inputs.