Coding interview: Design a restaurant table reservation module

Prompt and suitable context

This is a low-level design and coding question. The goal is to turn reservations, tables, time intervals, and a waitlist into objects with clear responsibilities. Public interview reports have included restaurant reservation design, while OOD guides emphasize clarifying scope, listing requirements, then choosing objects and interfaces. Assume one restaurant, fixed opening hours, and an in-memory module; add persistence and concurrency controls if the interviewer asks.

What the interviewer evaluates

• Whether you separate Restaurant, Table, Reservation, Waitlist, and allocation policy.
• Whether you correctly handle half-open intervals, capacity, table combinations, and release after cancellation.
• Whether you design a state machine, idempotent requests, and no double assignment under concurrency.
• Whether tests cover boundaries and you can explain complexity and extension points.

Clarifications to ask first

Ask whether guests choose a specific table or only party size, and whether tables may be combined. Clarify reservation duration and cleanup buffer, edits, late arrivals, no-shows, walk-ins, waitlist ordering, and request retries. Confirm time precision, timezone, single versus multiple restaurants, and whether cross-process persistence is required.

A 30-second answer framework

I would define an immutable TimeRange and reservation state machine first. AvailabilityService handles conflict queries, TableAllocator chooses by capacity and policy, ReservationService orchestrates create, cancel, and notifications, and Waitlist manages candidates separately. Creation uses an idempotency key and checks availability again inside the same critical section before occupying a table. Cancellation permits only valid transitions and releases capacity. Tests cover adjacent intervals, concurrent requests, repeated cancellation, and waitlist promotion.

Step-by-step deep answer

1. Model time, tables, and reservation states

Represent a reservation with a half-open interval [start, end), requiring start < end. Two intervals overlap when a.start < b.end && b.start < a.end. Table stores capacity, identifier, and availability; Reservation stores guest, party size, interval, table, and state. States can be HELD, CONFIRMED, SEATED, CANCELLED, and NO_SHOW; reject invalid transitions.

2. Make allocation replaceable

TableAllocator receives candidate tables and a request. The default picks the smallest table that fits, avoiding waste; other policies can prefer adjacent tables or accessibility. The allocator does not write reservations, keeping search, decision, and persistence separate instead of creating one giant class.

3. Implement conflict checks and creation

Filter by restaurant, interval, and table index, then let the allocator choose. Creation validates input, applies the cleanup buffer, creates an idempotency key, and rereads availability inside one lock or transaction before writing. It cannot trust a stale search result. The invariant is explicit: one table has zero overlapping CONFIRMED reservations.

create(request, key):
  if idempotency.exists(key): return idempotency.result(key)
  range = TimeRange(request.start, request.end + cleanupBuffer)
  lock(restaurantId, range):
    table = allocator.choose(availableTables(range), request.partySize)
    if table is null: return WAITLISTED
    reservation = Reservation.confirm(request, table, range)
    store(reservation)
    idempotency.save(key, reservation.id)
    return reservation

4. Handle cancellation, lateness, and promotion

Cancellation allows only HELD or CONFIRMED to become CANCELLED; repeating it returns the same result and does not duplicate notifications. Arrival changes the state to SEATED; a policy timeout can make it NO_SHOW and release the table. A WaitlistMatcher consumes release events, matches by wait time, party size, and priority, then reuses the same creation critical section so a new booking cannot double-assign the table.

5. Test and explain complexity

Test that adjacent [19:00,20:00) and [20:00,21:00) intervals do not conflict, reverse input is rejected, cleanup expands conflicts, a repeated idempotency key creates no extra reservation, cancellation promotes at most once, and concurrent creation has one winner. If each table stores sorted reservations, one-table conflict lookup is O(log n + k); with m candidate tables, selection and writes are about O(m log n). Capacity buckets or interval indexes can improve it.

High-quality sample answer

I would model an immutable half-open TimeRange, an explicit reservation state machine, and a replaceable allocation policy. AvailabilityService filters by restaurant, time, and table; TableAllocator picks the smallest sufficient table; ReservationService rereads and writes inside one lock or transaction using an idempotency key. Cancellation, lateness, and no-show release capacity through valid transitions, and waitlist matching reuses the same critical section. Tests cover adjacent intervals, cleanup buffers, repeated cancellation, concurrent creation, and waitlist races, with indexed complexity stated.

Common mistakes

• Putting all logic in Restaurant with unclear responsibilities and policy replacement.
• Using closed intervals and incorrectly marking adjacent reservations as conflicts.
• Searching for availability and writing later without rechecking at the write boundary.
• Making cancellation non-idempotent so retries release tables or notify twice.
• Implementing only guest booking while ignoring walk-ins, lateness, no-shows, and waitlists.
• Showing only a class diagram without invariants, boundary tests, or complexity.

Follow-up questions and responses

How would you support combined tables?

Return an ordered table set rather than one tableId, adding constraints for total capacity, connectability, and conflicts across the set. Keep the allocator interface and add a ComposableTableAllocator implementation.

How do you prevent double booking across processes?

Move the conflict invariant into persistence with a verifiable lock or transactional constraint on table and time. An application lock can reduce contention but cannot be the only correctness guarantee.

What if a user clicks create repeatedly?

Require a client idempotency key and store the result by restaurant and user scope. The same key returns the original reservation; a different key still goes through the shared conflict check. Rate limiting is not a substitute for business idempotency.

How do you optimize a popular dinner slot?

Shard by restaurant and time. Use cache only for search hints; final creation remains in a strongly consistent critical section. Precomputed capacity buckets and waitlist candidates still need a version check before writing.

What if notification fails after cancellation?

Commit the state change and an outbox event in one transaction; make notification consumers idempotent and retryable. Releasing the table must not wait for SMS success; failures go to retry and an operator-visible dead-letter queue.