Amazon OA 2026
Summary
I attempted two questions in the Amazon online assessment; I devised an optimal algorithm for the first BFS/ binary search problem and partially solved the second package tracking implementation.
Full Experience
FIRST QUESTION
Given an $N \times M$ city grid, delivery centers are marked as 1 and houses as 0. Inconvenience is defined by the maximum Chebyshev distance (allowing 8-directional/diagonal movement) from any house to its nearest delivery center.
Find the absolute minimum possible maximum inconvenience by strategically adding at most one new delivery center.
A brute-force simulation – placing a new center at every single empty cell and running a search – costs a massive $O((N \times M)^2)$ time complexity. For a $500 \times 500$ grid, that translates to over 62 billion operations. Result? An instant Time Limit Exceeded (TLE).
Optimal approach:
- Multi-source BFS: Instead of processing houses individually, we fire up an 8-directional multi-source BFS starting from all existing delivery centers simultaneously to build a baseline distance map in $O(N \times M)$.
- Binary Search on Answer (Minimax): Since we want to minimize a maximum value, we binary search the allowed inconvenience level $K$.
- Geometric Boundary Bounding: For a guessed $K$, we dynamically track the geometric overlap of bounding boxes for all violating houses. If a valid intersection containing a 0 exists, that $K$ is achievable!
The complexity plummeted to a crisp $O(N \times M \log(\max(N,M)))$.
SECOND QUESTION
AI-assisted development round designed to test real-world software engineering skills under a tight feedback loop.
Rather than standard competitive programming puzzles, this round simulated an actual production codebase scenario with automated test feedback.
The assignment was to build a high-performance Package Tracking & Status Aggregator Engine in C++.
I was given a dual-dataset structure:
- A master list of shipments containing delivery rules and deadlines (JSON).
- A continuous, sequential stream of live carrier scanner events (JSONL).
The goal? Aggregate the raw scanner data to calculate the current location, resolve the final delivery state (ON_TIME, LATE, PENDING), and output an alphabetically ordered ledger of tracking IDs.
I could solve only 3/6 test cases for this question. I chose C++ over Node.js, Django, or SpringBoot. Not hoping to hear back.
Interview Questions (2)
Minimize Maximum Chebyshev Distance with One Additional Delivery Center
Given an $N \times M$ city grid where delivery centers are marked as 1 and houses as 0, define inconvenience as the maximum Chebyshev distance (8-directional) from any house to its nearest delivery center. Add at most one new delivery center to minimize the maximum inconvenience. Provide the minimum possible maximum inconvenience.
Package Tracking & Status Aggregator Engine
Build a high-performance engine that consumes a master JSON list of shipments (with delivery rules and deadlines) and a live JSONL stream of carrier scanner events. The engine must aggregate scanner data to determine the current location of each shipment, resolve the final delivery state (ON_TIME, LATE, PENDING), and output an alphabetically ordered ledger of tracking IDs.