Design a parking lot

01The design, in the six-step framework

1. Requirements and use cases

A driver arrives and receives a ticket for a spot that fits the vehicle. A driver leaves, presents the ticket, pays a fee based on time parked, and the spot is freed. An attendant sees how many spots of each size are free. The lot has several floors with small, medium and large spots; a vehicle may take a larger spot than it needs when no exact fit is free. A full lot refuses entry.

Out of scope: payment processing, reservations and physical gates. Concurrent arrivals are a separate problem, the multi-threaded parking lot. These cuts are the first thing to say out loud: the question is deliberately vague, and turning a one-line prompt into a spec is the first scoring point (see from requirements to classes).

Constraints: the design must absorb a named future change with a small edit. Pick two: a new pricing scheme and a new way of choosing spots. Money is held in integer paise, never a float.

2. Core entities and relationships

• ParkingLot: the orchestrator; every use case starts here, and it owns the map of active tickets.
• Floor: holds spots and finds the tightest fit on that floor.
• Spot: knows its size and whether it is free. It enforces its own rule through fits.
• Vehicle, Ticket, Receipt: immutable records.
• AllocationStrategy, PricingStrategy: the two points of planned change.

Read the relationships in the diagram as sentences. A lot composes floors and a floor composes spots: they exist only as part of the building. A ticket refers to a spot by id, because a ticket outlives the moment and should not hold a live object. Strategies are used through interfaces, so the lot does not know which one it has.

3. Interfaces and key methods

class ParkingLot:
    def enter(self, vehicle: Vehicle, now: datetime) -> Ticket:
        """Assign a spot and issue a ticket; raises LotFull."""
    def leave(self, ticket_id: str, now: datetime) -> Receipt:
        """Free the spot and price the stay; raises UnknownTicket."""
    def available(self, size: SpotSize) -> int: ...

class Floor:
    def find_spot(self, vehicle: Vehicle) -> Spot | None: ...
    def available(self, size: SpotSize) -> int: ...

class AllocationStrategy(Protocol):
    def choose(self, floors: Sequence[Floor], vehicle: Vehicle) -> Spot | None: ...

class PricingStrategy(Protocol):
    def price(self, ticket: Ticket, exit_time: datetime) -> int:
        """Fee in paise, so money is never a float."""

Invariants: a spot is occupied if and only if an active ticket refers to it; leave works once per ticket, because the entry is popped; available always agrees with the spots, since it is computed from them. Each rule lives with the data it concerns, which is single responsibility in practice: pricing never touches a spot, and a spot never knows about money.

4. Design patterns and the choices behind them

An enum for sizes, not a Car subclass

The textbook answer draws Vehicle with Car, Bike and Truck subclasses. In this problem those classes would differ in one value and no behaviour, so a hierarchy is ceremony. An ordered enum gives spot.size >= vehicle.size in one comparison, and a new vehicle type is a value, with no new class. Move to subclasses the day a vehicle behaves differently, for example electric cars needing a charger.

Strategy for the two named changes

A weekend rate or a nearest-to-exit policy should not edit ParkingLot. Each sits behind a one-method strategy. These are the lot's extensibility points, chosen on purpose. Adding a strategy for every noun is over-engineering; interviewers penalise forced patterns as readily as missing ones.

Dependency injection rather than a singleton

Older guides make ParkingLot a singleton. Nothing here needs that, and a global instance makes tests share state. Passing floors and strategies into the constructor costs nothing. A factory function that builds a standard lot from a layout is useful if construction gets long, and it is the only factory this design needs.

Time passed in

now is a parameter, so a test can price a three-hour stay without waiting three hours.

5. Core flow and code

1. A van of size MEDIUM arrives. enter asks the allocation strategy to choose.
2. LowestFloorFirst asks each floor; Floor.find_spot filters with Spot.fits and returns the smallest that fits.
3. The lot calls spot.assign, builds a Ticket and stores the pair in _active.
4. If no floor has a fit, LotFull is raised and nothing has changed.
5. Later, leave(ticket_id, now) pops the entry and releases the spot.
6. The pricing strategy computes the fee from the ticket; a stay of 2 hours 10 minutes rounds up to 3 hours, or 12,000 paise in a medium spot.
7. A second leave with the same id raises UnknownTicket, so a fee cannot be charged twice.

from __future__ import annotations
import math, uuid
from dataclasses import dataclass, field
from datetime import datetime
from enum import IntEnum
from typing import Protocol, Sequence

class SpotSize(IntEnum):
    SMALL = 1; MEDIUM = 2; LARGE = 3        # ordered: a car may take a larger spot

class LotFull(Exception):
    pass
class UnknownTicket(Exception):
    pass

@dataclass(frozen=True)
class Vehicle:
    plate: str
    size: SpotSize

@dataclass
class Spot:
    spot_id: str
    size: SpotSize
    occupied_by: str | None = None

    def fits(self, vehicle: Vehicle) -> bool:
        return self.occupied_by is None and self.size >= vehicle.size

    def assign(self, plate: str) -> None:
        self.occupied_by = plate

    def release(self) -> None:
        self.occupied_by = None

class Floor:
    def __init__(self, number: int, spots: Sequence[Spot]) -> None:
        self.number = number
        self.spots = list(spots)

    def find_spot(self, vehicle: Vehicle) -> Spot | None:
        fitting = [s for s in self.spots if s.fits(vehicle)]
        return min(fitting, key=lambda s: s.size, default=None)  # tightest fit

    def available(self, size: SpotSize) -> int:
        return sum(1 for s in self.spots if s.size == size and s.occupied_by is None)

@dataclass(frozen=True)
class Ticket:
    ticket_id: str
    plate: str
    spot_id: str
    entered_at: datetime
    size: SpotSize

@dataclass(frozen=True)
class Receipt:
    ticket_id: str
    fee: int
    exited_at: datetime

class AllocationStrategy(Protocol):
    def choose(self, floors: Sequence[Floor], vehicle: Vehicle) -> Spot | None: ...

class PricingStrategy(Protocol):
    def price(self, ticket: Ticket, exit_time: datetime) -> int: ...

class LowestFloorFirst:
    def choose(self, floors: Sequence[Floor], vehicle: Vehicle) -> Spot | None:
        for floor in floors:
            spot = floor.find_spot(vehicle)
            if spot is not None:
                return spot
        return None

class HourlyPricing:
    RATES = {SpotSize.SMALL: 2000, SpotSize.MEDIUM: 4000, SpotSize.LARGE: 8000}   # paise per hour

    def price(self, ticket: Ticket, exit_time: datetime) -> int:
        hours = max(1, math.ceil((exit_time - ticket.entered_at).total_seconds() / 3600))
        return hours * self.RATES[ticket.size]

class ParkingLot:
    def __init__(self, floors: Sequence[Floor], allocation: AllocationStrategy,
                 pricing: PricingStrategy) -> None:
        self._floors = list(floors)
        self._allocation = allocation
        self._pricing = pricing
        self._active: dict[str, tuple[Ticket, Spot]] = {}

    def enter(self, vehicle: Vehicle, now: datetime) -> Ticket:
        spot = self._allocation.choose(self._floors, vehicle)
        if spot is None:
            raise LotFull(vehicle.plate)
        spot.assign(vehicle.plate)
        ticket = Ticket(uuid.uuid4().hex, vehicle.plate, spot.spot_id, now, spot.size)
        self._active[ticket.ticket_id] = (ticket, spot)
        return ticket

    def leave(self, ticket_id: str, now: datetime) -> Receipt:
        if ticket_id not in self._active:
            raise UnknownTicket(ticket_id)
        ticket, spot = self._active.pop(ticket_id)
        spot.release()
        return Receipt(ticket_id, self._pricing.price(ticket, now), now)

    def available(self, size: SpotSize) -> int:
        return sum(f.available(size) for f in self._floors)

6. Extensions, concurrency and what interviewers probe

• "Add electric charging spots": add a features set to Spot and a requirement on Vehicle, then extend fits. No strategy changes.
• "Add monthly passes": a new PricingStrategy that checks the plate. ParkingLot does not change, which is the proof the seam was placed well.
• "Two cars reach the last spot together": choose then assign is a check-then-act race. The concurrent variant handles it.
• Speed: find_spot scans the floor. For thousands of spots, keep one free list per size; the interface is unchanged.
• How it is scored: per the machine-coding rubric, a working core, clear boundaries and a small seam beat a large diagram. Google interviewers reported here care where state lives. Test first: tightest fit, fallback to a larger spot, full lot, double leave, and fee rounding.
• Common mistake: a God class ParkingLot that computes fees and scans spots itself, or a float for money.

02Where this question was reported

• Hello Interview · Hello Interview breakdown (Medium, premium); requirements -> entities -> class design -> code -> extensibility; has junior/mid/senior expectations
• Educative · Grokking LLD (Educative) chapter 7; requirements, use-case/class/sequence/activity diagrams, code
• DesignGurus · DesignGurus Grokking OOD case study (Everyday Objects); team 'of hiring managers from Google'
• ByteByteGo · ByteByteGo OOD chapter 4; 45-min framework worked on this problem
• LLD Mastery · Google-tagged (Beginner, free tutorial); Singleton + Factory, spot allocation strategy
• LLD Mastery · Google-tagged along with Amazon/Microsoft/Uber; vehicle/spot hierarchy, Strategy for allocation
• LLD Canvas · Google-tagged (also Amazon, Flipkart); model spot compatibility as data so new vehicle types need no code change
• techprep.app · TechPrep lists it under Google LLD: https://www.techprep.app/problems/parking-lot-system?topic=low-level-design
• interviewkickstart.com · Interview Kickstart Google list: 'Design a parking lot system' and 'Design a parking garage'
• IGotAnOffer · IGotAnOffer Google system-design guide lists 'Design a parking lot (Solution)' under practice answers (page blocks bots; seen via search snippet)
• devshreebharatia.substack.com · Personal Google guide: parking lot listed as an L4 design prompt
• dev.to · Educative top-10 OOD (says asked at Google/Amazon/Microsoft/Facebook); spot types, capacity, hourly pricing, payments