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 hard difficulty Coding & Algorithms question, commonly asked during Onsite rounds at Bytedance.

What role is this question designed for?

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

Course Schedule Feasibility | Bytedance Coding Question

Quick Overview

This question tests graph traversal skills and the ability to detect cycles in a directed graph, a core competency in algorithm interviews. It falls under graph theory and topological sorting, evaluating whether candidates can model dependency relationships and reason about feasibility conditions at scale.

Course Schedule Feasibility

Company: Bytedance

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: hard

Interview Round: Onsite

## Course Schedule Feasibility You are registering for `numCourses` courses, labeled `0` to `numCourses - 1`. Some courses have prerequisites: before you can take a given course, you must first finish all of its prerequisite courses. The prerequisites are given as a list `prerequisites`, where `prerequisites[i] = [a, b]` means that to take course `a` you must first complete course `b` (there is a directed dependency `b -> a`). Return `true` if it is possible to finish all `numCourses` courses, and `false` otherwise. It is possible to finish all courses **if and only if** there is no cyclic dependency among the prerequisites. ### Constraints & Assumptions - `1 <= numCourses <= 2000` - `0 <= prerequisites.length <= 5000` - `prerequisites[i].length == 2` - `0 <= a, b < numCourses` - All prerequisite pairs `[a, b]` are distinct. - A pair may have `a == b`, which is a self-dependency and makes finishing impossible. - The dependency graph may be disconnected (some courses have no prerequisites and no dependents). ### Example 1 - `numCourses = 2`, `prerequisites = [[1, 0]]` - Take course `0` first, then course `1`. Output: `true`. ### Example 2 - `numCourses = 2`, `prerequisites = [[1, 0], [0, 1]]` - To take `1` you need `0`, and to take `0` you need `1` — a cycle. Output: `false`. ### Example 3 - `numCourses = 4`, `prerequisites = [[1, 0], [2, 0], [3, 1], [3, 2]]` - A valid order is `0, 1, 2, 3` (course `3` after both `1` and `2`). Output: `true`. ### Required Interface Implement a function that takes the integer `numCourses` and the list of integer pairs `prerequisites`, and returns a boolean indicating whether all courses can be finished. Edge cases to handle: no prerequisites at all (always feasible), a self-loop `[a, a]` (infeasible), and a disconnected graph where one component contains a cycle.

Quick Answer: This question tests graph traversal skills and the ability to detect cycles in a directed graph, a core competency in algorithm interviews. It falls under graph theory and topological sorting, evaluating whether candidates can model dependency relationships and reason about feasibility conditions at scale.

You are registering for `numCourses` courses, labeled `0` to `numCourses - 1`. Some courses have prerequisites: before you can take a given course, you must first finish all of its prerequisite courses. The prerequisites are given as a list `prerequisites`, where `prerequisites[i] = [a, b]` means that to take course `a` you must first complete course `b` (a directed dependency `b -> a`). Return `true` if it is possible to finish all `numCourses` courses, and `false` otherwise. It is possible to finish all courses **if and only if** there is no cyclic dependency among the prerequisites. ### Examples - `numCourses = 2`, `prerequisites = [[1, 0]]` -> `true` (take 0, then 1). - `numCourses = 2`, `prerequisites = [[1, 0], [0, 1]]` -> `false` (1 needs 0 and 0 needs 1 — a cycle). - `numCourses = 4`, `prerequisites = [[1, 0], [2, 0], [3, 1], [3, 2]]` -> `true` (order 0, 1, 2, 3). ### Edge cases to handle - No prerequisites at all — always feasible. - A self-loop `[a, a]` — infeasible. - A disconnected graph where one component contains a cycle — infeasible overall.

Constraints

1 <= numCourses <= 2000
0 <= prerequisites.length <= 5000
prerequisites[i].length == 2
0 <= a, b < numCourses
All prerequisite pairs [a, b] are distinct.
A pair may have a == b (self-dependency), which makes finishing impossible.
The dependency graph may be disconnected.

Examples

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

Expected Output: True

Explanation: Take course 0 first, then course 1. No cycle, so feasible.

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

Expected Output: False

Explanation: 1 requires 0 and 0 requires 1 — a 2-node cycle, so no valid order exists.

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

Expected Output: True

Explanation: A valid order is 0, 1, 2, 3 (course 3 comes after both 1 and 2). Acyclic, so feasible.

Input: (1, [])

Expected Output: True

Explanation: No prerequisites at all — every course is immediately takeable.

Input: (3, [[0, 0]])

Expected Output: False

Explanation: Self-loop on course 0: it can never reach in-degree zero, so it's infeasible.

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

Expected Output: True

Explanation: Disconnected but acyclic graph: chain 0->1->2 plus edge 4->3. Both components are cycle-free, so all 5 courses can be finished.

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

Expected Output: False

Explanation: Courses 0, 1, 2 form a cycle (0->1->2->0). Course 3 is fine, but the cycle makes the whole schedule infeasible.

Hints

This is equivalent to asking whether a directed graph (b -> a for each [a, b]) is acyclic. All courses can be finished iff the graph has no cycle.
Use Kahn's algorithm: compute the in-degree of every course, start a queue with all zero-in-degree courses, and repeatedly remove a course and decrement its neighbors' in-degrees.
Count how many courses you successfully remove. If that count equals numCourses, the graph is acyclic (feasible); otherwise a cycle blocked some courses. A self-loop [a, a] gives course a an in-degree it can never lose, so it is naturally caught.

Quick Overview