Design a Parking Lot

Alice drives into the north ramp. The board says 1 compact left. Bob enters the south ramp at the same second. Both cars are compact. Both gates call park().

If both walk away with a ticket for stall C-12, the invariant is already broken. This is an LLD interview: objects, a state machine, and one atomic assign — not a city app.

The main design question is:

How do we hand out exactly one spot per vehicle, compute a fair fee, and survive two entry gates calling park() at once?

We will start with a list of spots and watch Alice and Bob collide. Types, free lists, compare-and-set, fees, and a display board appear when that list is no longer enough. If they later say “an airport,” shard by garage id. Each garage is this design.

1. Clarify the problem

“Design a parking lot” can mean a weekend coding puzzle or a mall with six ramps. The questions that change the objects:

• One floor or many?
• Vehicle types: motorcycle, compact, large, EV?
• Hourly, flat, or progressive fees?
• Drive-up only, or reservations too?
• Can a large car take two compact spots? (Usually no.)
• Can a motorcycle sit in a compact stall?
• How many entry and exit gates?
• What if the driver loses the ticket?
• Do we need a live display board?

If the interviewer gives no extra constraints, I would state:

Floors              Several, each with numbered spots
Types               MOTORCYCLE, COMPACT, LARGE, EV
Assignment          Exact type first; fallback is a stated product choice
Nearest-spot        Optional; correctness does not depend on it
Fee                 Hourly by vehicle type, billed at exit
Reservation         Out of scope (hold = booking)
Payment             Cash/card at the gate; mocked
Identity            Ticket id is the lock, not the plate alone
Gates               Many threads, one lot object

ANPR cameras, monthly passes, and indoor maps are extensions. Say so and move on.

2. Functional requirements

The system must:

1. Park a vehicle and issue a ticket that names one spot.
2. Leave with that ticket, charge a fee, and free the spot.
3. Report free count by type and by floor.
4. Reject park when nothing fits that vehicle.
5. Never assign the same spot to two open tickets.

Not in v1: stall-level GPS, cameras as source of truth, monthly permits, phone reservations. Those sit on the same spot and ticket model. They do not change the assign.

3. Non-functional requirements

This is not a 50k QPS problem. Interviewers want clear types and a CAS, not a cluster.

One FREE→OCCUPIED transition wins. Durability is optional until they ask to persist. Closed tickets outlive the visit.

Edge cases

• Alice and Bob both see the last compact.
• A large vehicle arrives and only compact stalls are free.
• An EV wants a charger; a compact wants any compact.
• The same plate is already inside.
• The driver loses the paper ticket.
• leave is called twice for the same ticket.
• A spot is out of service while the board still counts it.
• Exit is 61 minutes after entry.

4. Scale

Say the numbers so nobody spends the interview on QPS.

Spots                 200 – 10,000 in one garage
Gates                 2 – 8
Park + leave          a few per second at a busy mall
Tickets / day         thousands, not billions

A full scan of 10,000 spots works in a toy and is wrong once two threads scan at once. Keep closed tickets for audit, not in the free list.

If they push “scale to the airport,” do not invent Redis. Route by garage_id. Garage A and Garage B do not share a free list.

Airport
  ├── Garage A   ← this design
  ├── Garage B   ← this design
  └── Garage C   ← this design

5. Entities / what we store

Four facts, and a derived board.

Vehicle        plate, type
Spot           id, floor, type, status FREE | OCCUPIED | OUT_OF_SERVICE
Ticket         id, spot_id, plate, type, issued_at, exited_at, fee, status
ParkingLot     floors, pricing table, gates share one instance
Receipt        ticket_id, fee, hours, paid_at     (return value, not a new truth)

A ticket is the source of truth for “who is in C-12.” The spot row is occupancy you update in the same critical section as the ticket. The display board is a count you can recompute from free lists. If the board and the free list disagree, the free list wins.

Spot C-12 FREE
  park Alice
Spot C-12 OCCUPIED  +  Ticket T1 OPEN
  leave T1
Spot C-12 FREE      +  Ticket T1 PAID (fee stored)

Do not treat the license plate as the primary key. Plates get mistyped and reused. The ticket id (t_9f3a) is what the gate scanned; the plate is how you find a lost ticket. Spot ids look like B-C-12 (floor, type letter, number).

6. APIs or class methods

In LLD you may show a service, not HTTP. Either is fine.

park(vehicle) -> Ticket
leave(ticket_id) -> Receipt
availability(floor?, type?) -> counts

Park

Request:

POST /v1/garages/g_mall/park
{ "plate": "KA01AB1234", "vehicle_type": "COMPACT" }

Response (assigned):

HTTP 201
{ "ticket_id": "t_9f3a", "spot_id": "B-C-12", "floor": 2, "issued_at": "2026-08-22T10:04:00Z" }

Response (full):

HTTP 409
{ "error": { "code": "LOT_FULL", "message": "No compact spots" } }

Already inside is 409 ALREADY_PARKED with the existing ticket_id and spot_id.

Leave

Request:

POST /v1/garages/g_mall/leave
{ "ticket_id": "t_9f3a" }

Response:

HTTP 200
{ "ticket_id": "t_9f3a", "spot_id": "B-C-12", "hours": 2, "fee": { "amount": 80, "currency": "INR" }, "exited_at": "2026-08-22T11:10:00Z" }

A second leave with the same id returns the same body. It does not free C-12 again.

Availability

Request:

GET /v1/garages/g_mall/availability?floor=2

Response:

HTTP 200
{ "floor": 2, "free": { "MOTORCYCLE": 4, "COMPACT": 1, "LARGE": 2, "EV": 1 } }

The board can read this. The gate must not. Assignment goes through park(), not through a count the driver glanced at.

7. Start with a naive list of spots — show the race

The first design everyone writes:

function park(vehicle):
  for spot in lot.spots:
    if spot.status == FREE and spot.type == vehicle.type:
      spot.status = OCCUPIED
      return new Ticket(spot, vehicle)
  throw LOT_FULL

It is easy to draw and easy to break.

Floor B, last compact

  C-11 OCC   C-12 FREE   C-13 OCC

Alice: scan, see C-12 FREE
Bob:   scan, see C-12 FREE
Alice: C-12 = OCCUPIED, ticket T1
Bob:   C-12 = OCCUPIED, ticket T2

Two tickets, one stall. The invariant “a spot has at most one OPEN ticket” is gone.

The bug is not the loop. The bug is read, then write, with no claim in between. Alice’s “I saw free” is not a reservation.

A mutex around the whole loop fixes the race and makes every gate wait on every park. A 200-spot lot will survive that. A Senior answer still names it, then replaces the scan with something that claims in one step.

naive scan + no lock     wrong
naive scan + lot mutex   correct, coarse
free-list pop            correct, O(1)
SQL CAS on one row       correct, persistable

We will use the last two. The mutex is what you say if they ask for in-memory first.

8. Allocation rules

Before we lock anything, we have to know which spots a vehicle may take. Draw the floor, then state the rule.

Floor B

  motorcycle   [ M-01 FREE ] [ M-02 OCC  ]
  compact      [ C-12 FREE ] [ C-13 OCC  ] [ C-14 OCC ]
  large        [ L-01 OCC  ] [ L-02 FREE ]
  EV charger   [ E-01 FREE ] [ E-02 OCC  ]

Two defensible policies. Pick one out loud.

Exact type only (my default):

MOTORCYCLE  → motorcycle spots
COMPACT     → compact spots
LARGE       → large spots
EV          → EV charger spots

A bike never sits in a bus stall. A sedan never sits on a charger a Leaf needs. The board matches the rule: “1 compact left” means one compact car can still park.

Fallback (uses space better, argues more):

MOTORCYCLE  → motorcycle, then compact, then large
COMPACT     → compact, then large
LARGE       → large only
EV          → EV only

A motorcycle can take C-12 if the bike row is empty. That is a product choice, not an algorithm flex. The cost: the board said one compact left, a bike took it, and the next compact gets LOT_FULL. Say that trade-off.

I would not let a large car occupy two compact stalls. You now have a geometry problem (are they adjacent?), a release problem (free both or one?), and a board that cannot speak in “spots.” If they insist, treat a paired stall as its own type, DOUBLE, created by ops — not by park() gluing C-12 and C-13 at runtime.

candidates = free[type]                 // exact
          or free[type] + free[larger]  // fallback

prefer: same floor as the gate, then lowest spot number

Nearest-spot is a sort on the candidate list. It is not a second source of truth. Do not walk every stall on a 10,000-spot garage if you can pop from free[COMPACT].

OUT_OF_SERVICE is not in any free list. A cone on C-12 is a status change, not a missing row.

9. Atomic assign

The claim must be one operation: this thread now owns C-12, or it does not.

Same pattern as Uber driver reservation and booking inventory. Application if status == FREE without a WHERE status = FREE is not a proof.

In memory: mutex or free-list pop

synchronized (lotLock):
  spot = free[vehicle.type].pollFirst()
  if spot is null: throw LOT_FULL
  spot.status = OCCUPIED
  ticket = tickets.open(spot, vehicle)
  board.decrement(spot.floor, spot.type)
  return ticket

pollFirst() is already an atomic pop. The mutex keeps ticket insert, status write, and board decrement together. Pop and open in one critical section or a crash leaks a stall.

In SQL: compare-and-set

When they ask you to persist:

UPDATE spots
SET status = 'OCCUPIED',
    ticket_id = :t
WHERE id = :spot_id
  AND status = 'FREE'

Zero rows: someone else won. Try the next candidate or return LOT_FULL.

Do not:

SELECT id FROM spots WHERE type = 'COMPACT' AND status = 'FREE'
-- gap --
UPDATE spots SET status = 'OCCUPIED' WHERE id = 'C-12'

Alice and Bob both SELECT C-12. Both UPDATE. That is the naive loop with a network in the middle. SELECT … FOR UPDATE is also correct and heavier. Defense in depth:

UNIQUE (ticket_id) WHERE status = 'OCCUPIED'
UNIQUE (plate)     WHERE ticket status = 'OPEN'    -- already-inside

Alice vs Bob on the last compact

        Alice                      Lot                         Bob
          |                         |                           |
          |---- park(COMPACT) ----->|                           |
          |                         |<---- park(COMPACT) -------|
          |                         |                           |
          |              free[COMPACT] = [ C-12 ]               |
          |                         |                           |
          |     CAS C-12 FREE→OCC   |                           |
          |     1 row, T1 opened    |                           |
          |                         |                           |
          |                         |   CAS C-12 FREE→OCC       |
          |                         |   0 rows                  |
          |                         |   free list empty         |
          |                         |                           |
          |<-- 201  T1, C-12 -------|                           |
          |                         |-------- 409 LOT_FULL ---->|

Both calls are in flight. The first CAS writes OCCUPIED plus T1. The second still asks for FREE and gets nothing. If C-14 exists, Bob retries CAS there — the Uber loop, not a second lock.

lot mutex          simple; gates queue on one lock
per-type lock      less contention; two types park in parallel
SQL CAS            works across processes; needs a database
optimistic retry   fine while lists are long; noisy on the last stall

I would start with a per-type lock plus a deque, or one SQL CAS per candidate. I would not open a distributed lock “because concurrency.” One garage is one writer set.

10. Fees and pricing

Fee is a function of server timestamps on the ticket. The phone’s clock is not invited.

duration = exited_at - issued_at
hours    = ceil(duration / 1 hour)
fee      = min(hours * rate[type], daily_max[type])

Sixty-one minutes is two hours. Say that before they ask. A 15-minute grace is a product line: if duration < grace, hours = 0.

Progressive pricing (first hour 40, then 30) is the same function with a table instead of a single rate. Compute only at leave.

quote(COMPACT, 61 minutes)
  hours = 2
  raw   = 2 * 40 = 80
  cap   = 300
  fee   = 80

Store issued_at when you open the ticket. Store exited_at and fee when you close it. Snapshotting the rate card onto the ticket is the Senior habit; a mall interview will accept “use the table at exit.”

Lost ticket: charge daily max after you identify the visit, or after you give up. Do not invent a third pricing system.

Payment is mocked. If they want “pay then raise the arm,” that is quote then leave. Do not hold the spot lock while a card network thinks.

11. State machine for Spot and Ticket

Two machines. Do not squash them into spot.status = "alice_is_leaving".

Spot

  FREE ──── park / CAS ────► OCCUPIED
    ▲                         │
    └──── leave (first time) ─┘

  FREE ──── markOutOfService ────► OUT_OF_SERVICE
  OUT_OF_SERVICE ── restore ─────► FREE

OUT_OF_SERVICE is not assignable. Ops restores it. You cannot leave a spot that has no OPEN ticket.

Ticket

  OPEN ──── leave + fee ────► PAID
    │
    │  (admin void, rare)
    ▼
  VOID

The pair that must stay together:

BEGIN / synchronized
  spot  FREE      → OCCUPIED
  ticket          → OPEN
END

BEGIN / synchronized
  ticket OPEN     → PAID  (fee, exited_at)
  spot   OCCUPIED → FREE
END

If you persist the ticket and forget the spot, the next park() hands C-12 to Bob while Alice’s OPEN ticket still says she owns it. If you free the spot and forget to close the ticket, a lost-ticket lookup charges her forever. Illegal: PAID → OPEN, occupying a spot without a ticket.

12. Class sketch

Ideas, not a framework dump. Gates share one ParkingLot.

Vehicle     plate, type
Spot        id, floor, type, status, ticketId?
Ticket      id, spotId, plate, vehicleType, issuedAt, exitedAt?, fee?, status
Receipt     ticketId, spotId, hours, fee, exitedAt
Pricing     quote(type, duration) -> Money
            dailyMax(type) -> Money

SpotRepository
  tryOccupy(allowedTypes) -> Spot | empty     // atomic pop / CAS
  release(spotId)                             // only from leave, once
  markOutOfService(spotId)

TicketRepository
  findOpenByPlate(plate) -> Ticket?
  open(spot, vehicle) -> Ticket
  get(ticketId) -> Ticket
  close(ticket, fee, exitedAt) -> Ticket

DisplayBoard
  decrement / increment / snapshot(floor?)

ParkingLot
  park(vehicle) -> Ticket
  leave(ticketId) -> Receipt
  availability(floor?, type?) -> counts

ParkingLot.park in one breath:

park(vehicle):
  existing = tickets.findOpenByPlate(vehicle.plate)
  if existing: throw ALREADY_PARKED(existing)

  spot = spots.tryOccupy(allowedTypes(vehicle.type))
  if spot is empty: throw LOT_FULL

  ticket = tickets.open(spot, vehicle)
  board.decrement(spot.floor, spot.type)
  return ticket

tryOccupy is the only method allowed to flip FREE → OCCUPIED. Handlers do not touch Spot.status. Tests fake the repository for pricing; they use two threads against a real tryOccupy for the last stall.

13. Display board / free counts

The board over the ramp is a cache of list lengths.

        ┌─────────────────────────┐
        │  Floor B                │
        │  Motorcycle   4         │
        │  Compact      1         │
        │  Large        2         │
        │  EV           1         │
        └─────────────────────────┘
                 ▲
                 │  +1 / -1 in the same
                 │  critical section as CAS
         free[COMPACT].size()

Two implementations, same rule:

1. Derived: board[type] = free[type].size(). Always true if you never bypass the list.
2. Counter: integer per (floor, type), updated next to occupy and release.

I prefer (1) until they want per-floor numbers without floor-sharded lists. Then (2), in the same lock as the spot. A sign may lag by a second. park() must not read the board: Alice and Bob both see 1, and you are back in section 7.

14. Lost ticket, already-inside plate, idempotent leave

These three are where a clean state machine earns its keep.

Already inside

Alice’s compact is in C-12. She drives to another ramp and park()s again — retry, or a second car with the same plate.

findOpenByPlate("KA01AB1234") → T1, C-12
return 409 ALREADY_PARKED

Do not hand her C-14. Two stalls, one plate, and leave no longer knows which visit ended. If they truly want two cars, one household, they need two plates. Default: one OPEN ticket per plate.

Lost ticket

The paper is gone. The car is still in C-12.

attendant: plate?
  OPEN ticket for that plate → leave(that id)   // normal fee
  no OPEN ticket             → charge daily max

You did not create a new assign path. You found the existing OPEN ticket or you billed the cap. The spot still returns to FREE through leave.

Idempotent leave

Alice taps the ticket twice. Or the gate times out after a successful close and retries.

leave(T1) first time
  T1 OPEN → PAID, fee 80
  C-12 OCCUPIED → FREE
  board compact +1

leave(T1) second time
  T1 already PAID
  return the same receipt
  do not release C-12

That last line is the Senior trap. Between the two calls, Bob may have parked in C-12. A naive leave that always sets the spot FREE evicts Bob.

if ticket.status == PAID:
  return receiptFrom(ticket)    // no spot write

leave is idempotent. park is not retried into a second stall; it is ALREADY_PARKED or a new plate.

15. Tests that matter

Skip getters. Test the invariant.

1. Last compact race. One free compact. Two threads park(COMPACT). One 201, one LOT_FULL. Exactly one OPEN ticket.
2. Type refusal. Only compact free. park(LARGE) → LOT_FULL. Compact count unchanged.
3. Exact vs fallback. Bike row empty, fallback off → motorcycle LOT_FULL. Fallback on → motorcycle takes compact.
4. Sixty-one minutes. issued_at + 61 min → 2 hours × compact rate. A 20-hour stay → daily_max.
5. Leave twice. Same fee. After Bob parks in that spot, second leave does not free it.
6. Already inside. Second park same plate → ALREADY_PARKED with the first ticket id.
7. Lost ticket. Open ticket by plate, then leave — fee from timestamps, spot free.
8. Board and cones. Successful park moves the count; LOT_FULL does not. OUT_OF_SERVICE is never assigned.

Test (1) is the offer. If they only have time for one, run two threads on one stall.

16. Extensions

Stay on objects. Do not add a message bus.

EV. type = EV or has_charger. Ice-compact cars do not take chargers under exact-type. “EV may also take compact” is fallback — say it.

Handicap / permit. Another type or a flag. Same CAS. Nearest stall is a sort on the deque. Multi-entry is many gate threads, one ParkingLot.

Reservation. A phone hold is HELD until expiry, then FREE. That is the booking hold. See Design a Booking System.

Airport. garage_id on every call. Cameras may pre-fill the plate; the ticket is still the lock. Monthly pass zeroes quote(); the assign does not change.

17. Final architecture / object diagram

One garage. Many gates. One assign.

          North gate                         South gate
              |                                   |
              |  park(vehicle) / leave(ticket)    |
              v                                   v
        +---------------------------------------------+
        |                 ParkingLot                  |
        |  park / leave / availability                |
        +---------------+-------------+---------------+
                        |             |
            +-----------v--+     +----v------------+
            | SpotRepository|     | TicketRepository|
            | free[TYPE]    |     | OPEN by id      |
            | tryOccupy CAS |     | OPEN by plate   |
            | release       |     | close -> PAID   |
            +-------+-------+     +--------+--------+
                    |                      |
                    v                      v
              Spot rows               Ticket rows
              B-C-12 FREE|OCC         t_9f3a OPEN|PAID
                    |
                    v
              DisplayBoard  -->  LED / GET availability

park  already-inside? -> tryOccupy -> open ticket -> board -1 -> raise arm
leave if PAID return receipt; else quote, PAID, FREE, board +1

Kafka, Redis, and a region pair are not in this picture. If those words appear, you left LLD.

Source of truth    OPEN ticket + spot status, one critical section
Derived            display counts, LED panel, "1 compact left"
Ephemeral          gate UI, mocked payment
Audit              PAID tickets after the car is gone

18. Interview-ready summary

How to walk through in 10–15 minutes

0–2 min. Alice and Bob, last compact. LLD, not a city.
2–4 min. Types, floors, drive-up, hourly fees. Exact-type default.
4–6 min. Entities: Vehicle, Spot, Ticket. Ticket is the lock.
6–9 min. Naive scan, the race, mutex / free-list pop / SQL CAS.
9–12 min. Fees, both state machines, idempotent leave.
12–15 min. Board is derived, lost ticket, already-inside, one race test. Airport = many garages.

Key decisions to remember

1. This is objects and one atomic assign, not a distributed product.
2. Ticket + spot status change in one critical section or transaction.
3. Exact-fit spots unless you state a fallback rule out loud.
4. A large car does not consume two compact stalls.
5. Fee from issued_at at exit; ceil to the hour; daily cap.
6. Free lists beat a full scan; the board is not the allocator.
7. SQL CAS is UPDATE … WHERE status = 'FREE'. Zero rows means you lost.
8. Idempotent leave must not release a stall someone else now holds.
9. One OPEN ticket per plate; lost ticket is a lookup, then normal leave or daily max.
10. An airport is garage_id sharding, not Kafka.

Likely interviewer follow-up questions

• Can a bike take a compact stall?
• Two gates, one spot — prove only one ticket.
• How do you price 61 minutes? A 20-hour stay?
• Where is the source of truth — camera plate or ticket?
• How would you add reservations?
• How does the LED board stay honest?
• What if leave retries after success and Bob already parked?
• Can a large vehicle take two compact spots?
• What if they ask for an airport?

Senior-level points that differentiate the answer

• Name the race before drawing classes. Classes without CAS are a vocabulary list.
• Tie this CAS to booking inventory and Uber’s driver reservation — same WHERE trick.
• Separate Spot and Ticket machines; do not hide occupancy only on the car.
• Call out the “second leave evicts Bob” bug without being prompted.
• Treat the display board as derived, and refuse to allocate from it.
• Snapshot or cap fees; never trust the client clock. Scale is garage_id, not a log.

A 1–2 minute verbal answer

A parking lot is spots, vehicles, and tickets. I assign the smallest exact-type free spot with an atomic occupy — a free-list pop under a lock, or UPDATE spots SET occupied WHERE id = C-12 AND status = FREE — so two gates cannot share the last compact. The ticket stores entry time and the stall; it is the source of truth for the visit. Exit computes an hourly fee with a daily cap, marks the ticket PAID, and frees the spot in the same step. Leave is idempotent and must not release a stall that has already been given to someone else. A second park with the same plate returns already-parked. The LED board is a count of the free lists, not the allocator. I would test two threads on one remaining compact stall. This stays in one process or one database. An airport is many garages with the same design, routed by garage id.

For HLD framing around this, see the System Design Interview Complete Guide and the questions hub.