← Amazon Interview Insights

Amazon·Software Engineer·Onsite - Coding / Algorithms·Intermediate

Intermediate
Jun 2026

Summary

Amazon SWE coding round, one graph problem that looks approachable until you realize you need to handle cycles properly. Pretty standard for this type of interview but the details matter.

Questions Asked (1)

Q1

Given a list of course prerequisites where each pair [a, b] means b must be taken before a, return a valid ordering to complete all courses. If no valid ordering exists, return an empty array.

Algorithms & Data Structures
Author's notes

I went with the BFS in-degree approach first since it naturally handles the impossible case by just checking if you've processed all nodes.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Model the courses and prerequisites as a directed graph and perform a topological sort using Kahn's algorithm (BFS with in-degree tracking). If the topological order contains all courses, return it; otherwise, a cycle exists, so return an empty array.

Pro tip: Explicitly mention that you're using Kahn's algorithm because it naturally detects cycles (if the result size is less than the number of courses) and avoids recursion depth issues, which is important for large inputs at Amazon scale.

1. Clarify and model the problem

Confirm that prerequisites are given as pairs [a, b] meaning b before a, and that courses are labeled 0 to n-1. Build an adjacency list and an in-degree array to represent the graph.

2. Initialize and process sources

Add all courses with in-degree 0 to a queue. These are courses with no prerequisites and can be taken first.

3. Perform topological sort

While the queue is not empty, dequeue a course, add it to the result, and for each neighbor, decrement its in-degree. If a neighbor's in-degree becomes 0, enqueue it.

4. Check for cycles and return result

If the result contains all courses, return it as a valid ordering. Otherwise, a cycle exists, so return an empty array.

Key Points to Mention

  • Graph representation: adjacency list and in-degree array
  • Topological sorting using Kahn's algorithm (BFS-based)
  • Cycle detection: if processed courses < total courses, return empty array
  • Time and space complexity: O(V + E) time, O(V + E) space
  • Handling edge cases: empty input, no prerequisites, disconnected components
  • Alternative approach: DFS with recursion stack for cycle detection (mention trade-offs)

AI-generated suggestions, not part of the candidate's original notes. May be inaccurate — verify before relying on them.