Amazon·Software Engineer·Online Assessment (OA)·Intermediate

Intermediate

Jun 2026

Summary

Amazon SWE online assessment, one algorithmic problem centered on topological sort for course scheduling. Pretty standard graph problem but the cycle detection edge case tripped me up more than I expected.

Questions Asked (1)

Given n courses labeled 0 to n-1 and a list of prerequisite pairs where [a, b] means b must come before a, return any valid ordering of all courses that satisfies the prerequisites. If no valid ordering exists (i.e. there's a cycle), return an empty array.

Algorithms & Data Structures

Author's notes

Knew immediately it was topological sort, which felt reassuring.

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 n courses, return it; otherwise, a cycle exists and return an empty array.

Pro tip: Explicitly mention that you're using Kahn's algorithm because it naturally detects cycles by checking if the processed count equals n, and it's iterative, avoiding recursion depth issues. Also, clarify that the problem guarantees a unique solution only if the graph is a DAG, so any valid topological order is acceptable.

1. Clarify and Model the Problem

Confirm that the input is a list of prerequisite pairs and that we need any valid ordering. Build a directed graph where an edge from b to a indicates b must come before a, and compute in-degrees for each node.

2. Initialize Data Structures

Create an adjacency list for the graph, an array to store in-degrees, and a queue for nodes with in-degree 0. Also prepare a result list to store the topological order.

3. Perform Topological Sort (Kahn's Algorithm)

Enqueue all nodes with in-degree 0. While the queue is not empty, dequeue a node, add it to the result, and for each neighbor, decrement its in-degree; if it becomes 0, enqueue it.

4. Check for Cycles and Return Result

After processing, if the result contains all n courses, return it; otherwise, a cycle exists, so return an empty array.

Key Points to Mention

Graph representation: adjacency list and in-degree array.
Kahn's algorithm (BFS-based topological sort) vs. DFS-based approach.
Cycle detection: if the number of processed nodes is less than n, a cycle exists.
Time and space complexity: O(V+E) time, O(V+E) space.
Handling edge cases: empty input, no prerequisites, multiple valid orderings.
Why returning any valid order is acceptable (problem statement allows it).

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