Design a restaurant waitlist

01The design, in the six-step framework

1. Requirements

This question is usually a hybrid: the interviewer hands you four or five function signatures (join, leave, seat, estimate, notify) and expects both a working data structure and a small backend behind it. Treat it as a design question with a coding core.

Functional

• A guest joins the waitlist for a restaurant with a party size and a phone number, and gets a position and an estimated wait.
• Staff seat a party, which removes it from the list, or mark a party as no-show after a grace period.
• A guest can leave the list; the estimate for everyone behind them updates.
• The guest is paged (SMS or push) when their table is ready, and again if they do not respond.
• Out of scope: reservations made in advance, payments, table layout optimisation.

Non-functional

• Scale: 50,000 restaurants, a busy one holds 60 parties at peak; a few thousand joins per second nationwide at Friday 7 pm.
• Latency: join and estimate under 200 ms; a page delivered within 5 seconds of a table opening.
• Consistency: within one restaurant, order is strict and a party is never seated twice or lost.
• Availability: 99.9 percent; a restaurant must keep working on a flaky connection.

2. Core entities

• Restaurant: id, name, open hours, average turn time per party size, staff accounts.
• WaitlistEntry: entry id, restaurant id, guest phone, party size, joined at, status (waiting, paged, seated, left, no-show), paged at.
• Table: id, restaurant id, capacity, status (free, occupied, cleaning), occupied since.
• Notification: entry id, channel, sent at, delivery status.

3. API

• POST /restaurants/{id}/waitlist with party size and phone; returns entry id, position, estimate in minutes. Called by the guest app or the host stand.
• GET /waitlist/{entryId} returns position, estimate and status; polled by the guest every 30 seconds or pushed over a websocket.
• DELETE /waitlist/{entryId} leaves the list.
• POST /waitlist/{entryId}/seat with a table id; staff only.
• POST /restaurants/{id}/tables/{tableId}/free when a party leaves; triggers the next page.

4. High-level design

One request, end to end:

1. The guest app posts a join. The API validates the party size and writes the entry to Postgres with status waiting.
2. The service adds the entry to a sorted set in Redis keyed by restaurant, scored by join time. The rank in the set is the position.
3. The estimate is position × the restaurant's average turn time for that party size, read from a small per-restaurant stats record.
4. When staff free a table, the service pops the first entry whose party fits, marks it paged, and publishes a page job to the queue.
5. The notifier sends the push or SMS, records the delivery, and schedules a second page after three minutes if the guest has not confirmed.

5. Deep dives

What is the data structure, and what does each function cost?

The interviewer wants you to code this part. A plain list gives O(1) join and O(n) leave and position. A sorted set keyed by join time gives O(log n) for join, leave and rank, and O(log n + k) to find the first k candidates. With n at most a few hundred per restaurant, either works; say so, then pick the sorted set because seating is not strictly first come first served: a two-top may open while a party of six is first. Seating therefore scans forward from the head for the first party that fits, which is a short range read.

Estimate is the subtle function. Position alone is not enough because parties ahead of you may be waiting for a different table size. A better estimate counts only parties ahead that compete for tables of your size, multiplied by the average turn time, divided by the number of such tables. Keep a per-restaurant rolling average of actual waits per size bucket and update it when a party is seated.

How do we avoid seating a party twice when two hosts tap at once?

Two tablets at the host stand can free a table and page the same party. Make seat and page idempotent: the transition waiting → paged → seated is done as a conditional update in Postgres (update where status = waiting), and the Redis sorted set is changed only after the row update succeeds. The second host's tap sees zero rows updated and gets a conflict response. The sorted set is a cache of truth, rebuilt from Postgres if Redis restarts.

How does the page reach the guest, and what if it does not?

The page job carries the entry id and an attempt number. The notifier sends through a provider and writes the delivery receipt. If no confirmation arrives in three minutes, a second attempt goes out; after six minutes the entry becomes no-show and the next party is paged. Guests who confirm late are re-added at the head rather than the tail, which is the policy most restaurants want. Use idempotency keys on the provider call so a retried job does not send two messages.

How does the host stand keep working when the network drops?

Restaurants have bad Wi-Fi. The tablet keeps a local copy of its own waitlist and queues mutations with client-generated entry ids. On reconnect it replays them; because every mutation is idempotent and ordered per restaurant, the server applies them once. Conflicts are rare because one restaurant's list is owned by one host stand at a time; if two stands are in use, the server's order wins and the tablet refreshes.

Where does the state live, and what happens when Redis is slow?

Postgres is the system of record and Redis is the fast index for rank and estimate. A join writes Postgres first, then Redis; if the Redis write fails, the entry still exists and a background reconciler rebuilds the sorted set for that restaurant from the rows with status waiting, ordered by joined at. Reads of position fall back to a direct query (count of waiting rows with an earlier join time), which is fine for a list of a few hundred. Shard both stores by restaurant id so one hot restaurant cannot slow another, and because every operation touches one restaurant only, no cross-shard transaction is ever needed. The notifier reads from the queue with at-least-once delivery; the entry's paged-at timestamp lets it drop a duplicate job that arrives after the guest has already been seated.

6. What a strong answer sounds like

• State up front that one restaurant's list is tiny and the hard parts are the estimate and the state machine, not scale.
• Write the four functions with their complexities, then say which structure you chose and why seating is not FIFO.
• Name the status transitions and make each one a conditional update; that is what prevents double seating.
• Give a concrete page policy: page, re-page at 3 minutes, no-show at 6, re-add confirmers at the head.
• Expect follow-ups on estimate accuracy and on multi-restaurant chains; a common mistake is to design a global queue when the unit of ordering is one restaurant.

02Where this question was reported

• LeetCode Discuss · Coding-system-design round: implement 4-5 given functions (search snippet)
• 1point3acres · Warm-up coding then restaurant waitlist system design (search snippet)