Amazon·Software Engineer·Technical Phone Screen·Intermediate

IntermediatePrefer not to say

Jun 2026Remote

Summary

Amazon SWE interview with a grid-based BFS problem that looks deceptively simple until you actually have to explain correctness and complexity out loud. One round, pretty focused.

Questions Asked (1)

You're given an m×n grid where cells are either empty (0), fresh fruit (1), or spoiled fruit (2). Every minute, fresh fruit adjacent to spoiled fruit becomes spoiled. Return the minimum number of minutes to spoil all fresh fruit, or -1 if it's impossible. Describe your algorithm, argue why it's correct, analyze time and space complexity, then implement it.

Algorithms & Data StructuresTechnical Trade-offs

Author's notes

Multi-source BFS from all initially spoiled cells simultaneously, that part came to me pretty fast.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

This is a classic multi-source BFS problem: treat all initially spoiled fruits as sources and expand level by level, counting minutes. After BFS, check if any fresh fruit remains; if so, return -1, else return the number of minutes elapsed.

Pro tip: Mention that BFS is optimal because each minute corresponds to one level of expansion, and using a queue ensures we process all cells at the current minute before moving to the next. Also, note that you can optimize space by reusing the grid to mark visited cells.

1. Clarify and Model

Confirm grid dimensions, movement allowed (4-directional), and that spoilage spreads simultaneously. Model the problem as a graph where each cell is a node and edges connect adjacent cells.

2. Initialize BFS

Scan the grid to count fresh fruits and enqueue all spoiled fruit cells with their initial minute (0). Use a queue for BFS.

3. BFS Expansion

While the queue is not empty, process cells level by level (minute by minute). For each spoiled cell, check its 4 neighbors; if a neighbor is fresh, mark it spoiled, decrement fresh count, and enqueue it with minute+1.

4. Termination and Result

After BFS, if fresh count > 0, return -1 (impossible). Otherwise, return the maximum minute reached (or minutes elapsed).

5. Complexity Analysis

Time: O(m*n) since each cell is processed once. Space: O(m*n) for the queue in worst case (e.g., all spoiled initially).

Key Points to Mention

Multi-source BFS is the optimal approach because it simulates simultaneous spreading.
Use a queue to process cells in order of their spoilage time (level order).
Track the number of fresh fruits to quickly determine if all are spoiled.
Avoid revisiting cells by marking them spoiled (or using a visited set).
Time complexity is O(m*n) and space complexity is O(m*n) due to the queue.
Edge cases: no fresh fruit (return 0), no spoiled fruit (return -1 if fresh exist), disconnected components.

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