Amazon·Software Engineer·Technical Phone Screen·Intermediate

Intermediate

Jul 2026

Summary

Amazon SWE interview with a graph propagation problem that looks straightforward until you realize the adjacency list direction is the whole trap. Solid problem if you've done the LeetCode course schedule stuff, rough if you haven't.

Questions Asked (1)

Amazon has many internal services with dependencies. Given a set of services being shut down, return all services that become unavailable, including those that depend on them transitively.

Algorithms & Data StructuresSystem DesignTechnical Trade-offs

Author's notes

The part that got me was the adjacency list direction.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Model the services and their dependencies as a directed graph, then perform a traversal (BFS or DFS) starting from the shut-down services to find all reachable nodes. The reachable set represents all services that become unavailable, including transitive dependencies.

Pro tip: Clarify edge direction upfront: if service A depends on B, the edge should point from A to B (dependent to dependency) so that traversal from shut-down services follows reverse edges to find dependents. Also discuss handling cycles and large-scale graphs with millions of services.

1. Clarify requirements and assumptions

Confirm the input format (list of services, dependency pairs), whether the graph is directed, and if there are any constraints like cycles or multiple shut-down services. Ask if the output should include the initially shut-down services.

2. Model as a graph

Represent services as nodes and dependencies as directed edges. Decide the edge direction: typically, if service A depends on B, add an edge from A to B (or reverse for traversal). Build an adjacency list for efficient traversal.

3. Traverse to find affected services

Perform BFS or DFS starting from all shut-down services. For each service, follow edges to its dependents (reverse edges if needed) and mark visited nodes. Continue until no new services are reached.

4. Handle cycles and duplicates

Use a visited set to avoid infinite loops in cyclic dependencies. Ensure each affected service is added only once to the result.

5. Analyze complexity and trade-offs

State time complexity O(V+E) and space O(V+E). Discuss iterative vs recursive DFS (stack overflow risk), and potential optimizations for distributed systems or large graphs.

Key Points to Mention

Graph representation: adjacency list vs adjacency matrix, and why adjacency list is preferred for sparse graphs.
Edge direction: clarify that if A depends on B, then B's shutdown affects A, so traversal must follow reverse edges (from dependency to dependent).
Traversal algorithm: BFS vs DFS, iterative vs recursive, and handling multiple starting nodes.
Cycle detection: using visited set to prevent infinite loops and ensure correctness.
Time and space complexity: O(V+E) for traversal, O(V+E) for storage.
Scalability: considerations for millions of services, distributed graph processing, and caching.

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