Parking Lot

The parking lot is the most common LLD interview problem. A car arrives, gets a slot and a ticket, and later pays and leaves. The design questions are how you match vehicles to slots quickly, where pricing lives, and how you keep slot state consistent on exit.

Requirements#

Keep it to one level and a simple size rule:

1. The lot has many slots of different sizes.
2. A vehicle arriving asks for a slot; if one is available it is assigned and a ticket is issued.
3. On checkout the fee is charged and the slot is freed.
4. Vehicles come in different sizes, and so do slots.
5. If no suitable slot exists, the vehicle is rejected.

Actor: the driver.

Clarifications

• Single level, one entry, one exit.
• Exact size match: a small vehicle needs a small slot (relaxing this is an extension).

Out of scope: UI, concurrency, real payment (pricing sits behind an interface).

Core entities#

Six types cover the design:

Relationships#

The lot owns its slots and delegates pricing to a strategy.

Key flows#

Parking and exiting are the two flows that change state.

Park:

1. Look up the free-slot bucket for the vehicle's size.
2. If it's empty, reject the vehicle.
3. Otherwise, pop a slot, set its vehicle, create a ticket and record it as active.

Exit:

1. Validate that the ticket is active.
2. Stamp the exit time.
3. Ask the pricing strategy for the fee.
4. If payment fails, keep the slot occupied.
5. Otherwise, clear the slot, return it to its bucket and close the ticket.

Bucketing free slots as Dict[Size, List[Slot]] makes assignment an $O(1)$ pop instead of scanning every slot.

Code#

A single-level lot with flat-rate pricing:

import uuid
from abc import ABC, abstractmethod
from datetime import datetime
from enum import Enum
from typing import Dict, List, Optional, Tuple


class Size(Enum):
    SMALL = 1
    MEDIUM = 2
    LARGE = 3


class Vehicle:
    def __init__(self, plate: str, size: Size):
        self.plate = plate
        self.size = size


class Slot:
    def __init__(self, slot_id: int, size: Size):
        self.id = slot_id
        self.size = size
        self.vehicle: Optional[Vehicle] = None


class ParkingTicket:
    def __init__(self, slot: Slot, vehicle: Vehicle):
        self.id = uuid.uuid4().hex[:8]
        self.slot = slot
        self.vehicle = vehicle
        self.entry_time = datetime.now()
        self.exit_time: Optional[datetime] = None


class PricingStrategy(ABC):
    @abstractmethod
    def calculate(self, ticket: ParkingTicket) -> Tuple[float, bool]:
        """Return (fee, payment_succeeded)."""


class FlatRatePricing(PricingStrategy):
    def calculate(self, ticket: ParkingTicket) -> Tuple[float, bool]:
        return 10.0, True


class ParkingLot:
    def __init__(self, pricing: PricingStrategy):
        self.free_slots: Dict[Size, List[Slot]] = {}
        self.active_tickets: Dict[str, ParkingTicket] = {}
        self.pricing = pricing

    def add_slot(self, slot: Slot) -> None:
        self.free_slots.setdefault(slot.size, []).append(slot)

    def park(self, vehicle: Vehicle) -> Optional[ParkingTicket]:
        bucket = self.free_slots.get(vehicle.size, [])
        if not bucket:
            return None  # lot full for this size

        slot = bucket.pop()
        slot.vehicle = vehicle
        ticket = ParkingTicket(slot, vehicle)
        self.active_tickets[ticket.id] = ticket
        return ticket

    def exit(self, ticket: ParkingTicket) -> Optional[float]:
        if ticket.id not in self.active_tickets:
            # Unknown or already-used ticket: prevents freeing a slot twice
            return None

        ticket.exit_time = datetime.now()
        fee, ok = self.pricing.calculate(ticket)
        if not ok:
            # Payment failed: vehicle and slot stay as they are
            return None

        slot = ticket.slot
        slot.vehicle = None
        self.free_slots.setdefault(slot.size, []).append(slot)
        del self.active_tickets[ticket.id]
        return fee


if __name__ == "__main__":
    lot = ParkingLot(FlatRatePricing())
    lot.add_slot(Slot(1, Size.SMALL))

    t = lot.park(Vehicle("KA-01", Size.SMALL))
    print("parked in slot:", t.slot.id)                         # 1
    print("full now:", lot.park(Vehicle("KA-02", Size.SMALL)))  # None
    print("fee:", lot.exit(t))                                  # 10.0
    print("double exit:", lot.exit(t))                          # None
    t3 = lot.park(Vehicle("KA-03", Size.SMALL))
    print("reopened:", t3.slot.id)                              # 1

Extensions and trade-offs#

Each common follow-up maps to one extension point:

• Fit into larger slots: iterate sizes from the vehicle's size upward and take the first non-empty bucket. Put the policy behind a SlotAssignmentStrategy (exact fit, best fit, nearest to entrance).
• Hourly pricing: a new HourlyPricing strategy computes from exit_time - entry_time; nothing else changes.
• Multiple levels: add a Level that owns slots; the lot asks levels in order. The bucket structure moves into each level.
• Multiple entry/exit gates: gates become thin objects that call the lot; the lot stays the single source of truth.
• Concurrency: bucket.pop() followed by assignment is a check-then-act. Two gates could race for one slot, so guard park/exit with a lock (or one lock per size bucket).
• Bucket vs flag trade-off: buckets make "any free slot of size X" $O(1)$, but you can't cheaply answer "is slot 42 free?" without also keeping a slot_id → Slot map.

Key takeaways#

• Bucket free slots by size for $O(1)$ assignment.
• Track active tickets so a ticket can't be used twice.
• Keep pricing behind a strategy interface so new pricing rules are new classes.
• On exit, update every related piece of state together: slot, bucket, ticket.
• The usual follow-ups are slot-fit policy, multi-level, and concurrency.