Back to Notes

Design a Parking Lot

1. Problem & Why It's Asked

A classic LLD warm-up because it forces the fundamentals without much domain complexity: multiple entity types (vehicles, spots, tickets), a matching/allocation rule, and an obvious extensibility follow-up (add floors, add EV charging, add pricing tiers). It's a filter for whether you reach for polymorphism or write a wall of if/elif on type strings.

2. Requirements

Functional:

  • Vehicles of different types (motorcycle, car, truck/bus) park in spots sized for their type.
  • Issue a ticket on entry; compute a fee on exit based on duration.
  • Track available spots per type, support multiple floors.

Non-functional:

  • Thread-safe — two vehicles must never be assigned the same spot concurrently.
  • Extensible — new vehicle types, new pricing schemes, new spot types (EV charging) shouldn't require touching existing classes (Open/Closed — see [[SOLID Principles]]).

3. Core Entities & Class Diagram

classDiagram
    class VehicleType {
        <<enumeration>>
        MOTORCYCLE
        CAR
        TRUCK
    }
    class Vehicle {
        +str plate
        +VehicleType type
    }
    class ParkingSpot {
        +str id
        +VehicleType type
        +int floor
        +Vehicle vehicle
        +is_free() bool
        +park(vehicle)
        +vacate()
    }
    class Ticket {
        +str id
        +str spot_id
        +str plate
        +datetime entry_time
        +datetime exit_time
    }
    class PricingStrategy {
        <<interface>>
        +calculate_fee(ticket) float
    }
    class ParkingLot {
        -dict~str,ParkingSpot~ spots
        -dict~str,Ticket~ active_tickets
        -PricingStrategy pricing
        -Lock lock
        +park(vehicle) Ticket
        +unpark(ticket_id) float
    }
    Vehicle "1" --> "1" VehicleType
    ParkingSpot "1" --> "0..1" Vehicle
    ParkingLot "1" --> "*" ParkingSpot
    ParkingLot "1" --> "*" Ticket
    ParkingLot --> PricingStrategy

4. Design Patterns Used

  • Strategy for pricing — different fee schemes (flat rate, per-hour, per-vehicle-type) plug in without changing ParkingLot (see [[OOD Design Patterns]]).
  • Factory (optional, for larger versions) — constructing the right ParkingSpot subtype per floor-plan config.
  • Polymorphic VehicleType matching over spots, rather than branching if vehicle.type == "car": ... scattered through the allocation logic — this is the Open/Closed signal interviewers look for.

5. Implementation

from abc import ABC, abstractmethod
from dataclasses import dataclass, field
from datetime import datetime
from enum import Enum
from threading import Lock
from uuid import uuid4


class VehicleType(Enum):
    MOTORCYCLE = "motorcycle"
    CAR = "car"
    TRUCK = "truck"


@dataclass
class Vehicle:
    plate: str
    type: VehicleType


class ParkingSpot:
    def __init__(self, spot_id: str, spot_type: VehicleType, floor: int):
        self.id = spot_id
        self.type = spot_type
        self.floor = floor
        self.vehicle: Vehicle | None = None

    @property
    def is_free(self) -> bool:
        return self.vehicle is None

    def park(self, vehicle: Vehicle) -> None:
        self.vehicle = vehicle

    def vacate(self) -> None:
        self.vehicle = None


@dataclass
class Ticket:
    id: str
    spot_id: str
    plate: str
    entry_time: datetime
    exit_time: datetime | None = None


class PricingStrategy(ABC):
    @abstractmethod
    def calculate_fee(self, ticket: Ticket) -> float: ...


class HourlyPricing(PricingStrategy):
    def __init__(self, rate_per_hour: float = 2.0):
        self.rate = rate_per_hour

    def calculate_fee(self, ticket: Ticket) -> float:
        duration = (ticket.exit_time - ticket.entry_time).total_seconds() / 3600
        return round(max(duration, 0.25) * self.rate, 2)  # 15-min minimum charge


class ParkingLot:
    def __init__(self, pricing: PricingStrategy):
        self.spots: dict[str, ParkingSpot] = {}
        self.active_tickets: dict[str, Ticket] = {}
        self.pricing = pricing
        self._lock = Lock()

    def add_spot(self, spot: ParkingSpot) -> None:
        self.spots[spot.id] = spot

    def park(self, vehicle: Vehicle) -> Ticket | None:
        with self._lock:                                     # atomic find-and-claim
            for spot in self.spots.values():
                if spot.is_free and spot.type == vehicle.type:
                    spot.park(vehicle)
                    ticket = Ticket(
                        id=str(uuid4()), spot_id=spot.id,
                        plate=vehicle.plate, entry_time=datetime.now(),
                    )
                    self.active_tickets[ticket.id] = ticket
                    return ticket
            return None  # lot full for this vehicle type

    def unpark(self, ticket_id: str) -> float:
        with self._lock:
            ticket = self.active_tickets.pop(ticket_id)
            ticket.exit_time = datetime.now()
            self.spots[ticket.spot_id].vacate()
            return self.pricing.calculate_fee(ticket)

6. Concurrency

  • The naive version (existing vault note) had no locking — two threads calling park() simultaneously could both pass the is_free check on the same spot before either sets spot.vehicle, double-booking it. The Lock() around the whole find-and-claim in park() closes this window.
  • Granularity trade-off: one lock for the entire lot serializes all park/unpark calls — correct, but a bottleneck at high throughput (an airport lot with thousands of spots). A per-spot lock (or per-floor) would allow concurrent parks in different sections; the single-lock version is the right starting answer, with this as the scaling follow-up.
  • unpark() uses .pop() on the ticket dict — calling it twice on the same ticket_id raises KeyError rather than silently double-charging or double-vacating; worth naming this as deliberate (fail loud on a re-used ticket) rather than an oversight.

7. Edge Cases

  • Lot full for a vehicle's type — park() returns None; caller must handle (reject entry, or queue).
  • Lost/duplicate ticket — unpark() on an unknown ticket_id should raise a clear error, not silently no-op.
  • Vehicle larger than any available spot type — requirements should clarify whether a truck can use a car spot (usually no) or whether spot-type matching is strict; the implementation above assumes strict matching.

8. Extensibility

  • New vehicle type (e.g., bicycle): add an enum value + spots of that type — zero changes to ParkingLot.park() logic, since matching is by enum equality, not a type-specific branch.
  • New pricing scheme (e.g., flat daily rate, first-hour-free): implement a new PricingStrategy subclass, pass it into ParkingLot.__init__ — zero changes to ParkingLot itself. This is the concrete payoff of using Strategy from the start.
  • EV charging spots: add a requires_charging: bool flag to ParkingSpot and extend matching logic — or, for a cleaner OCP-compliant version, introduce a SpotFeature set on each spot and match on required features rather than a single VehicleType enum, avoiding a combinatorial explosion of enum values (CAR, CAR_EV, CAR_HANDICAP, CAR_EV_HANDICAP, ...).
  • Multi-floor display board ("2 spots free on floor 3"): an Observer (see [[OOD Design Patterns]]) subscribed to park()/unpark() events, decoupled from the core allocation logic.

9. Interview Drills

  1. Two cars arrive at the exact same moment for the last free spot. Walk through what happens with your code. — Both threads call park(); the Lock serializes them, so the first to acquire it claims the spot and returns a Ticket, the second finds no free spot of that type after acquiring the lock next and returns None. Without the lock, both could read is_free=True before either writes, double-booking.
  2. How would you support a spot that fits multiple vehicle types (a large spot that also fits motorcycles)? — Change ParkingSpot.type from a single VehicleType to a set of accepted types, and match vehicle.type in spot.accepted_types.
  3. Add support for reserved/subscription spots that regular vehicles can't use. — Add a reserved_for: str | None field on ParkingSpot; matching logic checks reserved_for is None or reserved_for == vehicle.owner_id alongside the type check — no change to the surrounding allocation flow.

Cross-links

[[SOLID Principles]] · [[OOD Design Patterns]] · [[LLD Interview Approach]] · [[Rate Limiter (OOD)]]