Design a Parking Lot: The Canonical LLD Problem

Why “Parking Lot” Is Still the Interview You Will Fail

The parking lot is the most over-prepared and most under-thought LLD problem in existence. Everyone has “seen it.” Almost nobody designs it well under pressure, because the difficulty was never the parking — it’s whether you can carve a fuzzy real-world system into responsibilities that each have exactly one reason to change, while keeping allocation and pricing pluggable without over-engineering, and whether you can tell an honest concurrency story instead of a hand-wavy one.

This lesson treats the parking lot the way an interviewer treats it: as a probe for taxonomy, encapsulation, the two or three places where a pattern genuinely earns its keep, and your ability to say precisely which of your guarantees actually hold. We go in the order you should actually work in an interview — clarify, model, diagram, sign the methods, hunt edge cases, justify patterns, then extend.

The meta-skill being tested: Can you take an open-ended prompt, bound it with smart questions, and produce a design that is correct for today but cheap to change tomorrow — and not overstate what your code guarantees? The parking is incidental. The judgment is the point.

Step 1 — Clarify the Requirements (Do Not Skip This)

The single biggest mistake at SDE-1 is diving into classes before scoping. Spend the first 3-4 minutes asking questions. But ask the load-bearing ones — the ones whose answers change your class graph — not trivia.

The questions that actually change the design

The scope I’ll commit to (state yours out loud)

“I’ll design a multi-level lot. Vehicle types: Motorcycle, Car, Truck. Spot types: Compact, Large, Motorcycle with simple fit rules. A vehicle gets a Ticket on entry, allocation is pluggable (default: nearest-to-entrance). Pricing is pluggable (default: per-hour by vehicle type). Payment happens on exit, and the closed Ticket plus its Payment are retained for audit and idempotent re-settlement. Out of scope: reservations, monthly passes, and license-plate OCR — but I’ll design so they slot in.”

That last sentence is gold in an interview. You are signaling that you know what you’re not building and why.

Be precise about concurrency — it’s a trap question

Most candidates say “I’ll make it thread-safe” and then write code that isn’t. Be specific:

“The only true race is two threads claiming the same spot at the same time, so I’ll make the claim-the-spot step atomic with a per-spot lock and a check-then-set under that lock. In my C++ implementation that’s a real std::mutex. My TypeScript and Python samples I’ll keep single-threaded (Node’s event loop / CPython under the GIL still doesn’t make a check then set across an await/yield atomic, but my code has no such suspension point), and I’ll say so rather than pretend a lock exists. If we needed real Python concurrency I’d add a threading.Lock per spot.”

Step 2 — Core Entities and Their Responsibilities

Before any code, list the nouns and give each one job. If you can’t state a class’s single responsibility in one sentence, it’s the wrong class.

• Vehicle (abstract) — knows its licensePlate and VehicleType. Knows what size spot it can fit in. Subtypes: Motorcycle, Car, Truck. The base is genuinely non-instantiable.
• ParkingSpot — a single physical spot. Knows its SpotType, whether it’s free, and which vehicle (if any) occupies it. Provides an atomic assign (the only authoritative race guard) and release.
• Level — a floor. Owns its spots and the availability counts per spot type. Exposes freeSpotsFor(v) (a fresh snapshot of candidate spots) and freeCount(type), and keeps its per-type counters consistent on assign/release.
• ParkingLot — the façade/aggregate root. Owns levels and the configured strategies. Exposes parkVehicle / unparkVehicle. Retains closed tickets and payments.
• Ticket — issued on entry. Identity (ticketId, entryTime, spot, vehicle) plus a closed/exitTime state. The contract between entry and exit.
• PricingStrategy (interface) — computes a fee (in cents) given a ticket and exit time.
• AllocationStrategy (interface) — picks a spot from a freshly-snapshotted candidate set.
• Payment — captures amount, method, status. Records the settlement of a ticket.
• VehicleFactory — turns (VehicleType, plate) into the right concrete Vehicle.

Enums and value objects

Model VehicleType and SpotType as enums, and put the fit policy in one place so it isn’t scattered across if statements. The base Vehicle must be impossible to instantiate directly — that’s a real guarantee, not a comment.

enum VehicleType { MOTORCYCLE, CAR, TRUCK }
enum SpotType { MOTORCYCLE, COMPACT, LARGE }

// Single source of truth for the fit rule.
const FITS: Record<VehicleType, SpotType[]> = {
[VehicleType.MOTORCYCLE]: [SpotType.MOTORCYCLE, SpotType.COMPACT, SpotType.LARGE],
[VehicleType.CAR]:        [SpotType.COMPACT, SpotType.LARGE],
[VehicleType.TRUCK]:      [SpotType.LARGE],
};

// protected constructor => 'new Vehicle()' is a compile error; only subtypes construct.
abstract class Vehicle {
protected constructor(
  public readonly licensePlate: string,
  public readonly type: VehicleType,
) {}
canFitIn(spotType: SpotType): boolean {
  return FITS[this.type].includes(spotType);
}
}
class Car extends Vehicle { constructor(p: string) { super(p, VehicleType.CAR); } }
class Motorcycle extends Vehicle { constructor(p: string) { super(p, VehicleType.MOTORCYCLE); } }
class Truck extends Vehicle { constructor(p: string) { super(p, VehicleType.TRUCK); } }

Step 3 — The Class Diagram

Draw this. Interviewers weight a clear diagram heavily because it proves you can hold the whole system in your head. Note the C++ ownership caveat called out below the diagram.

\`\`\`
                          +--------------------+
                          |     ParkingLot     |  (aggregate root / facade)
                          +--------------------+
                          | - levels: Level[]  |
                          | - alloc: Allocation|
                          | - pricing: Pricing |
                          | - open: Map<id,Tkt>|
                          | - closed: Map<id,..|  (Ticket+Payment, retained)
                          | - levelOf: Map<sid,|  (spot id -> owning Level)
                          +--------------------+
                          | + parkVehicle(v)   |---> Ticket
                          | + unparkVehicle(id)|---> Payment
                          +---------+----------+
                                    | 1..*
                                    v
                          +--------------------+
                          |       Level        |
                          +--------------------+
                          | - floor: int       |
                          | - spots: Spot*[]   |  (held by pointer in C++)
                          | - counts: Map      |
                          +--------------------+
                          | + freeSpotsFor(v)  |  -> ParkingSpot[]  (snapshot)
                          | + freeCount(type)  |
                          | + onAssigned(spot) |  (decrement counter)
                          | + onReleased(spot) |  (increment counter)
                          +---------+----------+
                                    | 1..*
                                    v
                          +--------------------+        +-------------+
                          |    ParkingSpot     |<>------|  Vehicle    | (abstract)
                          +--------------------+ 0..1   +-------------+
                          | - id: string       |        | plate,type  |
                          | - type: SpotType   |        | +canFitIn() |
                          | - vehicle?: V       |       | +label()*   |
                          | - mutex (C++ only) |        +------^------+
                          +--------------------+               |
                          | + canFit(v) (hint) |        +------+------+------+
                          | + assign(v) atomic |       Car   Motorcycle  Truck
                          | + release()        |
                          +--------------------+

   <<interface>>                 <<interface>>
 AllocationStrategy            PricingStrategy           +-----------+
 +selectSpot(spots,v)          +price(ticket, exitTime)  |  Ticket   |
       ^                              ^                  +-----------+
   +---+-----+                  +-----+-------+          | id        |
 Nearest   FirstFit          FlatRate  HourlyByType      | entryTs   |
                                                         | spot      |
   <<factory>>                                           | vehicle   |
 VehicleFactory.create(type, plate)                      | exitTs?   |
                                                         | +close()  |
   +-----------+                                         +-----------+
   |  Payment  |  amount(cents), method, status, paidAt
   +-----------+
\`\`\`

Key relationship notes to say aloud:

• ParkingLot owns Levels (composition); Level owns ParkingSpots.
• ParkingSpot references a Vehicle (association, 0..1) — it does not own the vehicle’s lifecycle.
• The two <<interface>> strategies are held by ParkingLot, giving you a clean seam for the Strategy pattern.
• ParkingLot keeps two maps: open tickets and closed (ticket + payment) for audit and idempotent re-settlement — plus a levelOf index from spot id to owning Level, so exit can update the right level’s counters in O(1).

Step 4 — Key Method Signatures

Signatures are where interviewers catch hand-waving. Commit to types, return values, and what happens on failure — and make the concurrency guarantee in each language match what the code actually does.

The spot — assign is the only authoritative race guard

canFit is an advisory hint used to build candidate snapshots. The authoritative guard is assign, which re-checks free-and-fits and sets the vehicle as one atomic step. In C++ that whole step is under the spot’s mutex (including the read), so there is no TOCTOU. In TS/Python the code is single-threaded by stated scope.

// Single-threaded scope (Node event loop): there is no suspension point
// between the check and the set inside assign(), so no lock is needed.
// If this ran on real threads we'd add a per-spot lock here.
class ParkingSpot {
private vehicle: Vehicle | null = null;
constructor(public readonly id: string, public readonly type: SpotType) {}

isFree(): boolean { return this.vehicle === null; }

// Advisory hint for building candidate snapshots. NOT the race guard.
canFit(v: Vehicle): boolean { return this.isFree() && v.canFitIn(this.type); }

// Authoritative: re-checks then sets in one synchronous step.
// Returns false if it lost a race (already taken) or doesn't fit.
assign(v: Vehicle): boolean {
  if (this.vehicle !== null || !v.canFitIn(this.type)) return false;
  this.vehicle = v;
  return true;
}
release(): Vehicle {
  if (!this.vehicle) throw new Error("Releasing an empty spot");
  const v = this.vehicle;
  this.vehicle = null;
  return v;
}
}

The Level — defines freeSpotsFor and keeps counters honest

This is the class the diagram names and parkVehicle calls. The counters the requirements committed to (real-time availability) are updated here, on every assign/release, so they never drift.

class Level {
// Per-type free counters: the authoritative 'real-time availability'.
private counts = new Map<SpotType, number>();
constructor(public readonly floor: number, private spots: ParkingSpot[]) {
  for (const s of spots) {
    if (s.isFree()) this.counts.set(s.type, (this.counts.get(s.type) ?? 0) + 1);
  }
}

// Fresh snapshot of fitting, free spots for v. Strategy operates on THIS array.
freeSpotsFor(v: Vehicle): ParkingSpot[] {
  return this.spots.filter(s => s.canFit(v));
}

// Does this spot belong to this level? Used by ParkingLot to index spot->level.
owns(s: ParkingSpot): boolean { return this.spots.includes(s); }

freeCount(type: SpotType): number { return this.counts.get(type) ?? 0; }

// Called by ParkingLot after a successful assign / release to keep counts in sync.
onAssigned(s: ParkingSpot): void {
  this.counts.set(s.type, (this.counts.get(s.type) ?? 0) - 1);
}
onReleased(s: ParkingSpot): void {
  this.counts.set(s.type, (this.counts.get(s.type) ?? 0) + 1);
}
}

The strategies, the factory, and the lot

The parkVehicle flow ties it together: for each level, take a fresh snapshot of candidates, let the allocation strategy choose, then attempt to claim it atomically. If a claim fails (lost race or spot just taken), re-snapshot and retry the same level until either we claim a spot or the level genuinely has no candidates — only then advance to the next level. That is what makes the “retry” comment honest.

When a spot is claimed, the lot records it in a levelOf index (spot id → owning Level). On exit, that index lets unparkVehicle call onReleased on the correct level so the per-type availability counters stay accurate — exactly the discipline the Python/C++ variants follow.

import { randomUUID } from "node:crypto"; // Node 19+ also exposes global crypto.randomUUID

interface AllocationStrategy {
selectSpot(candidates: ParkingSpot[], v: Vehicle): ParkingSpot | null;
}
interface PricingStrategy {
price(ticket: Ticket, exitTime: number): number; // cents
}

class Ticket {
exitTime: number | null = null;
constructor(
  public readonly id: string,
  public readonly vehicle: Vehicle,
  public readonly spot: ParkingSpot,
  public readonly entryTime: number,
) {}
isClosed(): boolean { return this.exitTime !== null; }
close(at: number): void { this.exitTime = at; }
}

class Payment {
readonly paidAt = Date.now();
constructor(public readonly amountCents: number,
            public readonly method = "card",
            public readonly status = "SETTLED") {}
}

// --- Allocation strategies ---
class FirstFit implements AllocationStrategy {
selectSpot(c: ParkingSpot[]): ParkingSpot | null { return c[0] ?? null; }
}
// 'Nearest' assumes candidate ordering encodes distance, or sorts by an id/row key.
class NearestToEntrance implements AllocationStrategy {
selectSpot(c: ParkingSpot[]): ParkingSpot | null {
  return c.length ? c.reduce((a, b) => (a.id <= b.id ? a : b)) : null;
}
}

// --- Pricing strategies ---
class FlatRate implements PricingStrategy {
constructor(private cents: number) {}
price(): number { return this.cents; }
}
// Charges per started hour, rate depends on vehicle type. Times are epoch ms.
class HourlyByType implements PricingStrategy {
constructor(private centsPerHour: Record<VehicleType, number>) {}
price(t: Ticket, exitTime: number): number {
  const ms = Math.max(0, exitTime - t.entryTime);
  const hours = Math.ceil(ms / 3_600_000) || 1; // min 1 hour
  return hours * this.centsPerHour[t.vehicle.type];
}
}

// --- Factory ---
class VehicleFactory {
static create(type: VehicleType, plate: string): Vehicle {
  switch (type) {
    case VehicleType.CAR: return new Car(plate);
    case VehicleType.MOTORCYCLE: return new Motorcycle(plate);
    case VehicleType.TRUCK: return new Truck(plate);
  }
}
}

class ParkingLot {
private open = new Map<string, Ticket>();
private closed = new Map<string, { ticket: Ticket; payment: Payment }>();
// spot.id -> owning Level, populated on assign so exit updates the right counters.
private levelOf = new Map<string, Level>();
constructor(
  private levels: Level[],
  private alloc: AllocationStrategy,
  private pricing: PricingStrategy,
) {}

parkVehicle(v: Vehicle): Ticket | null {
  for (const level of this.levels) {
    // Retry within the level: re-snapshot after each lost claim.
    while (true) {
      const candidates = level.freeSpotsFor(v);     // fresh snapshot
      const spot = this.alloc.selectSpot(candidates, v);
      if (!spot) break;                              // no candidates here -> next level
      if (spot.assign(v)) {                          // authoritative claim
        level.onAssigned(spot);
        this.levelOf.set(spot.id, level);            // remember the owning level
        const t = new Ticket(randomUUID(), v, spot, Date.now());
        this.open.set(t.id, t);
        return t;
      }
      // lost the race for 'spot' -> loop, re-snapshot, re-select
    }
  }
  return null; // genuinely full for this vehicle type
}

unparkVehicle(ticketId: string, exitTime = Date.now()): Payment {
  // Idempotent re-settlement: already-closed tickets return the stored payment.
  const done = this.closed.get(ticketId);
  if (done) return done.payment;

  const t = this.open.get(ticketId);
  if (!t) throw new Error("Unknown ticket");

  const amount = this.pricing.price(t, exitTime); // price BEFORE releasing
  t.spot.release();
  t.close(exitTime);
  const payment = new Payment(amount);

  this.open.delete(ticketId);
  this.closed.set(ticketId, { ticket: t, payment }); // retain for audit
  // Update the correct level's per-type counter via the spot->level index.
  this.levelOf.get(t.spot.id)?.onReleased(t.spot);
  this.levelOf.delete(t.spot.id);
  return payment;
}
}

HourlyByType worked example — prove the cents/ms contract

Say the rates are {CAR: 200 cents/hr, MOTORCYCLE: 100, TRUCK: 500}. A car enters at t0 and exits 2h 5m later. In ms that’s 7_500_000 ms.

• ms = 7_500_000
• hours = ceil(7_500_000 / 3_600_000) = ceil(2.083…) = 3 (per started hour)
• fee = 3 × 200 = 600 cents = $6.00

A motorcycle staying exactly 59 minutes: ms = 3_540_000, hours = ceil(0.983) = 1, fee = 1 × 100 = 100 cents. And a zero-duration / clock-skew exit (exit ≤ entry) clamps to ms = 0 → hours = max(1, 0) = 1, so you never charge 0. State this minimum-one-hour rule explicitly; interviewers probe the boundary.

Step 5 — Edge Cases (Where SSEs Separate from Juniors)

• Lost-spot race / contention. Two threads target the same free spot. Only the C++ assign is truly atomic; the loser gets false and parkVehicle re-snapshots and retries the same level before giving up — so a viable-but-different free spot on that level is never skipped.
• “Full” must mean full for this vehicle type. A truck can be rejected while compact spots sit empty. parkVehicle returns null only after every level yields no fitting candidate.
• Unknown / double exit. unparkVehicle on a closed ticket is idempotent: it returns the stored Payment instead of throwing or re-charging. This is only possible because we retain closed tickets + payments rather than deleting them.
• Price before release. Compute the fee while the ticket still references the spot and entry time; releasing first risks losing the data the price depends on.
• Counter drift. Availability counters are updated in exactly two places — onAssigned after a successful claim and onReleased after a release. The levelOf index guarantees onReleased fires on the spot’s actual owning level; never recompute counters by scanning, and never update them anywhere else.
• Clock skew / minimum charge. Negative or zero durations clamp to one started hour (shown above).
• Releasing an empty spot. release throws — it should never happen, and a thrown exception surfaces the bug instead of silently corrupting state.
• Oversized vehicle, no fitting spot type at all. The fit table returns an empty allowed set → no candidate ever appears → clean null, not a crash.

Step 6 — The Patterns That Naturally Appear (and Why)

You do not “apply patterns.” They emerge when a requirement says “this should vary.” Name them only where they earn their keep:

• Strategy — AllocationStrategy and PricingStrategy. The requirement “spot choice and pricing are pluggable” is the open/closed seam. Swapping FirstFit for NearestToEntrance, or FlatRate for HourlyByType, changes behavior with zero edits to ParkingLot. Crucially, a strategy receives a freshly-snapshotted candidate set each call — it must not cache spots across calls, or it will hand back already-claimed ones.
• Factory — VehicleFactory.create(type, plate). Entry gates produce vehicles from external input (a VehicleType off a sensor); the factory localizes the switch so adding a type touches one place.
• Facade / Aggregate Root — ParkingLot. Clients call parkVehicle / unparkVehicle and never see spots, levels, or strategies. This is what keeps the API tiny.
• (Implicit) Template-method-ish flow in parkVehicle: the skeleton (iterate levels → snapshot → select → claim → retry) is fixed; the variable steps (selectSpot, price) are delegated. That’s Strategy doing the varying inside a fixed algorithm.

Step 7 — Extensibility (“What If They Ask For X?”)

• “Add electric vehicles with charging spots.” Add VehicleType.EV and SpotType.CHARGING, one row in FITS, one case in VehicleFactory. The fit table and factory absorb it; nothing else changes. That’s the payoff of the single-source-of-truth table.
• “Surge pricing at peak hours.” New PricingStrategy (TimeOfDaySurge wrapping a base strategy — Decorator). No change to ParkingLot or Ticket.
• “Reservations.” A ReservationStrategy/hold on a spot before entry; the spot grows a RESERVED state distinct from occupied. The atomic-claim seam (assign) is exactly where you enforce “reserved spots aren’t allocatable to walk-ins.”
• “Real distributed lot across many gates.” The per-spot lock generalizes to a per-spot row in a DB with a conditional update (UPDATE spot SET vehicle=? WHERE id=? AND vehicle IS NULL) — the same compare-and-set, just durable. Your assign already models this; you swap the in-memory mutex for an atomic DB write.
• “Show live availability.” Already supported: Level.freeCount(type) is O(1) because counters are maintained on every assign/release. Aggregate across levels for a lot-wide view.