Amazon had this on their technical screen for software engineers, and the tag is doing a lot of damage.
The problem sounds like a warm-up. Tables, a waitlist, seat people in order. Anyone who has written a queue thinks they can do this in fifteen minutes. Then you get four sentences in and hit the part where two tables free up at the same moment while a party is cancelling and an SMS is halfway out the door, and the fifteen-minute answer falls apart in front of the interviewer.
The tag is not wrong about the data structures. The data structures really are easy. The tag is wrong about what is being tested, which is whether you can keep two pieces of state consistent when four things touch them at once, and whether you know that a text message must never decide whether a table is booked.
Here is the whole problem, worked.
The problem
Design a restaurant system with a configurable set of tables and a FIFO waitlist of parties. Each party has an ID, a size, an arrival sequence, and a phone number.
When a table frees up:
Prefer the earliest waiting party whose size exactly equals the table’s capacity.
If there is no exact match, seat the earliest party that fits.
So an eight-person party that arrived at 7:40 can jump an earlier two-person party when an eight-seat table opens. That is intentional. It is the whole reason the problem is interesting.
The rest of the constraints:
One party holds at most one active waitlist entry or table assignment.
One table holds at most one active party.
SMS may fail or arrive twice, and must not determine whether the assignment commits.
Cancellation can race with seating, and you must define a deterministic winner.
For Detailed Question, You can check here: Amazon Interview Question
Ask these four questions first
Do not start drawing classes. Every one of these changes the design, and the interviewer is watching to see whether you know that.
“Can tables be combined, and can a party accept a table smaller than its size?” If tables combine, this stops being a matching problem and becomes a packing problem. Get it excluded from scope, then offer it back as an extension at the end. Free points.
“How long does a party get to confirm after the text?” This is the question that reveals there is a whole state between “assigned” and “seated.” If there is a confirmation window, you need a hold, a deadline, and a background process that reclaims expired holds. If there is no window, seating is instant and you just saved yourself a component.
“Does the exact-size preference override FIFO forever, or is aging required?” This is the strongest question in the set, because you are telling the interviewer you already spotted the starvation bug before they asked about it.
“One process, or multiple hosts?” A single process means one lock. Multiple hosts means conditional updates in a database or a single-writer leader. Answering the wrong one wastes ten minutes.
For the rest of this walkthrough: no combining, a five-minute confirmation window, aging required, single process first, then multi-host.
The state machines
Almost every failure in this problem is a state machine that was never written down. So write it down.
A party moves WAITING → NOTIFIED → SEATED → DONE, and can exit to CANCELLED or EXPIRED.
A table moves FREE → HELD → OCCUPIED → FREE.
The critical part: (party WAITING → NOTIFIED) and (table FREE → HELD) are one transition, not two. If those can ever be observed separately, you have a party holding a table that thinks it is free, or a free table that thinks it is held. Everything below exists to make that pair atomic.
class Party {
final String id;
final int size;
final long seq; // global arrival order, never reused
final String phone;
State state; // WAITING, NOTIFIED, SEATED, CANCELLED, EXPIRED
String tableId; // set only in NOTIFIED / SEATED
}
class Table {
final String id;
final int capacity;
State state; // FREE, HELD, OCCUPIED
String partyId;
long holdExpiresAt;
}
seq comes from a single AtomicLong. That one counter is what makes "earliest" a total order rather than an argument about clock skew, and it is why you never compare wall-clock arrival times.
The data structure that makes the policy cheap
This is the part people overthink. They reach for a priority queue keyed on some composite score, then spend five minutes explaining a comparator that does not actually implement the rule.
The rule is simpler than it looks. Bucket the waitlist by exact party size:
Map> bySize; // size -> FIFO of waiting parties
Each bucket is already in arrival order, because parties only ever get appended. Now both halves of the policy are almost free:
Party findBestParty(int capacity) {
// 1. exact match: the head of the exact-size bucket
Party exact = head(bySize.get(capacity));
if (exact != null) return exact;
// 2. fallback: earliest head among all buckets that fit
Party best = null;
for (int s = capacity - 1; s >= 1; s--) {
Party h = head(bySize.get(s));
if (h != null && (best == null || h.seq < best.seq)) best = h;
}
return best;
}
Say this out loud in the interview, because it is the thing that makes the loop acceptable: the fallback scan is bounded by the largest table in the restaurant, not by the number of people waiting. A restaurant has tables that seat up to maybe twenty. Twenty pointer reads is a constant. A thousand people can be waiting and the scan does not get slower.
Then add the upgrade, because interviewers like hearing the general case even when you do not need it: if party sizes were unbounded, replace the scan with a Fenwick tree over size, storing the minimum seq in each bucket. Range-min over [1, capacity], point update on insert and remove, O(log S).
One detail that matters more than it looks. head() is not peekFirst(). Cancelled parties are left in place as tombstones and skipped lazily:
Party head(Deque q) {
if (q == null) return null;
while (!q.isEmpty() && q.peekFirst().state != WAITING) q.removeFirst();
return q.peekFirst();
}
Removing a cancelled party from the middle of a deque is O(n). Tombstoning makes cancellation O(1) and each dead entry is discarded exactly once, so the amortised cost of head() stays constant. Small thing, and the kind of small thing that reads as "has actually built this."
Concurrency: use one lock, and be able to defend it
Here is where candidates hurt themselves. They hear “concurrent” and start striping locks per table, then per party, then spend the rest of the interview reasoning about acquisition order and deadlock.
Do not. A restaurant has forty tables. The critical section is a handful of pointer reads and six field writes, measured in nanoseconds. Contention is effectively zero.
void onTableFree(String tableId) {
Assignment a = null;
synchronized (lock) {
Table t = tables.get(tableId);
if (t.state != FREE) return;
Party p = findBestParty(t.capacity);
if (p == null) return;
bySize.get(p.size).removeFirst();
p.state = NOTIFIED; p.tableId = t.id;
t.state = HELD; t.partyId = p.id;
t.holdExpiresAt = now() + HOLD_WINDOW;
a = new Assignment(newId(), p.id, t.id, p.phone);
outbox.append(a); // inside the same critical section
}
notifier.wake(); // outside it
}
Two things to point at explicitly.
The outbox append is inside the lock. The assignment and the intent to notify commit together. There is no window where a table is held but nothing remembers to tell the guest.
The SMS is not. Sending a text takes hundreds of milliseconds and talks to a third party that can hang. Holding a lock across that turns a nanosecond critical section into a restaurant-wide stall. If you take one line from this article into an interview, make it that one: never hold a lock across a network call.
If the interviewer pushes for finer granularity, the answer is not to refuse. It is: shard the lock by restaurant, because restaurants are completely independent, and that is the axis that actually scales. Per-table locks buy nothing and cost a deadlock proof.
The cancellation race, decided properly
The problem explicitly asks for a deterministic winner, so give it a rule rather than a description.
The commit inside the lock is the linearization point. A cancellation that acquires the lock first wins outright. A cancellation that arrives after the assignment committed does not fail, and does not undo anything. It degrades into a release.
boolean cancel(String partyId) {
String freed = null;
synchronized (lock) {
Party p = parties.get(partyId);
switch (p.state) {
case WAITING: // cancel won
p.state = CANCELLED; // tombstone; bucket cleans up lazily
return true;
case NOTIFIED: // seating won; become a release
p.state = CANCELLED;
freed = p.tableId;
Table t = tables.get(freed);
t.state = FREE; t.partyId = null;
break;
default:
return false; // SEATED / already terminal
}
}
if (freed != null) onTableFree(freed); // re-match, outside the lock
return true;
}
The guest may still get a text for a table they cancelled off. That is correct and worth saying out loud: the alternative is delaying every notification until the cancellation window closes, which makes the whole system slower to protect against a mildly awkward text message.
The invariant to state plainly: there is no reachable state where a party is CANCELLED and a table is still HELD for it. Both writes happen under the same lock, so no observer sees a half-applied cancellation.
SMS: the outbox, and why it comes after the commit
“SMS must not determine whether the assignment commits” is not a hint. It is the answer, handed to you.
Become a Medium member
Assignment commits in memory (or in a transaction). A durable outbox record goes in with it. A separate notifier drains the outbox:
while (running) {
for (Record r : outbox.pending()) {
try {
sms.send(r.phone, text(r), /* idempotencyKey */ r.assignmentId);
outbox.markSent(r.id);
} catch (Exception e) {
outbox.backoff(r.id); // exponential, with a dead-letter cap
}
}
park();
}
Now the follow-up they will ask: what if the SMS succeeds but the notifier crashes before recording success?
Answer it without flinching. On restart the record is still PENDING, so it is sent again with the same idempotency key, and the provider deduplicates it. You cannot get exactly-once across a network boundary. What you get is at-least-once from your side plus dedup on theirs, which is exactly-once in practice.
Then name the tradeoff, because this is what a senior answer sounds like: the failure mode is a guest occasionally receiving a duplicate text. The alternative ordering, sending first and committing after, has a failure mode of a table sitting empty while the guest waits. One of those costs an eye-roll. The other costs money. Pick the eye-roll, deliberately, and say why.
Timeouts
The hold needs a reaper, or a party that never replies keeps a table locked all night.
// scheduled, every second
List freed = new ArrayList<>();
synchronized (lock) {
for (Table t : tables.values()) {
if (t.state == HELD && now() > t.holdExpiresAt) {
parties.get(t.partyId).state = EXPIRED;
t.state = FREE; t.partyId = null;
freed.add(t.id);
}
}
}
for (String id : freed) onTableFree(id);
Whether an expired party is dropped or re-queued is a business decision, not a technical one. Say that, offer re-queueing at their original seq as the guest-friendly option, and move on. Do not spend interview time on it.
Preventing starvation, which they will ask about
The exact-size preference is a starvation bug wearing a nice hat.
Picture a restaurant where every two-top is occupied by a long, leisurely dinner, but four-tops and six-tops keep turning over, and parties of four and six keep walking in. Every one of those gets an exact match. A party of two sits there for two hours while parties that arrived after them get seated repeatedly. The policy is working exactly as written, and the guest is furious.
The fix is aging, and it is small:
Party findBestParty(int capacity) {
// 0. aged parties first: anyone past the threshold takes any table that fits
Party aged = agedQueue.earliestFitting(capacity); // ordered by seq
if (aged != null) return aged;
// 1. exact match, 2. fallback ... as before
}
A party crosses into agedQueue once it has waited longer than T. Aged parties are served in arrival order and ignore the exact-match preference entirely. Note that an aged party is always the head of its own size bucket, since buckets are FIFO by seq, so removal stays O(1).
Now state the guarantee precisely, because the precision is the point. Aging does not promise a fixed wait. What it promises is this: once a party ages in, no newly arriving party can ever be seated ahead of it. The aged queue drains strictly in arrival order, so the party’s position only moves forward. Its wait is T plus the turnover time of the aged parties already ahead of it, and that set can only shrink.
That is the difference that matters. Without aging, a small party’s wait is unbounded, because the stream of later arrivals that outrank it never ends. With aging, the wait is finite and monotonically improving. Be careful not to overclaim a constant bound here, because an interviewer who is paying attention will ask you to prove it and you will not be able to.
Then frame T as the business dial it actually is. Exact matching maximises seat utilisation, which is revenue. Aging bounds the worst wait, which is whether people come back. T is where the restaurant chooses between the two, and it belongs in a config file, not in your code.
Two hosts, one table
Move the truth into the database and make the claim conditional:
BEGIN;
UPDATE tables
SET state = 'HELD', party_id = :pid, hold_expires_at = :deadline,
version = version + 1
WHERE id = :tid AND state = 'FREE' AND version = :version;
-- require exactly 1 row affected, else ROLLBACK and re-match
UPDATE parties
SET state = 'NOTIFIED', table_id = :tid
WHERE id = :pid AND state = 'WAITING';
-- require exactly 1 row affected, else ROLLBACK and re-match
INSERT INTO outbox (assignment_id, party_id, table_id, phone, state)
VALUES (:aid, :pid, :tid, :phone, 'PENDING');
COMMIT;
Two hosts race, both run the first UPDATE, exactly one sees a row count of 1. The loser sees 0, rolls back, and re-runs matching against fresh state. No distributed lock, no lease, no coordination service. The row is the lock.
The outbox insert riding along in the same transaction is what closes the last gap: the notification intent is as durable as the assignment.
But do offer the simpler option too, because at this scale it is probably the right one: elect a single seater per restaurant. One restaurant generates a handful of events per minute. A single writer removes the entire race class, and a lease in the same database is enough to elect it. Distributed correctness you did not need is still complexity you have to maintain.
If tables can be combined
This is the follow-up that changes the shape of the problem, so it is worth ninety seconds even though you scoped it out at the start.
Matching against single tables is a lookup. Matching against combinations is a search, because a party of eight might be one eight-top, or two adjacent four-tops, or a four and two twos. You are no longer picking a table, you are picking a set.
The move that keeps it tractable: precompute the valid combinations as virtual tables. Physical adjacency is fixed by the floor plan and does not change at runtime, so enumerate the joinable groups once at startup, each with capacity = sum of members. Matching then runs unchanged against a list that happens to include virtual entries.
Two things break and you should name both.
Committing a virtual table means transitioning several physical tables at once. In one process, acquire them in sorted ID order so no two commits can deadlock against each other. Across hosts, put every member row in the same conditional UPDATE transaction and require the full row count, so it is all or nothing.
The second is subtler and worth raising because it shows you thought past correctness. Seating a party of eight across two four-tops can strand the floor: you have consumed two tables that two separate parties of four could have used. That is not a bug, it is an optimisation objective, and it is where the problem stops being a data structures question and becomes bin packing. Say that you would prefer the smallest sufficient combination, and prefer a single physical table over any combination of equal capacity. Then say that anything beyond that heuristic is a scheduling problem and out of scope for a screen.
Tests, and make them race-focused
Generic test lists get generic credit. Name the races.
Policy:
The eight-person party bypasses the earlier two-person party when an eight-top opens. This is the example from the problem statement, so it is the first test.
Fallback:
No exact match, and the earliest party that fits wins, not the largest one that fits.
No double-assignment:
Free every table simultaneously from N threads, ten thousand iterations, assert no table has two parties and no party has two tables.
Cancel versus seat:
Fire cancel(p) and onTableFree(t) from two threads released by the same barrier. Assert the outcome is always one of exactly two states, never a third. The forbidden state, party CANCELLED while the table is still HELD for them, is the assertion that actually earns the point.
Crash recovery:
Kill the notifier between sms.send and markSent, restart, assert the provider records exactly one delivery for that assignment ID.
Starvation:
Build the two-top scenario above, then assert the property aging actually guarantees, which is that no party arriving after the aged party is seated before it. Testing for a fixed wait time gives you a flaky test and a claim you cannot defend.
Invariant checker:
After every operation in every test, assert each party has at most one active claim and each table has at most one active party. This single check catches more than the individual tests do, and mentioning it is worth more than three more test names.
What actually separates the answers
I have watched enough of these to see the same 5 moments decide it, and none of them are about the queue.
The first is the SMS
Candidates who put the send inside the assignment path have failed the question that was being asked, even if every other part is clean. The problem statement told you the answer in advance and they read past it.
The second is the cancellation race
“We would handle that with a lock” is not an answer. Naming a linearization point and then showing which state the loser lands in is an answer.
The third is the bounded scan
If you cannot say why looping over table sizes is acceptable, it looks like you did not notice you wrote a loop.
The fourth is starvation
Everyone can answer it once asked. Very few raise it themselves, and raising it is what makes the difference between someone implementing a policy and someone who can tell that a policy is wrong.
The fifth is the lock
Reaching for one coarse lock and defending it with numbers reads as senior. Striping locks across forty tables and then reasoning about acquisition order reads as someone who has read about concurrency but not shipped it.
The tag says easy. What it means is that there is no algorithmic trick to discover, so there is nowhere to hide. Everything you get graded on is the part most people skip.
Top comments (0)