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 Technical Screen rounds at Amazon.

What role is this question designed for?

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

Course Prerequisite Feasibility | Amazon Coding Question

Quick Overview

This question tests graph theory fundamentals, specifically cycle detection in directed graphs as modeled by dependency constraints. It evaluates practical understanding of topological sorting and the ability to recognize circular dependencies — a core concept frequently assessed in software engineering interviews for roles requiring algorithmic reasoning.

Course Prerequisite Feasibility

Company: Amazon

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Technical Screen

## Course Prerequisite Feasibility You are given an integer `n` representing the number of courses, labeled from `0` to `n - 1`. You are also given a list `prerequisites`, where `prerequisites[i] = [a, b]` means that **in order to take course `a`, you must first complete course `b`**. Determine whether it is possible to finish **all** `n` courses given these prerequisite constraints. Return `true` if it is possible, and `false` otherwise. A schedule is infeasible if and only if there is a circular dependency among the courses (for example, course `a` requires `b`, `b` requires `c`, and `c` requires `a`). ### Examples **Example 1** ``` Input: n = 2, prerequisites = [[1, 0]] Output: true Explanation: Take course 0 first, then course 1. ``` **Example 2** ``` Input: n = 2, prerequisites = [[1, 0], [0, 1]] Output: false Explanation: Course 1 requires course 0, and course 0 requires course 1 — a cycle, so neither can be taken. ``` **Example 3** ``` Input: n = 4, prerequisites = [[1, 0], [2, 0], [3, 1], [3, 2]] Output: true Explanation: A valid order is 0, 1, 2, 3. ``` ### Constraints - `1 <= n <= 2000` - `0 <= prerequisites.length <= n * (n - 1)` - `prerequisites[i].length == 2` - `0 <= a, b < n` - All prerequisite pairs `[a, b]` are distinct. - Self-dependencies may appear (e.g. `[a, a]`), which immediately make the schedule infeasible. ### Required Output Return a boolean: `true` if all `n` courses can be completed, otherwise `false`.

Quick Answer: This question tests graph theory fundamentals, specifically cycle detection in directed graphs as modeled by dependency constraints. It evaluates practical understanding of topological sorting and the ability to recognize circular dependencies — a core concept frequently assessed in software engineering interviews for roles requiring algorithmic reasoning.

You are given an integer `n` representing the number of courses, labeled from `0` to `n - 1`. You are also given a list `prerequisites`, where `prerequisites[i] = [a, b]` means that **in order to take course `a`, you must first complete course `b`**. Determine whether it is possible to finish **all** `n` courses given these prerequisite constraints. Return `true` if it is possible, and `false` otherwise. A schedule is infeasible if and only if there is a circular dependency among the courses (for example, course `a` requires `b`, `b` requires `c`, and `c` requires `a`). Self-dependencies (e.g. `[a, a]`) immediately make the schedule infeasible.

Constraints

1 <= n <= 2000
0 <= prerequisites.length <= n * (n - 1)
prerequisites[i].length == 2
0 <= a, b < n
All prerequisite pairs [a, b] are distinct.
Self-dependencies may appear (e.g. [a, a]), which immediately make the schedule infeasible.

Examples

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

Expected Output: True

Explanation: Course 1 requires course 0. Take 0 first, then 1. Feasible.

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

Expected Output: False

Explanation: Course 1 requires 0 and course 0 requires 1 — a 2-cycle. Neither can ever be taken first.

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

Expected Output: True

Explanation: A valid order is 0, 1, 2, 3. No cycle exists.

Input: (1, [])

Expected Output: True

Explanation: Single course with no prerequisites is trivially completable.

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

Expected Output: False

Explanation: Self-dependency: course 0 requires course 0. Its indegree never reaches 0, so it's infeasible.

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

Expected Output: False

Explanation: A 3-node cycle 0 -> 1 -> 2 -> 0. None of the courses can be scheduled.

Input: (5, [])

Expected Output: True

Explanation: Five independent courses with no prerequisites — all can be completed in any order.

Hints

Model the courses as a directed graph: an edge b -> a means course b must be completed before course a. The schedule is feasible if and only if this graph has no cycle.
Cycle detection on a directed graph can be done with topological sort. Kahn's algorithm (BFS using indegrees) is a clean approach: repeatedly remove nodes with indegree 0.
Count how many nodes you successfully remove. If you can topologically order all n courses, return true; if some nodes can never reach indegree 0 (they are stuck in a cycle), the count will be less than n, so return false. Note a self-loop [a, a] gives course a an indegree it can never shed.

Quick Overview