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.
