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 Amazon.

What role is this question designed for?

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

Find a Valid Course Order | Amazon Coding Question

Quick Overview

This question evaluates graph algorithm skills—specifically topological ordering, directed cycle detection, and analysis of time and space complexity. Common in Coding & Algorithms interviews, it examines reasoning about dependency resolution in directed graphs and requires practical algorithm implementation with emphasis on algorithmic complexity, placing it at the practical application and algorithmic-analysis level rather than purely conceptual understanding.

Find a Valid Course Order

Company: Amazon

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: hard

Interview Round: Onsite

You are given n courses labeled from 0 to n - 1 and a list of prerequisite pairs. Each pair [course, prerequisite] means prerequisite must be completed before course. Return any valid ordering of all courses. If no ordering is possible because the prerequisites contain a cycle, return an empty list. Implement the solution using breadth-first topological sorting and analyze the time and space complexity.

Quick Answer: This question evaluates graph algorithm skills—specifically topological ordering, directed cycle detection, and analysis of time and space complexity. Common in Coding & Algorithms interviews, it examines reasoning about dependency resolution in directed graphs and requires practical algorithm implementation with emphasis on algorithmic complexity, placing it at the practical application and algorithmic-analysis level rather than purely conceptual understanding.

You are given an integer n representing courses labeled from 0 to n - 1 and a list of prerequisite pairs. Each pair [course, prerequisite] means the prerequisite course must be completed before the course. Return a valid ordering of all courses such that every prerequisite appears before the course that depends on it. If no such ordering exists because the prerequisite graph contains a cycle, return an empty list. Implement the solution using breadth-first topological sorting (Kahn's algorithm).

Constraints

1 <= numCourses <= 100000
0 <= len(prerequisites) <= 200000
Each prerequisite pair has the form [course, prerequisite]
0 <= course, prerequisite < numCourses

Examples

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

Expected Output: [0, 1, 2, 3]

Explanation: This is a simple chain: 0 must come before 1, 1 before 2, and 2 before 3.

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

Expected Output: [0, 1]

Explanation: Course 0 must be taken before course 1.

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

Expected Output: []

Explanation: The prerequisites form a cycle: 0 -> 1 -> 2 -> 0, so no valid order exists.

Input: (1, [])

Expected Output: [0]

Explanation: With only one course and no prerequisites, the only valid order is [0].

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

Expected Output: [0, 1, 2, 3, 4]

Explanation: The dependency structure forces the order: 0 before 1, 1 before 2 and 3, 2 before 3, and 3 before 4.

Hints

Treat courses as nodes in a directed graph where prerequisite -> course.
Count how many prerequisites each course still needs, then start from all courses with zero remaining prerequisites.

Last updated: May 30, 2026

Loading coding console...