Q6 - Returns Drop-Off Booking (Finding the Nearest Store)
We believe Amazon now mixes low-level design into its coding rounds, and candidates report rounds shaped exactly like this one: a small real service to model, written as working code rather than boxes on a whiteboard, with the interviewer steering mid-round.
Expect the steer. Candidates describe getting halfway through the booking logic before the interviewer stops them with "and how would you find the nearest store?", which is a different problem wearing the same costume. Part 1 is the design. Part 2 is that question, answered properly rather than waved at.
Scenario: Amazon Returns runs the trip in reverse. Instead of a driver collecting a return from the customer, the customer books a slot at a nearby drop store and carries the package there. You are building the service behind that booking.
Drop stores sit on an integer map grid. Each store takes a limited number of packages per time slot, because someone has to scan and cage them. Your service exposes three operations:
open_store(store_id, x, y, capacity) -> "OK" or "ERROR"
book(booking_id, x, y, slot) -> the chosen store id, or "NONE", or "ERROR"
cancel(booking_id) -> "OK" or "ERROR"
open_storeadds a store at map position(x, y)that acceptscapacitypackages in each slot. It is anERRORif thatstore_idalready exists orcapacityis not above zero.bookreserves one place for a customer standing at(x, y)in the namedslot. It is anERRORif thatbooking_idhas already been used.cancelreleases a booking and frees its place. It is anERRORif thebooking_idis unknown.
A slot is just a label, like "morning" or "18:00". Capacity is counted per store per slot, so filling a store's morning slot leaves its evening slot untouched.
Part 1: The Booking Engine
book assigns the nearest store that still has room in that slot. Rank candidates by straight-line distance from the customer, and if two are exactly the same distance away, take the one whose store_id sorts first. If no store has room, return "NONE" and reserve nothing.
📐 Compare squared distances, never square roots. (sx - x)² + (sy - y)² orders stores identically to the real distance, because squaring is monotonic for non-negative numbers. It also keeps every comparison in integers, so two stores that are genuinely equidistant tie exactly and your alphabetical tie-break fires instead of losing to a floating point rounding wobble. Say this out loud in the room; it is a small detail interviewers notice.
Example 1: capacity, slots, and cancellation
OPEN_STORE S1 0 0 capacity 1 -> OK
OPEN_STORE S2 10 10 capacity 2 -> OK
BOOK B1 customer (1,1) morning -> S1 nearest: 2 away vs 162 away
BOOK B2 customer (2,2) morning -> S2 S1's morning slot is full (capacity 1)
BOOK B3 customer (1,1) evening -> S1 different slot, so S1 has room again
CANCEL B1 -> OK frees S1's morning place
BOOK B4 customer (1,1) morning -> S1 and the freed place is reusable
Example 2: an exact tie, then running out of room
OPEN_STORE S-NORTH 5 10 capacity 1 -> OK
OPEN_STORE S-SOUTH 5 0 capacity 1 -> OK
BOOK B1 customer (5,5) morning -> S-NORTH
BOOK B2 customer (5,5) morning -> S-SOUTH
BOOK B3 customer (5,5) morning -> NONE
WHY:
both stores are squared distance 25 from (5,5), an exact tie,
so the tie-break decides: "S-NORTH" < "S-SOUTH"
B2 finds S-NORTH full and takes the other one
B3 finds both full, so nothing is reserved and the answer is NONE
Solution - Part 1
Three pieces of state, and the whole design falls out of naming them:
stores store id -> (x, y, capacity) the network
taken (store id, slot) -> places used so far the thing capacity is checked against
bookings booking id -> (store id, slot) so cancel knows what to give back
The middle one is the piece people skip. Capacity is not a property of a store, it is a property of a store in a slot, so the key has to be the pair. Get that wrong and one busy morning silently blocks the same store's evening.
book then walks the stores, skips any whose (store, slot) count has reached its capacity, and keeps the smallest (squared distance, store id) pair it sees. Comparing the pair gives distance first and the alphabetical tie-break second, in one comparison.
from collections import defaultdict
class ReturnsNetwork:
def __init__(self):
self.stores = {} # store id -> (x, y, capacity)
self.taken = defaultdict(int) # (store id, slot) -> places used
self.bookings = {} # booking id -> (store id, slot)
def open_store(self, store_id, x, y, capacity):
if store_id in self.stores or capacity <= 0:
return "ERROR"
self.stores[store_id] = (x, y, capacity)
return "OK"
def find_nearest(self, x, y, slot):
"""Measure every store. Part 2 replaces this method and nothing else."""
best = None # (squared distance, store id)
for store_id, (sx, sy, capacity) in self.stores.items():
if self.taken[(store_id, slot)] >= capacity:
continue # this store is full for this slot
distance = (sx - x) ** 2 + (sy - y) ** 2
if best is None or (distance, store_id) < best:
best = (distance, store_id)
return best
def book(self, booking_id, x, y, slot):
if booking_id in self.bookings:
return "ERROR"
best = self.find_nearest(x, y, slot)
if best is None:
return "NONE"
chosen = best[1]
self.taken[(chosen, slot)] += 1
self.bookings[booking_id] = (chosen, slot)
return chosen
def cancel(self, booking_id):
if booking_id not in self.bookings:
return "ERROR"
store_id, slot = self.bookings.pop(booking_id)
self.taken[(store_id, slot)] -= 1
return "OK"
Complexity Analysis
open_storeandcancel:O(1). Hash lookups and a counter.book:O(S)forSstores in the network, because it measures every one of them. Fine for a few hundred stores, and the reason Part 2 exists.- Space:
O(S + B)for the stores plus the live bookings.
⏱️ Not finishing is normal here, and nobody runs your code. LLD rounds are graded on the design you talk through, so naming the state you would keep and the method you would write next counts for more than a file that compiles. Keep narrating the roadmap, because going quiet to type is what actually costs candidates in these rounds.
Part 2: Finding the Nearest Store at Fleet Scale
This is the point where the interviewer stops you. "Amazon has tens of thousands of drop stores. Are you really going to measure every one of them on every booking?"
No. The fix is the one every ride-hailing and delivery service uses: geosharding. Cut the map into square cells of side cell_size, file each store into the cell it falls in, and when a customer asks, look only at cells that could plausibly hold the winner. book keeps returning exactly the same store as Part 1, it just stops reading the whole network to do it.
cell_size is chosen once, when the network is built, and never changes. A point (x, y) then belongs to cell (x / cell_size, y / cell_size), using floor division so negative coordinates land correctly.
Step 1: File every store into a cell
cell_size = 10, so a store at (19, 19) files into cell (1, 1)
x: 0-9 x: 10-19 x: 20-29
y: 20-29 (0, 2) (1, 2) (2, 2)
y: 10-19 (0, 1) (1, 1) (2, 1)
y: 0-9 (0, 0) (1, 0) (2, 0)
Step 2: Search outward in rings
Start at the customer's own cell, then the eight cells around it, then the sixteen around those. Ring r is every cell whose Chebyshev distance from the customer's cell is exactly r, so you walk a hollow square shell each time and never re-check the middle.
customer in cell (1,1):
ring 0 ring 1 ring 2
. . . . . . . . . . 2 2 2 2 2
. . . . . . 1 1 1 . 2 . . . 2
. . 0 . . . 1 0 1 . 2 . 0 . 2
. . . . . . 1 1 1 . 2 . . . 2
. . . . . . . . . . 2 2 2 2 2
Step 3: The ring you stop on is not the ring you find something in
Here is the mistake, and it is the one worth getting right in the room. The obvious rule is "expand until a ring gives me a store, then answer." That rule is wrong, because a store one ring further out can still be closer than one in the ring you just searched.
cell_size = 10, customer at (10, 10), which is cell (1, 1)
S-FAR at (19, 19) -> cell (1, 1) the customer's OWN cell squared distance 162
S-NEAR at (10, 0) -> cell (1, 0) one ring further out squared distance 100
ring 0 is not empty, so "answer at the first ring with a hit" returns S-FAR
but S-NEAR is closer, and the correct answer is S-NEAR
Two corners of the same cell can be nearly cell_size * 1.41 apart, while the cell next door starts right at the boundary. So being in a nearer cell does not make a store nearer.
The rule that is correct: a cell in ring r cannot contain any point closer than (r - 1) * cell_size to the customer, because the customer sits somewhere inside ring 0's cell. So keep expanding until the best distance you already hold beats that floor.
cell_size = 10, so the floor distance per ring is:
ring 1 -> at least 0 away squared 0 anything can still win
ring 2 -> at least 10 away squared 100
ring 3 -> at least 20 away squared 400
after ring 1 the best is S-NEAR at squared distance 100
ring 2's floor is 100, and 100 <= 100, so no later ring can beat it -> stop
We measured how often the shortcut actually bites: across tens of thousands of random lookups it returned the wrong store in roughly four percent of them. That is exactly the kind of bug that never shows up in a demo and generates support tickets forever.
🎛️ Expect to be asked how you pick cell_size. It is the whole trade-off in one number. Cells that are too big and every lookup reads half the network again; too small and you walk through empty rings before you find anything. The honest answer is that you size it against store density, aiming for a handful of stores per cell in the areas that get the most traffic, and that dense cities and empty highways want different sizes, which is why production systems reach for a quadtree or S2 cells that subdivide where the data actually is. Saying that sentence is worth more than any single number.
Solution - Part 2
Everything from Part 1 stays. Two things are added: open_store also files the store into its cell, and the scan inside book becomes a ring search.
from collections import defaultdict
class GeoShardedNetwork(ReturnsNetwork):
def __init__(self, cell_size):
super().__init__()
self.cell_size = cell_size
self.cells = defaultdict(list) # (cx, cy) -> store ids filed there
self.min_cx = self.max_cx = None # bounding box of occupied cells
self.min_cy = self.max_cy = None
def open_store(self, store_id, x, y, capacity):
result = super().open_store(store_id, x, y, capacity)
if result == "OK":
cx, cy = x // self.cell_size, y // self.cell_size
self.cells[(cx, cy)].append(store_id)
self.min_cx = cx if self.min_cx is None else min(self.min_cx, cx)
self.max_cx = cx if self.max_cx is None else max(self.max_cx, cx)
self.min_cy = cy if self.min_cy is None else min(self.min_cy, cy)
self.max_cy = cy if self.max_cy is None else max(self.max_cy, cy)
return result
def find_nearest(self, x, y, slot):
"""Same answer as Part 1's scan, without reading the whole network."""
if not self.cells:
return None
size = self.cell_size
cx, cy = x // size, y // size
max_ring = max(abs(cx - self.min_cx), abs(cx - self.max_cx),
abs(cy - self.min_cy), abs(cy - self.max_cy))
best = None # (squared distance, store id)
for ring in range(max_ring + 1):
if best is not None and ring >= 1:
floor_distance = ((ring - 1) * size) ** 2
if best[0] <= floor_distance:
break # no later ring can beat what we hold
for cell_x in range(cx - ring, cx + ring + 1):
for cell_y in range(cy - ring, cy + ring + 1):
if max(abs(cell_x - cx), abs(cell_y - cy)) != ring:
continue # walk the hollow shell only
for store_id in self.cells.get((cell_x, cell_y), ()):
sx, sy, capacity = self.stores[store_id]
if self.taken[(store_id, slot)] >= capacity:
continue
distance = (sx - x) ** 2 + (sy - y) ** 2
if best is None or (distance, store_id) < best:
best = (distance, store_id)
return best
Complexity Analysis
bookafter sharding:O(stores actually read), which in a network with roughly even density is the handful of stores inside the few rings you touch, not the wholeS. The worst case is stillO(S), when every store sits in one cell or the only store with room is on the far side of the map, and saying that out loud is better than claiming a bound you cannot defend.open_store:O(1), one extra append into a cell bucket.- Space:
O(S)for the index. Each store is filed exactly once. - The cell index never changes the answer, only the amount of reading. That equivalence is the thing to state, and the thing to test.
Final Notes
We believe this question, and close variations of it, have appeared in recent Amazon interviews, where low-level design is increasingly folded into the coding round rather than kept in a separate session. It rewards clean modeling first and a real answer to the scaling follow-up second, which is exactly the order the round runs in.
- Capacity belongs to a store and a slot. The single most common modeling slip is hanging the counter off the store alone, which makes a busy morning close the same store's evening and gives you no error to chase. Key it by the pair and the rest of the design stops fighting you.
- Keep a booking's destination, not just its existence.
cancelhas to give a place back to a specific(store, slot), so the booking record has to remember which one it took. Storing only the booking id leaves you unable to undo anything. - Compare squared distances. No square roots, integer comparisons throughout, and exact ties so the alphabetical tie-break actually decides them rather than floating point noise.
- Finding the first store is not finding the nearest store. The ring you get a hit in is rarely the ring you can stop on, because a cell one step further out starts closer to you than the far corner of your own cell. Expand until the best you hold beats the next ring's floor of
(r - 1) * cell_size. - The follow-up is the round. Candidates report getting the booking logic mostly written and then being pushed on the nearest-store question with a nudge toward how ride-hailing apps do it. Having "bucket the map into cells, search outward, stop when the next ring cannot win" ready as a sentence is what turns that moment from a stall into the strongest part of the interview.
What makes this one worth practising is that both halves are ordinary. Hash maps, a loop, a bounded search. What is being measured is whether you can hold a small service in your head, name its state precisely, and then keep the answers identical while making the lookup cheap. That is most of what building on a real fleet actually feels like. 🚀