Parking lot

Design a parking lot with several floors. Vehicles of different sizes arrive at entry gates, are given a slot and a ticket, and pay at an exit gate based on how long they stayed. This is the most common low-level design question because it exercises every habit from the course: modeling, strategy, state, concurrency and extension.

• Several floors, each with slots of three sizes: small (bikes), medium (cars), large (trucks).
• A vehicle may use a slot of its own size or a larger one, never a smaller one.
• Entry issues a ticket that records the vehicle, slot and time. If the lot is full, entry is refused.
• Exit computes the fee from the time parked and the vehicle type, takes payment, and frees the slot.
• Fees differ by vehicle type and are likely to change, so pricing must be replaceable.
• A display shows free slots per size. Lost tickets need a fixed fee.
• Out of scope: the physical gates, number plate recognition, a real payment network.
• Non-functional: many gates working at once, so two cars must never get the same slot.

From the nouns: ParkingLot, Floor, Slot, Vehicle, Ticket, Gate, Payment. From the verbs: enter, allocate, leave, pay. Decide what is a class and what is a value.

• Slot: an id, a size, a floor and a distance from the entrance. It is either free or taken.
• Vehicle needs only a plate and a size, so a value type is enough. A subclass per vehicle would be the procedural switch in disguise.
• Ticket: id, plate, slot and entry time. It is data plus one derived question, how long has it been.
• PricingRule: a strategy, since fees change and differ by type.
• SlotAllocator: a strategy for choosing a slot, such as nearest to the entrance.
• ParkingLot: the coordinator that holds active tickets.

By Information Expert the allocator, which knows what is free, picks the slot, and the pricing rule, which knows rates, computes the fee. The lot coordinates and owns the tickets, so by Creator it makes them. Gates are controllers that pass requests in. No class here does two jobs, which is what makes each easy to change.

Finding a free slot by scanning every slot costs O(n), which is slow at a large lot with many gates. Better: keep, for each size, a min-heap of free slots ordered by distance to the entrance. Taking the nearest free slot is a pop, which is O(log n). Releasing a slot is a push, also O(log n). Memory is O(n).

For a medium vehicle, try the medium heap first. If it is empty, try the large heap. This implements "own size or larger" and is easy to reason about. A different goal, such as spreading cars across floors, is a different comparator, or a different allocator, with no change to the lot.

enum Size { Small, Medium, Large }
interface PricingRule { fee(minutes: number): number }
interface Clock { now(): number }

class Slot {
  constructor(readonly id: string, readonly size: Size, readonly distance: number) {}
}
type Ticket = { id: string; plate: string; slot: Slot; enteredAt: number };

class SlotAllocator {
  private free = new Map<Size, MinHeap<Slot>>();   // any priority queue
  constructor(slots: Slot[]) { for (const s of slots) this.heap(s.size).push(s); }
  private heap(size: Size) {
    if (!this.free.has(size)) this.free.set(size, new MinHeap<Slot>((a, b) => a.distance - b.distance));
    return this.free.get(size)!;
  }
  take(need: Size): Slot | null {
    for (let s = need; s <= Size.Large; s++) {
      const slot = this.free.get(s)?.pop();
      if (slot) return slot;
    }
    return null;
  }
  release(slot: Slot) { this.heap(slot.size).push(slot); }
}

class ParkingLot {
  private active = new Map<string, Ticket>();
  constructor(private alloc: SlotAllocator, private rule: PricingRule, private clock: Clock) {}

  enter(plate: string, size: Size): Ticket {
    const slot = this.alloc.take(size);
    if (!slot) throw new Error("lot full");
    const t = { id: crypto.randomUUID(), plate, slot, enteredAt: this.clock.now() };
    this.active.set(t.id, t);
    return t;
  }
  leave(id: string): number {
    const t = this.active.get(id);
    if (!t) throw new Error("unknown ticket");
    const amount = this.rule.fee((this.clock.now() - t.enteredAt) / 60000);
    this.active.delete(id);
    this.alloc.release(t.slot);
    return amount;
  }
}

The clock is injected, so tests control time. Pricing is injected, so the holiday rule is a new class. Slots are claimed by removing them from the heap, so one slot can never go to two cars, as long as that removal is atomic.

Many gates call enter at once. The danger is check then act: two gates both see the same nearest slot. Because take removes the slot in one step, you only need that step to be protected. Options, from simple to scalable: one lock around take and release, a lock per size heap, or a database with a conditional update such as "set taken where free". Keep the critical section tiny, since every gate waits on it. If the lot spans servers, the claim must go through shared storage, because an in-memory lock only protects one process.

class HourlyRule implements PricingRule {
  constructor(private perHour: number) {}
  fee(m: number) { return Math.ceil(m / 60) * this.perHour; }
}

Different vehicles get different rules, chosen by a small factory. A free first 15 minutes, a daily cap or a weekend discount are decorators wrapped around an existing rule. Store money as integers in the smallest unit, never as floating point, so rounding never leaks.

• A car gets the nearest medium slot, and the next car gets the next nearest.
• A car takes a large slot when medium ones are gone, and a bike never gets a car slot.
• A full lot refuses entry and changes nothing.
• Leaving frees the slot, and the next car receives it.
• 61 minutes costs two hours, and a fake clock makes this exact.
• An unknown or already used ticket is rejected.
• Many simultaneous entries never assign one slot twice.

• Payment before exit: make a ticket a state machine, issued, paid, exited, so the gate refuses an unpaid ticket. The state pattern fits exactly.
• Display board: an observer that listens to SlotTaken and SlotFreed events.
• Electric vehicle charging: a new slot type and an extra requirement, handled by a richer allocator.
• Reservations: a reserved status with an expiry, which adds a timeout and a cleanup job.
• Several lots: a repository per lot behind one interface, so persistence can be swapped.

• A subclass per vehicle type with its own fee, which brings back the if chain in a new shape.
• Scanning all slots for each arrival.
• Computing fees from the current time inside the logic, which makes tests flaky.
• Releasing the slot before payment is confirmed.
• Letting the display or the gate know pricing details.