Amazon·Software Engineer·Technical Phone Screen·Intermediate

Intermediate

May 2026

Summary

Amazon SWE coding round with a graph/pathfinding problem disguised as a database table. Pretty clean problem once you see what it's actually asking, but the setup threw me off at first.

Questions Asked (1)

Given a table of user navigation records (each row has a user ID, a source URL, and a destination URL), write a function to determine whether a path exists from one URL to another using only the connections recorded in the table.

Algorithms & Data StructuresData Modeling

Author's notes

Took me a beat to realize this is just a graph reachability problem.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Model the navigation records as a directed graph where URLs are nodes and each record is a directed edge from source to destination. Then use a graph traversal algorithm (BFS or DFS) starting from the source URL to determine if the destination URL is reachable. Discuss trade-offs between BFS and DFS, and consider edge cases like cycles and disconnected components.

Pro tip: Clarify upfront whether the graph is static or dynamic, and whether you need to handle multiple queries efficiently. Mentioning that you'd preprocess the graph (e.g., build an adjacency list) for repeated queries shows you think about scalability.

1. Clarify requirements and assumptions

Ask about the size of the data, whether the graph is directed, if there are cycles, and if multiple queries will be made. Confirm the expected input/output format.

2. Model as a graph

Represent each unique URL as a node and each navigation record as a directed edge from source to destination. Build an adjacency list for efficient traversal.

3. Choose traversal algorithm

Select BFS or DFS based on requirements. BFS finds the shortest path in terms of edges, while DFS uses less memory for deep graphs. Both can determine reachability.

4. Implement traversal with visited set

Traverse from the source URL, keeping track of visited nodes to avoid infinite loops in cyclic graphs. Return true if the destination is reached, false otherwise.

5. Analyze complexity and edge cases

State time and space complexity: O(V+E) for traversal, O(V+E) space for adjacency list. Discuss edge cases: source equals destination, missing URLs, empty table, and disconnected graphs.

Key Points to Mention

Graph representation: adjacency list vs. adjacency matrix, and why adjacency list is preferred for sparse graphs.
BFS vs. DFS: trade-offs in terms of time, space, and path optimality.
Handling cycles with a visited set to prevent infinite loops.
Time and space complexity analysis: O(V+E) time, O(V+E) space.
Edge cases: source equals destination, non-existent URLs, empty input, and multiple queries.
Scalability considerations: preprocessing for multiple queries, using distributed graph processing for very large datasets.

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