Amazon·Software Engineer·Technical Phone Screen·Intermediate

Intermediate

May 2026

Summary

Amazon SWE coding round, one question, graph-based. Nothing too wild but it required knowing your way around topological sort.

Questions Asked (1)

Given a list of courses with prerequisites, return a valid order in which all courses can be completed.

Algorithms & Data Structures

Author's notes

Classic topological sort.

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 to find a valid order. Use Kahn's algorithm (BFS with in-degree tracking) or DFS with cycle detection, and clearly explain how you handle cycles (return empty if impossible).

Pro tip: Mention that you would first clarify edge cases like duplicate prerequisites, disconnected components, and whether the input is guaranteed to be a DAG. Also, discuss the trade-offs between Kahn's algorithm and DFS-based topological sort in terms of simplicity and cycle detection.

1. Clarify the problem and edge cases

Ask questions to confirm input format, whether all courses are listed, if prerequisites can be duplicated, and if a cycle is possible. This shows attention to detail and avoids assumptions.

2. Model as a graph

Represent courses as nodes and prerequisites as directed edges (e.g., if course A requires B, edge B -> A). Build an adjacency list and compute in-degrees for each node.

3. Choose a topological sort algorithm

Select either Kahn's algorithm (BFS) or DFS-based topological sort. Explain your choice, considering factors like cycle detection and ease of implementation.

4. Implement and handle cycles

Execute the algorithm, ensuring that if a cycle exists, you detect it (e.g., if the result size is less than the number of courses) and return an empty list or appropriate error.

5. Analyze complexity and test

State the time and space complexity (O(V+E)), and walk through a small example to verify correctness, including a case with a cycle.

Key Points to Mention

Topological sorting is the core concept for ordering tasks with dependencies.
Kahn's algorithm uses in-degree and a queue; DFS uses recursion and a stack.
Cycle detection is crucial: if a cycle exists, no valid order is possible.
Time and space complexity: O(V + E) for both algorithms.
Handling disconnected components: the algorithm should still produce a valid order if no cycles.
Edge cases: empty input, single course, duplicate prerequisites, and self-loops.

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