Amazon·Software Engineer·Technical Phone Screen·Intermediate

IntermediatePrefer not to say

Jun 2026

Summary

Amazon SWE interview with a graph theory problem that looked straightforward on paper but had more depth than I expected once they started asking about tradeoffs between approaches.

Questions Asked (1)

Given a directed graph as an adjacency list with n vertices and m edges, detect whether the graph contains a cycle. Implement a solution, explain its time and space complexity, and walk through both a DFS-with-recursion-stack approach and a topological sort approach using Kahn's algorithm.

Algorithms & Data StructuresTechnical Trade-offs

Author's notes

I started with DFS because that felt natural, tracking nodes in three states: unvisited, currently in the recursion stack, and fully processed.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Start by clarifying the graph properties (directed, possible self-loops, multiple edges) and then present two distinct approaches: DFS with recursion stack and Kahn's algorithm. For each, explain the algorithm, walk through a small example, and analyze time and space complexity. Conclude by comparing trade-offs and mentioning edge cases.

Pro tip: Emphasize that Kahn's algorithm can also produce a topological order if no cycle exists, which is useful in many applications. Also, mention that DFS recursion depth may cause stack overflow for large graphs, so an iterative version or Kahn's algorithm might be preferred in production.

1. Clarify requirements and edge cases

Ask if the graph can have self-loops or multiple edges, and confirm that we need to detect any cycle. Mention that self-loops are cycles and that the graph may be disconnected.

2. Explain DFS with recursion stack

Describe using three states (unvisited, visiting, visited) to track nodes in the current recursion stack. If a node is encountered that is already in the 'visiting' state, a cycle exists. Walk through a small example.

3. Explain Kahn's algorithm (topological sort)

Compute in-degrees, enqueue nodes with in-degree 0, and repeatedly remove nodes and decrement in-degrees of neighbors. If the number of processed nodes is less than n, a cycle exists. Walk through a small example.

4. Analyze time and space complexity

Both approaches run in O(n + m) time and use O(n + m) space for the adjacency list and auxiliary data structures. Mention that DFS recursion uses O(n) stack space in the worst case.

5. Compare trade-offs and conclude

Discuss when to prefer each: DFS is simpler to implement recursively but may risk stack overflow; Kahn's algorithm is iterative and can also produce a topological order. Mention that both are optimal for this problem.

Key Points to Mention

Three-state DFS (unvisited, visiting, visited) to detect back edges.
Kahn's algorithm uses in-degree and a queue; cycle if processed count < n.
Time complexity O(n + m) for both approaches.
Space complexity O(n + m) for adjacency list and auxiliary arrays.
Self-loops are cycles and must be handled.
Disconnected graphs: run DFS from each unvisited node or initialize queue with all in-degree 0 nodes.

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