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 Machine Learning Engineer candidates at Amazon during technical interviews.

Determine if all courses can be completed

Company: Amazon

Role: Machine Learning Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Technical Screen

You are building a planner for a training program with `n` courses labeled `0` through `n - 1`. You are given a list of prerequisite pairs `prerequisites`, where each pair `[course, prerequisite]` means `prerequisite` must be completed before `course` can be taken. Write a function that returns `true` if it is possible to complete all courses, and `false` otherwise. Clarifications: - A course may have multiple prerequisites. - The prerequisite graph may contain disconnected components. - If there is a dependency cycle, not all courses can be completed. Example: ```text n = 4 prerequisites = [[1, 0], [2, 1], [3, 2]] Output: true ``` Example: ```text n = 2 prerequisites = [[0, 1], [1, 0]] Output: false ```

Quick Answer: This question evaluates graph-theoretic dependency modeling and cycle-detection competency, measuring the ability to represent course prerequisites as a directed graph within the Coding & Algorithms domain for a Machine Learning Engineer role.

You are building a planner for a training program with n courses labeled 0 through n - 1. You are given a list of prerequisite pairs prerequisites, where each pair [course, prerequisite] means prerequisite must be completed before course can be taken. Return True if it is possible to complete all courses, and False otherwise. A course may have multiple prerequisites, the prerequisite graph may contain disconnected components, and any dependency cycle makes it impossible to complete all courses.

Constraints

0 <= n <= 100000
0 <= len(prerequisites) <= 200000
Each prerequisite pair has exactly two integers: [course, prerequisite]
0 <= course, prerequisite < n
A course may have multiple prerequisites
The prerequisite graph may be disconnected

Examples

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

Expected Output: True

Explanation: The courses can be completed in order 0, 1, 2, 3.

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

Expected Output: False

Explanation: Course 0 requires course 1, and course 1 requires course 0, forming a cycle.

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

Expected Output: True

Explanation: Course 0 can be completed first, then courses 1 and 2, then course 3. Course 4 is disconnected and can be completed anytime.

Input: (3, [])

Expected Output: True

Explanation: There are no prerequisites, so every course can be completed.

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

Expected Output: False

Explanation: The only course depends on itself, creating a cycle.

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

Expected Output: False

Explanation: Although courses 0, 1, and 2 can be completed, courses 3 and 4 form a disconnected cycle.

Input: (0, [])

Expected Output: True

Explanation: With no courses, there is nothing to complete.

Hints

Model the courses as a directed graph where each prerequisite points to the course that depends on it.
If you repeatedly take courses with no remaining prerequisites, what does it mean if some courses can never be taken?

Quick Overview

This question evaluates graph-theoretic dependency modeling and cycle-detection competency, measuring the ability to represent course prerequisites as a directed graph within the Coding & Algorithms domain for a Machine Learning Engineer role.