Design a Parking Lot
The parking lot problem is the most frequently asked LLD interview question. It tests core OOP skills: inheritance, composition, encapsulation, and the ability to model real-world entities as classes.
How this page fits with the mock interview
Mock Interview: Design a Parking Lot plays this problem out as a 45-minute transcript, with smallest-fit allocation, one lock around enter and exit, and EV chargers and peak pricing as extensions. Read it for how to run the interview. This page is the reference answer and covers what the transcript doesn't: several allocation strategies, pricing as a strategy family, gates racing for one spot without a global lock (one compare-and-set per spot), and three different extensions.
1. Clarifying questions and requirements
Every question below changes a class or a signature, which is the test of a question worth asking.
| Question | Assumption if the interviewer says "you decide" | What it changes |
|---|---|---|
| Which vehicle types, and which spot sizes? | Motorbike, car, van. Small, medium, large. A vehicle fits its own size or bigger. | VehicleType carries a minimum Size, and no vehicle subclass hierarchy is needed |
| How is a spot chosen? | Smallest spot that fits, lowest level first. Likely to change. | AllocationStrategy interface from the start |
| Is there more than one entry gate? | Yes, four, all working at once. | Spot claiming must be atomic. This is the concurrency question. |
| How is a stay charged? | Free for 15 minutes, then per started hour, rate by vehicle type. Likely to change. | PricingStrategy interface, money in integer cents, an injected clock |
| Do we take payment? | No, just compute the fee. | No Payment class in the core |
| Can a vehicle be inside twice? Can a ticket be used twice? | Neither. | A plate index and a single-use ticket |
Write down the two "likely to change" answers: they justify the two interfaces later. The LLD interview framework explains why proposing an answer ("I'll assume four gates") beats asking an open question.
Requirements & Use Cases
Functional Requirements
- The parking lot has multiple floors, each with multiple parking spots
- Three vehicle types: motorcycle, car, truck
- Three spot sizes: small (motorcycle), medium (car), large (truck)
- A vehicle can park in a spot of equal or larger size
- Entry and exit points with ticket generation
- Payment calculation based on time parked (hourly rate)
- Display available spots per floor and per type
- Support multiple entry/exit points concurrently
Non-Functional Requirements
- Thread-safe spot allocation (no double-booking)
- O(1) spot lookup for the nearest available spot
- Extensible for new vehicle types or payment methods
Use Cases
| Actor | Use Case |
|---|---|
| Driver | Enter lot and receive ticket |
| Driver | Find available spot on a floor |
| Driver | Park vehicle in assigned spot |
| Driver | Pay at exit and leave |
| Admin | View occupancy per floor |
| Admin | Configure hourly rates |
| System | Track entry/exit timestamps |
Correction (2026-11-10): "O(1) spot lookup" isn't what the code does
The requirement above promises O(1) lookup, but the first-pass code filters every spot list on each call, which is O(n). Real O(1) needs an atomic free-list per size. For a few thousand spots an O(n) scan takes microseconds, so the complete code keeps it. Claim "O(n) over a precomputed order", not O(1).
2. Entities and relationships
| Entity | Kind | Owns or knows | Invariant it protects |
|---|---|---|---|
ParkingLot | Coordinator (service) | All spots, the open tickets, the plate index, one allocation strategy, one pricing strategy, a clock | A plate is inside at most once, and a ticket closes at most once |
Spot | Entity with identity | Its level, size, distance to each gate, and the current occupant's plate | At most one vehicle at a time, and only the occupant can release it |
Vehicle | Value object | Plate and type | None. It's immutable data. |
VehicleType / Size | Enums | VehicleType knows its minimum Size | A van never fits a medium spot |
Ticket | Value object | Ticket id, vehicle, spot, gate, entry instant | Immutable once issued |
AllocationStrategy | Interface (Strategy) | A ranking of spots for a vehicle at a gate | It ranks and never claims, so claiming stays in one place |
PricingStrategy | Interface (Strategy) | The fee for a type and a stay | Pure function of its inputs |
Two modelling choices matter most:
- Vehicle is a value with a type, not a class hierarchy. Subclasses would add only a type tag. From Nouns to Classes gives the rule: a noun with no behaviour of its own is an enum value or a field.
- The spot guards its own occupancy.
ParkingLotnever writes the occupant field. It asks the spot totryOccupy, and the spot either succeeds or says no. That one decision is what makes the concurrency story short.
3. Class diagram
classDiagram
class ParkingLot {
-spots: List~Spot~
-openTickets: Map~String,Ticket~
-ticketByPlate: Map~String,String~
-allocation: AllocationStrategy
-pricing: PricingStrategy
-clock: Clock
+enter(vehicle, gateId) Ticket
+exit(ticketId) Receipt
+freeSpotsFor(type) long
}
class Spot {
+id: String
+level: int
+size: Size
+metresToGate: Map~String,Integer~
-occupant: AtomicReference~String~
+fits(type) boolean
+isFree() boolean
+tryOccupy(plate) boolean
+release(plate) void
}
class Vehicle {
<<record>>
+plate: String
+type: VehicleType
}
class VehicleType {
<<enumeration>>
MOTORBIKE
CAR
VAN
}
class Size {
<<enumeration>>
SMALL
MEDIUM
LARGE
}
class Ticket {
<<record>>
+id: String
+vehicle: Vehicle
+spot: Spot
+gateId: String
+entry: Instant
}
class Receipt {
<<record>>
+ticketId: String
+spotId: String
+stay: Duration
+feeCents: long
}
class AllocationStrategy {
<<interface>>
+rank(vehicle, gateId) List~Spot~
}
class BestFitStrategy
class NearestToGateStrategy
class PricingStrategy {
<<interface>>
+feeCents(type, stay) long
}
class HourlyPricing
class FlatDailyPricing
ParkingLot "1" *-- "many" Spot
ParkingLot "1" o-- "many" Ticket : open
ParkingLot --> AllocationStrategy
ParkingLot --> PricingStrategy
AllocationStrategy <|.. BestFitStrategy
AllocationStrategy <|.. NearestToGateStrategy
PricingStrategy <|.. HourlyPricing
PricingStrategy <|.. FlatDailyPricing
Ticket --> Vehicle
Ticket --> Spot
Vehicle --> VehicleType
Spot --> Size
ParkingLot ..> Receipt : creates
The first-pass diagram below is kept for comparison. Its EntryPanel/ExitPanel classes only forward to the lot, and its vehicle subclasses only carry a type tag, so the design above drops them.
Class Diagram
classDiagram
class ParkingLot {
-name: string
-floors: ParkingFloor[]
-entryPanels: EntryPanel[]
-exitPanels: ExitPanel[]
-rateStrategy: PricingStrategy
+addFloor(floor: ParkingFloor)
+getAvailableSpots(type: VehicleType): number
+findSpot(vehicle: Vehicle): ParkingSpot?
}
class ParkingFloor {
-floorNumber: int
-spots: Map~SpotType, ParkingSpot[]~
+getAvailableSpots(type: SpotType): ParkingSpot[]
+assignSpot(vehicle: Vehicle): ParkingSpot?
+freeSpot(spotId: string): void
}
class ParkingSpot {
-id: string
-type: SpotType
-floor: int
-isOccupied: boolean
-vehicle: Vehicle?
+canFit(vehicle: Vehicle): boolean
+park(vehicle: Vehicle): void
+free(): Vehicle?
}
class Vehicle {
<<abstract>>
-licensePlate: string
-type: VehicleType
+getType(): VehicleType
}
class Car {
}
class Motorcycle {
}
class Truck {
}
class ParkingTicket {
-ticketId: string
-vehicle: Vehicle
-spot: ParkingSpot
-entryTime: Date
-exitTime: Date?
-amountPaid: number
+calculateFee(strategy: PricingStrategy): number
}
class EntryPanel {
-id: string
+issueTicket(vehicle: Vehicle): ParkingTicket?
}
class ExitPanel {
-id: string
+processExit(ticket: ParkingTicket): Payment
}
class PricingStrategy {
<<interface>>
+calculate(entry: Date, exit: Date, vehicleType: VehicleType): number
}
class HourlyPricing {
-rates: Map~VehicleType, number~
+calculate(entry: Date, exit: Date, vehicleType: VehicleType): number
}
class FlatRatePricing {
-dailyRate: number
+calculate(entry: Date, exit: Date, vehicleType: VehicleType): number
}
class Payment {
-amount: number
-method: PaymentMethod
-timestamp: Date
-status: PaymentStatus
}
Vehicle <|-- Car
Vehicle <|-- Motorcycle
Vehicle <|-- Truck
ParkingLot *-- ParkingFloor
ParkingLot *-- EntryPanel
ParkingLot *-- ExitPanel
ParkingLot --> PricingStrategy
ParkingFloor *-- ParkingSpot
ParkingSpot --> Vehicle
EntryPanel --> ParkingTicket
ExitPanel --> Payment
PricingStrategy <|.. HourlyPricing
PricingStrategy <|.. FlatRatePricing
ParkingTicket --> ParkingSpot
ParkingTicket --> Vehicle
4. Key flows
Entry, with two gates racing for the same spot
Under best fit, two cars arriving together both want the first free spot. Neither takes a lock. Each tries one compare-and-set, exactly one wins, and the loser moves to its next candidate.
sequenceDiagram
participant GA as Gate A
participant GB as Gate B
participant L as ParkingLot
participant AS as AllocationStrategy
participant M1 as Spot L0-M1
participant M2 as Spot L0-M2
GA->>L: enter(CAR-1, north)
GB->>L: enter(CAR-2, north)
L->>AS: rank(CAR-1, north)
AS-->>L: M1, M2, ...
L->>AS: rank(CAR-2, north)
AS-->>L: M1, M2, ...
L->>M1: tryOccupy(CAR-1)
L->>M1: tryOccupy(CAR-2)
M1-->>L: true for CAR-1
M1-->>L: false for CAR-2
L->>M2: tryOccupy(CAR-2)
M2-->>L: true
L-->>GA: Ticket T1 at M1
L-->>GB: Ticket T2 at M2
Exit
sequenceDiagram
participant G as Exit gate
participant L as ParkingLot
participant C as Clock
participant P as PricingStrategy
participant S as Spot
G->>L: exit(T1)
L->>L: remove T1 from open tickets, atomically
Note over L: a second exit with T1 finds nothing and fails here
L->>C: instant()
L->>P: feeCents(CAR, 90 minutes)
P-->>L: 400
L->>S: release(CAR-1)
L->>L: remove plate CAR-1 from index
L-->>G: Receipt 4.00
Lifecycles
Two states each, so neither needs the State pattern. The diagram still shows which call moves which object, and what may not happen.
stateDiagram-v2
state "Spot" as SpotLife {
[*] --> FREE
FREE --> OCCUPIED: tryOccupy wins the CAS
OCCUPIED --> FREE: release by the occupant
OCCUPIED --> OCCUPIED: tryOccupy by anyone returns false
}
state "Ticket" as TicketLife {
[*] --> OPEN: enter
OPEN --> CLOSED: exit
CLOSED --> [*]
}
5. Patterns used, and the alternatives rejected
Spot allocation is a Strategy
"Might change" is the Strategy pattern's cue. The interface returns a ranking and never claims a spot, so a new rule can't break the concurrency guarantee: claiming happens in one place. Rankings are precomputed in the constructor.
| Strategy | Rule | Good for | Cost |
|---|---|---|---|
| Best fit | Smallest size that fits, then lowest level | Keeping large spots free for vans | Every gate wants the same first spot, so CAS losses rise under load |
| Nearest to gate | Shortest walk from the driver's gate, then smallest | Big lots with gates on different sides | Can put a car in a large spot near a gate, wasting it |
| Fill by level | Fill level 0 before opening level 1 | Saving lighting and staff on upper levels at night | Long searches when the low levels are nearly full |
| Spread | Least occupied level first | Even wear, and fewer cars circling one level | Drivers walk further |
Pricing is a Strategy, and a cap is a Decorator
HourlyPricing and FlatDailyPricing sit behind PricingStrategy. "Never more than 20.00 a day" is a rule around another rule, so it's a Decorator (extension 3). Money is integer cents: a double fee drifts.
Alternatives considered and rejected
| Alternative | Why it was rejected |
|---|---|
One lock around enter and exit | Correct, simple, and the mock interview's choice. It serialises all gates, which is fine at four. Either answer is acceptable if you can say what it costs. |
| Vehicle subclasses | No behaviour differs. An enum with a minimum size says the same in one line. |
ParkingLot as a Singleton | Tests share state. Create one instance at startup and pass it in. |
| Factory Method for vehicles | Nothing varies in how a vehicle is built. |
Design Patterns Used
| Pattern | Where | Why |
|---|---|---|
| Strategy | PricingStrategy interface with HourlyPricing, FlatRatePricing | Swap pricing algorithms without changing ParkingLot code |
| Factory Method | Vehicle subclass constructors | Each vehicle type encapsulates its own VehicleType enum |
| Facade | ParkingLot class | Single entry point hides floor/spot/ticket complexity |
| Composition | ParkingLot -> ParkingFloor -> ParkingSpot | Natural ownership hierarchy; floors don't exist without lot |
Correction (2026-11-10): constructors aren't the Factory Method pattern
The table above lists "Vehicle subclass constructors" as Factory Method. A constructor that sets a type field is just a constructor. Factory Method is an overridable method that decides which class to instantiate, such as createVehicle(type) returning a Car or a Truck. Neither version of the code has one.
6. Complete code
The three versions share classes, rules and checks, and each prints parking lot: all checks passed. All were run before publishing (the Python race test is in section 9):
- Java 24:
javac -d out ParkingLotDemo.java && java -cp out ParkingLotDemo - Python 3.12:
python parking_lot.py - TypeScript (strict):
tsc --strict --noEmit --target es2022 --types node parking-lot.ts && npx tsx parking-lot.ts
import java.time.Clock;
import java.time.Duration;
import java.time.Instant;
import java.time.ZoneId;
import java.time.ZoneOffset;
import java.util.*;
import java.util.concurrent.*;
import java.util.concurrent.atomic.AtomicLong;
import java.util.concurrent.atomic.AtomicReference;
enum Size { SMALL, MEDIUM, LARGE }
enum VehicleType {
MOTORBIKE(Size.SMALL), CAR(Size.MEDIUM), VAN(Size.LARGE);
final Size minSize;
VehicleType(Size minSize) { this.minSize = minSize; }
}
record Vehicle(String plate, VehicleType type) {}
final class Spot {
final String id;
final int level;
final Size size;
final Map<String, Integer> metresToGate; // gateId -> walking distance
private final AtomicReference<String> occupant = new AtomicReference<>();
Spot(String id, int level, Size size, Map<String, Integer> metresToGate) {
this.id = id; this.level = level; this.size = size; this.metresToGate = Map.copyOf(metresToGate);
}
boolean fits(VehicleType t) { return size.compareTo(t.minSize) >= 0; }
boolean isFree() { return occupant.get() == null; }
/** The only way a spot becomes occupied: one atomic compare-and-set. */
boolean tryOccupy(String plate) { return occupant.compareAndSet(null, plate); }
void release(String plate) {
if (!occupant.compareAndSet(plate, null))
throw new IllegalStateException(id + " is not held by " + plate);
}
}
/** Returns spots in preference order. The lot skips spots that don't fit or are taken. */
interface AllocationStrategy {
List<Spot> rank(Vehicle vehicle, String gateId);
}
/** Smallest size that fits, then lowest level. Saves large spots for large vehicles. */
final class BestFitStrategy implements AllocationStrategy {
private final List<Spot> ordered;
BestFitStrategy(List<Spot> spots) {
ordered = spots.stream()
.sorted(Comparator.comparing((Spot s) -> s.size).thenComparingInt(s -> s.level).thenComparing(s -> s.id))
.toList();
}
public List<Spot> rank(Vehicle vehicle, String gateId) { return ordered; }
}
/** Closest to the gate the driver used, then smallest. Ordering is precomputed per gate. */
final class NearestToGateStrategy implements AllocationStrategy {
private final Map<String, List<Spot>> byGate = new HashMap<>();
NearestToGateStrategy(List<Spot> spots, Collection<String> gateIds) {
for (String g : gateIds) {
byGate.put(g, spots.stream()
.sorted(Comparator.comparingInt((Spot s) -> s.metresToGate.get(g)).thenComparing(s -> s.size))
.toList());
}
}
public List<Spot> rank(Vehicle vehicle, String gateId) {
List<Spot> ranked = byGate.get(gateId);
if (ranked == null) throw new IllegalArgumentException("unknown gate " + gateId);
return ranked;
}
}
interface PricingStrategy {
long feeCents(VehicleType type, Duration stay);
}
/** Free during the grace period, then every started hour is charged at the vehicle's rate. */
final class HourlyPricing implements PricingStrategy {
private final Map<VehicleType, Long> centsPerHour;
private final Duration grace;
HourlyPricing(Map<VehicleType, Long> centsPerHour, Duration grace) {
this.centsPerHour = Map.copyOf(centsPerHour); this.grace = grace;
}
public long feeCents(VehicleType type, Duration stay) {
if (stay.compareTo(grace) <= 0) return 0;
long startedHours = (stay.toSeconds() + 3599) / 3600;
return startedHours * centsPerHour.get(type);
}
}
/** One price per started 24 hours, whatever the vehicle. */
final class FlatDailyPricing implements PricingStrategy {
private final long centsPerDay;
FlatDailyPricing(long centsPerDay) { this.centsPerDay = centsPerDay; }
public long feeCents(VehicleType type, Duration stay) {
long startedDays = Math.max(1, (stay.toSeconds() + 86399) / 86400);
return startedDays * centsPerDay;
}
}
record Ticket(String id, Vehicle vehicle, Spot spot, String gateId, Instant entry) {}
record Receipt(String ticketId, String spotId, Duration stay, long feeCents) {}
final class ParkingLot {
private final List<Spot> spots;
private final AllocationStrategy allocation;
private final PricingStrategy pricing;
private final Clock clock;
private final ConcurrentMap<String, Ticket> openTickets = new ConcurrentHashMap<>();
private final ConcurrentMap<String, String> ticketByPlate = new ConcurrentHashMap<>();
private final AtomicLong seq = new AtomicLong();
ParkingLot(List<Spot> spots, AllocationStrategy allocation, PricingStrategy pricing, Clock clock) {
this.spots = List.copyOf(spots); this.allocation = allocation; this.pricing = pricing; this.clock = clock;
}
/** Empty means "no free spot fits this vehicle". Throws if the plate is already inside. */
Optional<Ticket> enter(Vehicle v, String gateId) {
String ticketId = "T" + seq.incrementAndGet();
if (ticketByPlate.putIfAbsent(v.plate(), ticketId) != null)
throw new IllegalStateException(v.plate() + " is already inside");
for (Spot s : allocation.rank(v, gateId)) {
// isFree() is a cheap pre-filter; tryOccupy() is the real decision.
if (s.fits(v.type()) && s.isFree() && s.tryOccupy(v.plate())) {
Ticket t = new Ticket(ticketId, v, s, gateId, clock.instant());
openTickets.put(ticketId, t);
return Optional.of(t);
}
}
ticketByPlate.remove(v.plate(), ticketId);
return Optional.empty();
}
Receipt exit(String ticketId) {
Ticket t = openTickets.remove(ticketId); // atomic: a ticket can be used once
if (t == null) throw new IllegalArgumentException("unknown or already used ticket " + ticketId);
Duration stay = Duration.between(t.entry(), clock.instant());
long fee = pricing.feeCents(t.vehicle().type(), stay);
t.spot().release(t.vehicle().plate());
ticketByPlate.remove(t.vehicle().plate(), ticketId);
return new Receipt(ticketId, t.spot().id, stay, fee);
}
long freeSpotsFor(VehicleType type) {
return spots.stream().filter(s -> s.fits(type) && s.isFree()).count();
}
}
/** A clock the test moves by hand. */
final class TestClock extends Clock {
private volatile Instant now;
TestClock(Instant start) { now = start; }
void advance(Duration d) { now = now.plus(d); }
public Instant instant() { return now; }
public ZoneId getZone() { return ZoneOffset.UTC; }
public Clock withZone(ZoneId zone) { return this; }
}
public class ParkingLotDemo {
static void check(boolean ok, String msg) { if (!ok) throw new AssertionError(msg); }
static Spot spot(String id, int level, Size size, int north, int south) {
return new Spot(id, level, size, Map.of("north", north, "south", south));
}
static HourlyPricing hourly() {
return new HourlyPricing(Map.of(VehicleType.MOTORBIKE, 100L, VehicleType.CAR, 200L, VehicleType.VAN, 350L),
Duration.ofMinutes(15));
}
public static void main(String[] args) throws Exception {
TestClock clock = new TestClock(Instant.parse("2026-11-10T08:00:00Z"));
// 1. Best fit: smallest spot that fits, large spots kept for vans.
List<Spot> small = List.of(spot("L0-S1", 0, Size.SMALL, 5, 50), spot("L0-M1", 0, Size.MEDIUM, 40, 10),
spot("L1-L1", 1, Size.LARGE, 2, 60));
ParkingLot lot = new ParkingLot(small, new BestFitStrategy(small), hourly(), clock);
check(lot.enter(new Vehicle("CAR-1", VehicleType.CAR), "north").orElseThrow().spot().id.equals("L0-M1"), "car gets medium");
check(lot.enter(new Vehicle("BIKE-1", VehicleType.MOTORBIKE), "north").orElseThrow().spot().id.equals("L0-S1"), "bike gets small");
check(lot.enter(new Vehicle("CAR-2", VehicleType.CAR), "north").orElseThrow().spot().id.equals("L1-L1"), "car overflows to large");
check(lot.enter(new Vehicle("CAR-3", VehicleType.CAR), "north").isEmpty(), "lot full for cars");
// 2. Nearest to gate: same spots, different preference per gate.
List<Spot> fresh = List.of(spot("L0-M1", 0, Size.MEDIUM, 40, 10), spot("L0-M2", 0, Size.MEDIUM, 12, 45));
ParkingLot gates = new ParkingLot(fresh, new NearestToGateStrategy(fresh, List.of("north", "south")), hourly(), clock);
check(gates.enter(new Vehicle("N-1", VehicleType.CAR), "north").orElseThrow().spot().id.equals("L0-M2"), "north gets M2");
check(gates.enter(new Vehicle("S-1", VehicleType.CAR), "south").orElseThrow().spot().id.equals("L0-M1"), "south gets M1");
// 3. Pricing boundaries with the injected clock.
PricingStrategy p = hourly();
check(p.feeCents(VehicleType.CAR, Duration.ofMinutes(15)) == 0, "grace is free");
check(p.feeCents(VehicleType.CAR, Duration.ofMinutes(61)) == 400, "61 min = 2 started hours");
clock.advance(Duration.ofMinutes(90));
Receipt r = lot.exit("T1"); // CAR-1 entered first
check(r.feeCents() == 400 && r.spotId().equals("L0-M1"), "90 min car = 4.00");
check(lot.freeSpotsFor(VehicleType.CAR) == 1, "spot freed");
// 4. A ticket can be used once, and a plate can be inside once.
boolean threw = false;
try { lot.exit("T1"); } catch (IllegalArgumentException e) { threw = true; }
check(threw, "double exit rejected");
threw = false;
try { lot.enter(new Vehicle("BIKE-1", VehicleType.MOTORBIKE), "south"); } catch (IllegalStateException e) { threw = true; }
check(threw, "same plate twice rejected");
// 5. Concurrency: 16 gates race for 40 spots (distinct plates), then 8 gates read one plate.
for (int round = 0; round < 100; round++) {
check(race(40, 16, false) == 40, "exactly 40 tickets for 40 spots");
check(race(8, 8, true) == 1, "one ticket per plate");
}
System.out.println("parking lot: all checks passed");
}
/** Starts `gates` threads together; each tries 10 cars (or the same plate). Returns tickets issued. */
static int race(int spotCount, int gates, boolean samePlate) throws Exception {
List<Spot> spots = new ArrayList<>();
for (int i = 0; i < spotCount; i++) spots.add(spot("M" + i, i / 10, Size.MEDIUM, i, i));
ParkingLot lot = new ParkingLot(spots, new BestFitStrategy(spots), hourly(), Clock.systemUTC());
ExecutorService pool = Executors.newFixedThreadPool(gates);
CountDownLatch start = new CountDownLatch(1);
List<Future<Integer>> results = new ArrayList<>();
for (int g = 0; g < gates; g++) {
String prefix = "G" + g + "-";
results.add(pool.submit(() -> {
start.await();
int won = 0;
for (int c = 0; c < 10; c++) {
try {
String plate = samePlate ? "SAME-1" : prefix + c;
if (lot.enter(new Vehicle(plate, VehicleType.CAR), "north").isPresent()) won++;
} catch (IllegalStateException alreadyInside) { /* expected for samePlate */ }
}
return won;
}));
}
start.countDown();
int total = 0;
for (Future<Integer> f : results) total += f.get();
pool.shutdown();
long used = spotCount - lot.freeSpotsFor(VehicleType.CAR);
check(used == total, "spots used must equal tickets issued");
return total;
}
}
from __future__ import annotations
import itertools
import threading
from dataclasses import dataclass
from datetime import datetime, timedelta
from enum import Enum
from typing import Callable, Iterable, Optional, Protocol
class Size(Enum):
SMALL = 1
MEDIUM = 2
LARGE = 3
class VehicleType(Enum):
MOTORBIKE = Size.SMALL
CAR = Size.MEDIUM
VAN = Size.LARGE
@property
def min_size(self) -> Size:
return self.value
@dataclass(frozen=True)
class Vehicle:
plate: str
type: VehicleType
class Spot:
def __init__(self, spot_id: str, level: int, size: Size, metres_to_gate: dict[str, int]):
self.id = spot_id
self.level = level
self.size = size
self.metres_to_gate = dict(metres_to_gate)
self._occupant: Optional[str] = None
self._lock = threading.Lock()
def fits(self, t: VehicleType) -> bool:
return self.size.value >= t.min_size.value
def is_free(self) -> bool:
return self._occupant is None
def try_occupy(self, plate: str) -> bool:
"""Compare-and-set: the check and the write happen under one lock."""
with self._lock:
if self._occupant is not None:
return False
self._occupant = plate
return True
def release(self, plate: str) -> None:
with self._lock:
if self._occupant != plate:
raise RuntimeError(f"{self.id} is not held by {plate}")
self._occupant = None
class AllocationStrategy(Protocol):
def rank(self, vehicle: Vehicle, gate_id: str) -> list[Spot]: ...
class BestFitStrategy:
"""Smallest size that fits, then lowest level."""
def __init__(self, spots: Iterable[Spot]):
self._ordered = sorted(spots, key=lambda s: (s.size.value, s.level, s.id))
def rank(self, vehicle: Vehicle, gate_id: str) -> list[Spot]:
return self._ordered
class NearestToGateStrategy:
"""Closest to the driver's gate, then smallest. Precomputed once per gate."""
def __init__(self, spots: Iterable[Spot], gate_ids: Iterable[str]):
spots = list(spots)
self._by_gate = {
g: sorted(spots, key=lambda s, g=g: (s.metres_to_gate[g], s.size.value)) for g in gate_ids
}
def rank(self, vehicle: Vehicle, gate_id: str) -> list[Spot]:
if gate_id not in self._by_gate:
raise ValueError(f"unknown gate {gate_id}")
return self._by_gate[gate_id]
class PricingStrategy(Protocol):
def fee_cents(self, vehicle_type: VehicleType, stay: timedelta) -> int: ...
class HourlyPricing:
def __init__(self, cents_per_hour: dict[VehicleType, int], grace: timedelta):
self._rates = dict(cents_per_hour)
self._grace = grace
def fee_cents(self, vehicle_type: VehicleType, stay: timedelta) -> int:
if stay <= self._grace:
return 0
started_hours = -(-int(stay.total_seconds()) // 3600) # ceiling division
return started_hours * self._rates[vehicle_type]
class FlatDailyPricing:
def __init__(self, cents_per_day: int):
self._cents_per_day = cents_per_day
def fee_cents(self, vehicle_type: VehicleType, stay: timedelta) -> int:
started_days = max(1, -(-int(stay.total_seconds()) // 86400))
return started_days * self._cents_per_day
@dataclass(frozen=True)
class Ticket:
id: str
vehicle: Vehicle
spot: Spot
gate_id: str
entry: datetime
@dataclass(frozen=True)
class Receipt:
ticket_id: str
spot_id: str
stay: timedelta
fee_cents: int
class ParkingLot:
def __init__(self, spots: Iterable[Spot], allocation: AllocationStrategy,
pricing: PricingStrategy, clock: Callable[[], datetime]):
self._spots = list(spots)
self._allocation = allocation
self._pricing = pricing
self._clock = clock
self._open_tickets: dict[str, Ticket] = {}
self._ticket_by_plate: dict[str, str] = {}
self._index_lock = threading.Lock() # guards the two dicts, never held while scanning spots
self._seq = itertools.count(1)
def enter(self, vehicle: Vehicle, gate_id: str) -> Optional[Ticket]:
with self._index_lock:
ticket_id = f"T{next(self._seq)}"
if vehicle.plate in self._ticket_by_plate:
raise RuntimeError(f"{vehicle.plate} is already inside")
self._ticket_by_plate[vehicle.plate] = ticket_id
for spot in self._allocation.rank(vehicle, gate_id):
if spot.fits(vehicle.type) and spot.is_free() and spot.try_occupy(vehicle.plate):
ticket = Ticket(ticket_id, vehicle, spot, gate_id, self._clock())
with self._index_lock:
self._open_tickets[ticket_id] = ticket
return ticket
with self._index_lock:
del self._ticket_by_plate[vehicle.plate]
return None
def exit(self, ticket_id: str) -> Receipt:
with self._index_lock:
ticket = self._open_tickets.pop(ticket_id, None)
if ticket is None:
raise KeyError(f"unknown or already used ticket {ticket_id}")
stay = self._clock() - ticket.entry
fee = self._pricing.fee_cents(ticket.vehicle.type, stay)
ticket.spot.release(ticket.vehicle.plate)
with self._index_lock:
self._ticket_by_plate.pop(ticket.vehicle.plate, None)
return Receipt(ticket_id, ticket.spot.id, stay, fee)
def free_spots_for(self, vehicle_type: VehicleType) -> int:
return sum(1 for s in self._spots if s.fits(vehicle_type) and s.is_free())
class FakeClock:
def __init__(self, start: datetime):
self.now = start
def __call__(self) -> datetime:
return self.now
def advance(self, delta: timedelta) -> None:
self.now += delta
def spot(spot_id: str, level: int, size: Size, north: int, south: int) -> Spot:
return Spot(spot_id, level, size, {"north": north, "south": south})
def hourly() -> HourlyPricing:
return HourlyPricing({VehicleType.MOTORBIKE: 100, VehicleType.CAR: 200, VehicleType.VAN: 350},
timedelta(minutes=15))
def demo() -> None:
clock = FakeClock(datetime(2026, 11, 10, 8, 0))
spots = [spot("L0-S1", 0, Size.SMALL, 5, 50), spot("L0-M1", 0, Size.MEDIUM, 40, 10),
spot("L1-L1", 1, Size.LARGE, 2, 60)]
lot = ParkingLot(spots, BestFitStrategy(spots), hourly(), clock)
assert lot.enter(Vehicle("CAR-1", VehicleType.CAR), "north").spot.id == "L0-M1"
assert lot.enter(Vehicle("BIKE-1", VehicleType.MOTORBIKE), "north").spot.id == "L0-S1"
assert lot.enter(Vehicle("CAR-2", VehicleType.CAR), "north").spot.id == "L1-L1"
assert lot.enter(Vehicle("CAR-3", VehicleType.CAR), "north") is None
fresh = [spot("L0-M1", 0, Size.MEDIUM, 40, 10), spot("L0-M2", 0, Size.MEDIUM, 12, 45)]
gates = ParkingLot(fresh, NearestToGateStrategy(fresh, ["north", "south"]), hourly(), clock)
assert gates.enter(Vehicle("N-1", VehicleType.CAR), "north").spot.id == "L0-M2"
assert gates.enter(Vehicle("S-1", VehicleType.CAR), "south").spot.id == "L0-M1"
p = hourly()
assert p.fee_cents(VehicleType.CAR, timedelta(minutes=15)) == 0
assert p.fee_cents(VehicleType.CAR, timedelta(minutes=61)) == 400
assert FlatDailyPricing(1500).fee_cents(VehicleType.CAR, timedelta(hours=25)) == 3000
clock.advance(timedelta(minutes=90))
receipt = lot.exit("T1")
assert receipt.fee_cents == 400 and receipt.spot_id == "L0-M1"
assert lot.free_spots_for(VehicleType.CAR) == 1
try:
lot.exit("T1")
raise AssertionError("double exit must fail")
except KeyError:
pass
try:
lot.enter(Vehicle("BIKE-1", VehicleType.MOTORBIKE), "south")
raise AssertionError("same plate twice must fail")
except RuntimeError:
pass
print("parking lot: all checks passed")
if __name__ == "__main__":
demo()
enum Size { SMALL = 1, MEDIUM = 2, LARGE = 3 }
enum VehicleType { MOTORBIKE = "MOTORBIKE", CAR = "CAR", VAN = "VAN" }
const MIN_SIZE: Record<VehicleType, Size> = {
[VehicleType.MOTORBIKE]: Size.SMALL,
[VehicleType.CAR]: Size.MEDIUM,
[VehicleType.VAN]: Size.LARGE,
};
interface Vehicle { readonly plate: string; readonly type: VehicleType }
class Spot {
private occupant: string | null = null;
constructor(
readonly id: string,
readonly level: number,
readonly size: Size,
readonly metresToGate: ReadonlyMap<string, number>,
) {}
fits(t: VehicleType): boolean { return this.size >= MIN_SIZE[t]; }
isFree(): boolean { return this.occupant === null; }
/** Synchronous check-and-set. No await inside, so no other gate can interleave. */
tryOccupy(plate: string): boolean {
if (this.occupant !== null) return false;
this.occupant = plate;
return true;
}
release(plate: string): void {
if (this.occupant !== plate) throw new Error(`${this.id} is not held by ${plate}`);
this.occupant = null;
}
}
interface AllocationStrategy { rank(vehicle: Vehicle, gateId: string): readonly Spot[] }
class BestFitStrategy implements AllocationStrategy {
private readonly ordered: readonly Spot[];
constructor(spots: readonly Spot[]) {
this.ordered = [...spots].sort((a, b) => a.size - b.size || a.level - b.level || a.id.localeCompare(b.id));
}
rank(): readonly Spot[] { return this.ordered; }
}
class NearestToGateStrategy implements AllocationStrategy {
private readonly byGate = new Map<string, readonly Spot[]>();
constructor(spots: readonly Spot[], gateIds: readonly string[]) {
for (const g of gateIds) {
this.byGate.set(g, [...spots].sort((a, b) =>
a.metresToGate.get(g)! - b.metresToGate.get(g)! || a.size - b.size));
}
}
rank(_v: Vehicle, gateId: string): readonly Spot[] {
const ranked = this.byGate.get(gateId);
if (!ranked) throw new Error(`unknown gate ${gateId}`);
return ranked;
}
}
interface PricingStrategy { feeCents(type: VehicleType, stayMs: number): number }
const HOUR_MS = 3_600_000;
const DAY_MS = 24 * HOUR_MS;
class HourlyPricing implements PricingStrategy {
constructor(private readonly centsPerHour: Record<VehicleType, number>, private readonly graceMs: number) {}
feeCents(type: VehicleType, stayMs: number): number {
if (stayMs <= this.graceMs) return 0;
return Math.ceil(stayMs / HOUR_MS) * this.centsPerHour[type];
}
}
class FlatDailyPricing implements PricingStrategy {
constructor(private readonly centsPerDay: number) {}
feeCents(_type: VehicleType, stayMs: number): number {
return Math.max(1, Math.ceil(stayMs / DAY_MS)) * this.centsPerDay;
}
}
interface Ticket { readonly id: string; readonly vehicle: Vehicle; readonly spot: Spot; readonly gateId: string; readonly entryMs: number }
interface Receipt { readonly ticketId: string; readonly spotId: string; readonly stayMs: number; readonly feeCents: number }
class ParkingLot {
private readonly openTickets = new Map<string, Ticket>();
private readonly ticketByPlate = new Map<string, string>();
private seq = 0;
constructor(
private readonly spots: readonly Spot[],
private readonly allocation: AllocationStrategy,
private readonly pricing: PricingStrategy,
private readonly now: () => number,
) {}
/** null means no free spot fits. Throws if the plate is already inside. */
enter(vehicle: Vehicle, gateId: string): Ticket | null {
if (this.ticketByPlate.has(vehicle.plate)) throw new Error(`${vehicle.plate} is already inside`);
const id = `T${++this.seq}`;
for (const spot of this.allocation.rank(vehicle, gateId)) {
if (spot.fits(vehicle.type) && spot.tryOccupy(vehicle.plate)) {
const ticket: Ticket = { id, vehicle, spot, gateId, entryMs: this.now() };
this.openTickets.set(id, ticket);
this.ticketByPlate.set(vehicle.plate, id);
return ticket;
}
}
return null;
}
exit(ticketId: string): Receipt {
const ticket = this.openTickets.get(ticketId);
if (!ticket) throw new Error(`unknown or already used ticket ${ticketId}`);
this.openTickets.delete(ticketId);
const stayMs = this.now() - ticket.entryMs;
const feeCents = this.pricing.feeCents(ticket.vehicle.type, stayMs);
ticket.spot.release(ticket.vehicle.plate);
this.ticketByPlate.delete(ticket.vehicle.plate);
return { ticketId, spotId: ticket.spot.id, stayMs, feeCents };
}
freeSpotsFor(type: VehicleType): number {
return this.spots.filter((s) => s.fits(type) && s.isFree()).length;
}
}
// ─── Demo and self-checks ─────────────────────────────────
function check(ok: boolean, msg: string): void { if (!ok) throw new Error(`check failed: ${msg}`); }
const spot = (id: string, level: number, size: Size, north: number, south: number) =>
new Spot(id, level, size, new Map([["north", north], ["south", south]]));
const hourly = () => new HourlyPricing({ MOTORBIKE: 100, CAR: 200, VAN: 350 }, 15 * 60_000);
/** Stands in for a camera read at the gate: real I/O, so the gate yields to the event loop. */
const readPlate = (plate: string) => new Promise<string>((r) => setTimeout(() => r(plate), Math.random() * 3));
async function main(): Promise<void> {
let nowMs = Date.parse("2026-11-10T08:00:00Z");
const clock = () => nowMs;
const spots = [spot("L0-S1", 0, Size.SMALL, 5, 50), spot("L0-M1", 0, Size.MEDIUM, 40, 10), spot("L1-L1", 1, Size.LARGE, 2, 60)];
const lot = new ParkingLot(spots, new BestFitStrategy(spots), hourly(), clock);
check(lot.enter({ plate: "CAR-1", type: VehicleType.CAR }, "north")?.spot.id === "L0-M1", "car gets medium");
check(lot.enter({ plate: "BIKE-1", type: VehicleType.MOTORBIKE }, "north")?.spot.id === "L0-S1", "bike gets small");
check(lot.enter({ plate: "CAR-2", type: VehicleType.CAR }, "north")?.spot.id === "L1-L1", "car overflows");
check(lot.enter({ plate: "CAR-3", type: VehicleType.CAR }, "north") === null, "full");
const fresh = [spot("L0-M1", 0, Size.MEDIUM, 40, 10), spot("L0-M2", 0, Size.MEDIUM, 12, 45)];
const gates = new ParkingLot(fresh, new NearestToGateStrategy(fresh, ["north", "south"]), hourly(), clock);
check(gates.enter({ plate: "N-1", type: VehicleType.CAR }, "north")?.spot.id === "L0-M2", "north");
check(gates.enter({ plate: "S-1", type: VehicleType.CAR }, "south")?.spot.id === "L0-M1", "south");
const p = hourly();
check(p.feeCents(VehicleType.CAR, 15 * 60_000) === 0, "grace");
check(p.feeCents(VehicleType.CAR, 61 * 60_000) === 400, "61 min");
nowMs += 90 * 60_000;
const r = lot.exit("T1");
check(r.feeCents === 400 && r.spotId === "L0-M1", "90 min car");
let threw = false;
try { lot.exit("T1"); } catch { threw = true; }
check(threw, "double exit rejected");
// Concurrency: 16 async gates, each awaiting a camera read before entering.
const many = Array.from({ length: 40 }, (_, i) => spot(`M${i}`, Math.floor(i / 10), Size.MEDIUM, i, 40 - i));
const busy = new ParkingLot(many, new BestFitStrategy(many), hourly(), clock);
const gate = async (g: number) => {
let won = 0;
for (let c = 0; c < 10; c++) {
const plate = await readPlate(`G${g}-${c}`);
if (busy.enter({ plate, type: VehicleType.CAR }, "north")) won++;
}
return won;
};
const wins = await Promise.all(Array.from({ length: 16 }, (_, g) => gate(g)));
check(wins.reduce((a, b) => a + b, 0) === 40, "exactly 40 tickets");
check(busy.freeSpotsFor(VehicleType.CAR) === 0, "all taken once");
// The bug the synchronous tryOccupy prevents: an await between "is it free?" and "take it".
const one = spot("X", 0, Size.MEDIUM, 0, 0);
const holders: string[] = [];
const naiveGate = async (plate: string) => {
if (one.isFree()) {
await readPlate(plate); // yields: the other gate runs here
holders.push(plate); // both think they got it
}
};
await Promise.all([naiveGate("A"), naiveGate("B")]);
check(holders.length === 2, "naive check-then-act double-assigns");
console.log("parking lot: all checks passed");
}
main().catch((e) => { console.error(e); process.exit(1); });
Earlier reference implementation
The first version of this page shipped the code below. It's a fair whiteboard answer, but it has no compare-and-set (so it isn't safe with concurrent gates), no injected clock, and floating-point fees.
Core Classes & Interfaces
TypeScript Implementation
// ─── Enums ───────────────────────────────────────────────
enum VehicleType {
MOTORCYCLE = 'MOTORCYCLE',
CAR = 'CAR',
TRUCK = 'TRUCK',
}
enum SpotType {
SMALL = 'SMALL',
MEDIUM = 'MEDIUM',
LARGE = 'LARGE',
}
enum PaymentMethod {
CASH = 'CASH',
CREDIT_CARD = 'CREDIT_CARD',
UPI = 'UPI',
}
enum PaymentStatus {
PENDING = 'PENDING',
COMPLETED = 'COMPLETED',
FAILED = 'FAILED',
}
// ─── Vehicle hierarchy ───────────────────────────────────
abstract class Vehicle {
constructor(
public readonly licensePlate: string,
public readonly type: VehicleType
) {}
}
class Car extends Vehicle {
constructor(licensePlate: string) {
super(licensePlate, VehicleType.CAR);
}
}
class Motorcycle extends Vehicle {
constructor(licensePlate: string) {
super(licensePlate, VehicleType.MOTORCYCLE);
}
}
class Truck extends Vehicle {
constructor(licensePlate: string) {
super(licensePlate, VehicleType.TRUCK);
}
}
// ─── Vehicle ↔ Spot compatibility ────────────────────────
const VEHICLE_TO_MIN_SPOT: Record<VehicleType, SpotType> = {
[VehicleType.MOTORCYCLE]: SpotType.SMALL,
[VehicleType.CAR]: SpotType.MEDIUM,
[VehicleType.TRUCK]: SpotType.LARGE,
};
const SPOT_ORDER: SpotType[] = [SpotType.SMALL, SpotType.MEDIUM, SpotType.LARGE];
function canFit(spotType: SpotType, vehicleType: VehicleType): boolean {
const minSpot = VEHICLE_TO_MIN_SPOT[vehicleType];
return SPOT_ORDER.indexOf(spotType) >= SPOT_ORDER.indexOf(minSpot);
}
// ─── Parking Spot ────────────────────────────────────────
class ParkingSpot {
private vehicle: Vehicle | null = null;
constructor(
public readonly id: string,
public readonly type: SpotType,
public readonly floor: number
) {}
get isOccupied(): boolean {
return this.vehicle !== null;
}
canFitVehicle(vehicle: Vehicle): boolean {
return !this.isOccupied && canFit(this.type, vehicle.type);
}
park(vehicle: Vehicle): void {
if (!this.canFitVehicle(vehicle)) {
throw new Error(`Spot ${this.id} cannot fit ${vehicle.type}`);
}
this.vehicle = vehicle;
}
free(): Vehicle | null {
const v = this.vehicle;
this.vehicle = null;
return v;
}
getVehicle(): Vehicle | null {
return this.vehicle;
}
}
// ─── Parking Floor ───────────────────────────────────────
class ParkingFloor {
private spots: Map<SpotType, ParkingSpot[]> = new Map();
constructor(public readonly floorNumber: number) {
for (const type of SPOT_ORDER) {
this.spots.set(type, []);
}
}
addSpot(spot: ParkingSpot): void {
this.spots.get(spot.type)!.push(spot);
}
getAvailableSpots(type: SpotType): ParkingSpot[] {
return this.spots.get(type)?.filter((s) => !s.isOccupied) ?? [];
}
/** Find the first available spot that can fit the vehicle */
assignSpot(vehicle: Vehicle): ParkingSpot | null {
const minIndex = SPOT_ORDER.indexOf(VEHICLE_TO_MIN_SPOT[vehicle.type]);
// Try smallest fitting spot first, then larger ones
for (let i = minIndex; i < SPOT_ORDER.length; i++) {
const spotType = SPOT_ORDER[i];
const available = this.getAvailableSpots(spotType);
if (available.length > 0) {
const spot = available[0];
spot.park(vehicle);
return spot;
}
}
return null;
}
freeSpot(spotId: string): void {
for (const spotList of this.spots.values()) {
const spot = spotList.find((s) => s.id === spotId);
if (spot) {
spot.free();
return;
}
}
throw new Error(`Spot ${spotId} not found on floor ${this.floorNumber}`);
}
getTotalAvailable(): number {
let count = 0;
for (const spotList of this.spots.values()) {
count += spotList.filter((s) => !s.isOccupied).length;
}
return count;
}
}
// ─── Pricing Strategy (Strategy Pattern) ─────────────────
interface PricingStrategy {
calculate(entry: Date, exit: Date, vehicleType: VehicleType): number;
}
class HourlyPricing implements PricingStrategy {
constructor(private rates: Map<VehicleType, number>) {}
calculate(entry: Date, exit: Date, vehicleType: VehicleType): number {
const hours = Math.ceil(
(exit.getTime() - entry.getTime()) / (1000 * 60 * 60)
);
const rate = this.rates.get(vehicleType) ?? 0;
return hours * rate;
}
}
class FlatRatePricing implements PricingStrategy {
constructor(private dailyRate: number) {}
calculate(entry: Date, exit: Date, _vehicleType: VehicleType): number {
const days = Math.ceil(
(exit.getTime() - entry.getTime()) / (1000 * 60 * 60 * 24)
);
return Math.max(1, days) * this.dailyRate;
}
}
// ─── Parking Ticket ──────────────────────────────────────
class ParkingTicket {
public exitTime: Date | null = null;
public amountPaid: number = 0;
constructor(
public readonly ticketId: string,
public readonly vehicle: Vehicle,
public readonly spot: ParkingSpot,
public readonly entryTime: Date = new Date()
) {}
calculateFee(strategy: PricingStrategy): number {
const exit = this.exitTime ?? new Date();
return strategy.calculate(this.entryTime, exit, this.vehicle.type);
}
}
// ─── Payment ─────────────────────────────────────────────
class Payment {
public status: PaymentStatus = PaymentStatus.PENDING;
constructor(
public readonly amount: number,
public readonly method: PaymentMethod,
public readonly timestamp: Date = new Date()
) {}
complete(): void {
this.status = PaymentStatus.COMPLETED;
}
fail(): void {
this.status = PaymentStatus.FAILED;
}
}
// ─── Entry & Exit Panels ─────────────────────────────────
class EntryPanel {
constructor(
public readonly id: string,
private lot: ParkingLot
) {}
issueTicket(vehicle: Vehicle): ParkingTicket | null {
return this.lot.enter(vehicle);
}
}
class ExitPanel {
constructor(
public readonly id: string,
private lot: ParkingLot
) {}
processExit(ticket: ParkingTicket, method: PaymentMethod): Payment | null {
return this.lot.exit(ticket, method);
}
}
// ─── Parking Lot (Facade) ────────────────────────────────
class ParkingLot {
private floors: ParkingFloor[] = [];
private activeTickets: Map<string, ParkingTicket> = new Map();
private ticketCounter: number = 0;
constructor(
public readonly name: string,
private pricingStrategy: PricingStrategy
) {}
addFloor(floor: ParkingFloor): void {
this.floors.push(floor);
}
setPricingStrategy(strategy: PricingStrategy): void {
this.pricingStrategy = strategy;
}
/** Find a spot across all floors and issue a ticket */
enter(vehicle: Vehicle): ParkingTicket | null {
for (const floor of this.floors) {
const spot = floor.assignSpot(vehicle);
if (spot) {
const ticketId = `TKT-${++this.ticketCounter}`;
const ticket = new ParkingTicket(ticketId, vehicle, spot);
this.activeTickets.set(ticketId, ticket);
return ticket;
}
}
return null; // lot is full for this vehicle type
}
/** Process payment and free the spot */
exit(ticket: ParkingTicket, method: PaymentMethod): Payment | null {
ticket.exitTime = new Date();
const fee = ticket.calculateFee(this.pricingStrategy);
const payment = new Payment(fee, method);
// In production: integrate with payment gateway here
payment.complete();
ticket.amountPaid = fee;
// Free the spot
const floor = this.floors.find(
(f) => f.floorNumber === ticket.spot.floor
);
floor?.freeSpot(ticket.spot.id);
this.activeTickets.delete(ticket.ticketId);
return payment;
}
getAvailableSpotsCount(): Map<number, number> {
const result = new Map<number, number>();
for (const floor of this.floors) {
result.set(floor.floorNumber, floor.getTotalAvailable());
}
return result;
}
}
Python Implementation
from abc import ABC, abstractmethod
from dataclasses import dataclass, field
from datetime import datetime
from enum import Enum
from math import ceil
from typing import Optional
import uuid
# ─── Enums ──────────────────────────────────────────────
class VehicleType(Enum):
MOTORCYCLE = "MOTORCYCLE"
CAR = "CAR"
TRUCK = "TRUCK"
class SpotType(Enum):
SMALL = 1
MEDIUM = 2
LARGE = 3
class PaymentMethod(Enum):
CASH = "CASH"
CREDIT_CARD = "CREDIT_CARD"
UPI = "UPI"
class PaymentStatus(Enum):
PENDING = "PENDING"
COMPLETED = "COMPLETED"
FAILED = "FAILED"
# ─── Vehicle hierarchy ──────────────────────────────────
class Vehicle(ABC):
def __init__(self, license_plate: str, vehicle_type: VehicleType):
self.license_plate = license_plate
self.vehicle_type = vehicle_type
class Car(Vehicle):
def __init__(self, license_plate: str):
super().__init__(license_plate, VehicleType.CAR)
class Motorcycle(Vehicle):
def __init__(self, license_plate: str):
super().__init__(license_plate, VehicleType.MOTORCYCLE)
class Truck(Vehicle):
def __init__(self, license_plate: str):
super().__init__(license_plate, VehicleType.TRUCK)
# ─── Spot compatibility ─────────────────────────────────
VEHICLE_TO_MIN_SPOT: dict[VehicleType, SpotType] = {
VehicleType.MOTORCYCLE: SpotType.SMALL,
VehicleType.CAR: SpotType.MEDIUM,
VehicleType.TRUCK: SpotType.LARGE,
}
SPOT_ORDER = [SpotType.SMALL, SpotType.MEDIUM, SpotType.LARGE]
def can_fit(spot_type: SpotType, vehicle_type: VehicleType) -> bool:
return spot_type.value >= VEHICLE_TO_MIN_SPOT[vehicle_type].value
# ─── Parking Spot ────────────────────────────────────────
class ParkingSpot:
def __init__(self, spot_id: str, spot_type: SpotType, floor: int):
self.id = spot_id
self.type = spot_type
self.floor = floor
self._vehicle: Optional[Vehicle] = None
@property
def is_occupied(self) -> bool:
return self._vehicle is not None
def can_fit_vehicle(self, vehicle: Vehicle) -> bool:
return not self.is_occupied and can_fit(self.type, vehicle.vehicle_type)
def park(self, vehicle: Vehicle) -> None:
if not self.can_fit_vehicle(vehicle):
raise ValueError(f"Spot {self.id} cannot fit {vehicle.vehicle_type}")
self._vehicle = vehicle
def free(self) -> Optional[Vehicle]:
v = self._vehicle
self._vehicle = None
return v
# ─── Parking Floor ───────────────────────────────────────
class ParkingFloor:
def __init__(self, floor_number: int):
self.floor_number = floor_number
self._spots: dict[SpotType, list[ParkingSpot]] = {
t: [] for t in SpotType
}
def add_spot(self, spot: ParkingSpot) -> None:
self._spots[spot.type].append(spot)
def get_available_spots(self, spot_type: SpotType) -> list[ParkingSpot]:
return [s for s in self._spots[spot_type] if not s.is_occupied]
def assign_spot(self, vehicle: Vehicle) -> Optional[ParkingSpot]:
min_index = SPOT_ORDER.index(VEHICLE_TO_MIN_SPOT[vehicle.vehicle_type])
for i in range(min_index, len(SPOT_ORDER)):
available = self.get_available_spots(SPOT_ORDER[i])
if available:
spot = available[0]
spot.park(vehicle)
return spot
return None
def free_spot(self, spot_id: str) -> None:
for spot_list in self._spots.values():
for spot in spot_list:
if spot.id == spot_id:
spot.free()
return
raise ValueError(f"Spot {spot_id} not found on floor {self.floor_number}")
def total_available(self) -> int:
return sum(
len(self.get_available_spots(t)) for t in SpotType
)
# ─── Pricing Strategy ───────────────────────────────────
class PricingStrategy(ABC):
@abstractmethod
def calculate(
self, entry: datetime, exit_time: datetime, vehicle_type: VehicleType
) -> float:
...
class HourlyPricing(PricingStrategy):
def __init__(self, rates: dict[VehicleType, float]):
self._rates = rates
def calculate(
self, entry: datetime, exit_time: datetime, vehicle_type: VehicleType
) -> float:
hours = ceil((exit_time - entry).total_seconds() / 3600)
return hours * self._rates.get(vehicle_type, 0)
class FlatRatePricing(PricingStrategy):
def __init__(self, daily_rate: float):
self._daily_rate = daily_rate
def calculate(
self, entry: datetime, exit_time: datetime, vehicle_type: VehicleType
) -> float:
days = max(1, ceil((exit_time - entry).total_seconds() / 86400))
return days * self._daily_rate
# ─── Parking Ticket ──────────────────────────────────────
@dataclass
class ParkingTicket:
ticket_id: str
vehicle: Vehicle
spot: ParkingSpot
entry_time: datetime = field(default_factory=datetime.now)
exit_time: Optional[datetime] = None
amount_paid: float = 0.0
def calculate_fee(self, strategy: PricingStrategy) -> float:
exit_t = self.exit_time or datetime.now()
return strategy.calculate(self.entry_time, exit_t, self.vehicle.vehicle_type)
# ─── Payment ────────────────────────────────────────────
@dataclass
class Payment:
amount: float
method: PaymentMethod
timestamp: datetime = field(default_factory=datetime.now)
status: PaymentStatus = PaymentStatus.PENDING
def complete(self) -> None:
self.status = PaymentStatus.COMPLETED
def fail(self) -> None:
self.status = PaymentStatus.FAILED
# ─── Parking Lot (Facade) ───────────────────────────────
class ParkingLot:
def __init__(self, name: str, pricing_strategy: PricingStrategy):
self.name = name
self._pricing = pricing_strategy
self._floors: list[ParkingFloor] = []
self._active_tickets: dict[str, ParkingTicket] = {}
self._ticket_counter = 0
def add_floor(self, floor: ParkingFloor) -> None:
self._floors.append(floor)
def set_pricing_strategy(self, strategy: PricingStrategy) -> None:
self._pricing = strategy
def enter(self, vehicle: Vehicle) -> Optional[ParkingTicket]:
for floor in self._floors:
spot = floor.assign_spot(vehicle)
if spot:
self._ticket_counter += 1
ticket_id = f"TKT-{self._ticket_counter}"
ticket = ParkingTicket(
ticket_id=ticket_id, vehicle=vehicle, spot=spot
)
self._active_tickets[ticket_id] = ticket
return ticket
return None # lot full
def exit(self, ticket: ParkingTicket, method: PaymentMethod) -> Payment:
ticket.exit_time = datetime.now()
fee = ticket.calculate_fee(self._pricing)
payment = Payment(amount=fee, method=method)
payment.complete()
ticket.amount_paid = fee
for floor in self._floors:
if floor.floor_number == ticket.spot.floor:
floor.free_spot(ticket.spot.id)
break
self._active_tickets.pop(ticket.ticket_id, None)
return payment
def get_availability(self) -> dict[int, int]:
return {f.floor_number: f.total_available() for f in self._floors}
Correction (2026-11-10): a ticket can be paid twice in the first-pass code
In the first-pass exit, nothing checks that the ticket is still active. Calling exit twice with the same ticket charges twice and calls freeSpot on a spot that may already hold another car, which evicts that car. The fix is to remove the ticket from activeTickets first and reject the call if it wasn't there, as the complete code does.
7. Concurrency
What's shared, and what must stay true
| Shared state | Invariant | Mechanism |
|---|---|---|
| Each spot's occupant | At most one vehicle per spot | AtomicReference.compareAndSet(null, plate), a lock per spot in Python, a synchronous method in TypeScript |
| Plate index | A plate is inside at most once | putIfAbsent on a ConcurrentHashMap (a short lock in Python) |
| Open tickets | A ticket closes at most once | remove returns the ticket to one caller only |
| Ticket sequence | Ids are unique | AtomicLong |
The three races
- Two gates, one spot. Both see the spot free. The compare-and-set merges "see it free" and "take it" into one step, and the loser continues down its ranking. No gate ever waits on another.
- One plate, two gates. The plate reservation runs before allocation, so the second gate fails fast and never claims a spot. The Java demo races eight threads on one plate 100 times and asserts one ticket each time.
- One ticket, two exits. Removing the ticket from the map is the decision point, and only one call gets it back.
Why compare-and-set, and what it costs
Per-spot compare-and-set lets gates that want different spots run in parallel and settles a clash over the same spot in one instruction. The cost shows under best fit at high load: every gate ranks spots identically, so they collide on the first free spot, then the next. With g gates that's up to g failed attempts per entry, nothing at four gates. At hundreds of concurrent requests, start each gate at a different offset among equally good spots, or use per-size free-lists with an atomic poll().
isFree() before tryOccupy() only skips obviously failing attempts. release(plate) succeeds only for the current occupant, so a stale exit can't free a re-occupied spot.
Language notes
- Java: each invariant spans one key or one spot, so no lock spans two objects and there's no deadlock to reason about.
- Python: the GIL doesn't make check-then-act atomic.
try_occupytakes the spot's lock, and the dictionaries share one short lock never held while scanning spots. - TypeScript: keep claims synchronous. If I/O must sit in the middle, claim first and compensate if the I/O fails.
For the general toolkit, see Thread-Safe Class Design and race conditions.
Concurrency Considerations
Critical Section: Spot Assignment
Two vehicles arriving simultaneously could be assigned the same spot. The assignSpot method is the critical section.
Solutions:
- Mutex per floor — Lock each floor independently during assignment. Vehicles on different floors don't block each other.
class ParkingFloor {
private mutex = new Mutex();
async assignSpot(vehicle: Vehicle): Promise<ParkingSpot | null> {
return this.mutex.runExclusive(() => {
// existing logic — now atomic
});
}
}
-
Optimistic locking — Use a version field on each spot.
park()checks the version hasn't changed since it was read. -
CAS (Compare-And-Swap) — Atomically set
isOccupiedfromfalsetotrue. If the CAS fails, try the next spot.
Thread-safety checklist:
activeTicketsmap: UseConcurrentHashMapor a read-write lockticketCounter: UseAtomicInteger- Spot assignment: Mutex per floor (not global — reduces contention)
8. Extensibility: "the interviewer adds X"
Answer each one in three moves: where the change goes, what doesn't change, and the code.
Extension 1: an occupancy board at each entrance
"Show the number of free spots for each vehicle type on a board at every entrance, updated live."
Where: an ObservedLot wrapper that notifies subscribers after each entry or exit, the Observer pattern. What doesn't change: everything else, including ParkingLot.
from typing import Callable
Listener = Callable[[VehicleType, int], None] # (vehicle type, free spots for it)
class ObservedLot:
"""Wraps a ParkingLot and tells subscribers when free counts change."""
def __init__(self, lot: ParkingLot):
self._lot = lot
self._listeners: list[Listener] = []
def subscribe(self, listener: Listener) -> None:
self._listeners.append(listener)
def enter(self, vehicle: Vehicle, gate_id: str) -> Optional[Ticket]:
ticket = self._lot.enter(vehicle, gate_id)
if ticket:
self._publish()
return ticket
def exit(self, ticket_id: str) -> Receipt:
receipt = self._lot.exit(ticket_id)
self._publish()
return receipt
def _publish(self) -> None:
for t in VehicleType:
free = self._lot.free_spots_for(t)
for listener in self._listeners:
listener(t, free)
class EntranceBoard:
def __init__(self) -> None:
self.shown: dict[VehicleType, int] = {}
def __call__(self, vehicle_type: VehicleType, free: int) -> None:
self.shown[vehicle_type] = free
spots = [spot("M1", 0, Size.MEDIUM, 1, 1), spot("L1", 0, Size.LARGE, 2, 2)]
observed = ObservedLot(ParkingLot(spots, BestFitStrategy(spots), hourly(), FakeClock(datetime(2026, 11, 10))))
board = EntranceBoard()
observed.subscribe(board)
t = observed.enter(Vehicle("CAR-1", VehicleType.CAR), "north")
assert board.shown[VehicleType.CAR] == 1 and board.shown[VehicleType.VAN] == 1
observed.enter(Vehicle("VAN-1", VehicleType.VAN), "north")
assert board.shown[VehicleType.VAN] == 0 and board.shown[VehicleType.CAR] == 0
observed.exit(t.id)
assert board.shown[VehicleType.CAR] == 1
print("display board ok")
Extension 2: accessible spots
"Permit holders get accessible spots first. Nobody else may use them, even when the lot is otherwise full."
Where: a strategy that wraps any other and reshapes its ranking, plus an optional permit flag on Vehicle. What doesn't change: ParkingLot, Spot, the CAS logic and pricing.
/** Vehicles may now carry an accessibility permit. Existing callers don't set it. */
interface PermitVehicle extends Vehicle { readonly accessiblePermit?: boolean }
/** Wraps any strategy: permit holders try accessible spots first, everyone else never gets them. */
class AccessibleAwareStrategy implements AllocationStrategy {
constructor(private readonly inner: AllocationStrategy, private readonly accessibleIds: ReadonlySet<string>) {}
rank(vehicle: PermitVehicle, gateId: string): readonly Spot[] {
const ranked = this.inner.rank(vehicle, gateId);
const accessible = ranked.filter((s) => this.accessibleIds.has(s.id));
const regular = ranked.filter((s) => !this.accessibleIds.has(s.id));
return vehicle.accessiblePermit ? [...accessible, ...regular] : regular;
}
}
A wrapper can reshape the ranking because strategies rank rather than claim. Both extension snippets ran against the code above with their own checks.
Extension 3: a daily price cap
"You never pay more than 20.00 per 24 hours." Where: a decorator around any PricingStrategy. Nothing else changes.
/** Decorator: any pricing, capped per started 24 hours. ParkingLot doesn't change. */
final class DailyCapPricing implements PricingStrategy {
private final PricingStrategy inner;
private final long capCentsPerDay;
DailyCapPricing(PricingStrategy inner, long capCentsPerDay) {
this.inner = inner; this.capCentsPerDay = capCentsPerDay;
}
public long feeCents(VehicleType type, Duration stay) {
long fullDays = stay.toDays();
Duration rest = stay.minusDays(fullDays);
long restFee = rest.isZero() ? 0 : Math.min(capCentsPerDay, inner.feeCents(type, rest));
return fullDays * capCentsPerDay + restFee;
}
}
Ask whether the cap is per calendar day or per 24 hours from entry. Guessing a business rule wrong is a bug.
Extensions & Follow-ups
| Extension | Design Impact |
|---|---|
| Electric vehicle charging spots | Add EVSpot extends ParkingSpot with chargerType field; add ElectricVehicle subclass |
| Reservation system | Add Reservation class with time window; assignSpot checks reservations first |
| Dynamic pricing | New SurgePricing strategy that adjusts rate based on occupancy percentage |
| Handicap spots | Add HANDICAP to SpotType enum; these spots are reserved and prioritized |
| Multi-level priority | VIP spots near entrance; use priority queue for spot assignment |
| License plate recognition | EntryPanel uses an LPRScanner interface; automated entry without manual ticket |
| Monthly subscription | Add Subscription class; exit() checks subscription before charging |
9. Testing
Test boundaries with a fake clock and no sleeps: 15:00 is free and 15:01 is one hour; a van never gets a medium spot; each strategy's order; a reusable spot after exit; a failed entry that doesn't leave the plate "inside". For concurrency, release all threads on a barrier, assert the ticket count and that spot ids are distinct, and repeat the race, because one passing run proves little. Save the Python code as parking_lot.py to run this suite:
import threading
import unittest
from datetime import datetime, timedelta
from parking_lot import (BestFitStrategy, FakeClock, ParkingLot, Size, Vehicle,
VehicleType, hourly, spot)
class ParkingLotTest(unittest.TestCase):
def setUp(self) -> None:
self.clock = FakeClock(datetime(2026, 11, 10, 8, 0))
def lot(self, spots):
return ParkingLot(spots, BestFitStrategy(spots), hourly(), self.clock)
def test_grace_period_boundary_is_free(self):
lot = self.lot([spot("M1", 0, Size.MEDIUM, 1, 1)])
t = lot.enter(Vehicle("CAR-1", VehicleType.CAR), "north")
self.clock.advance(timedelta(minutes=15))
self.assertEqual(lot.exit(t.id).fee_cents, 0)
def test_one_second_past_grace_charges_an_hour(self):
lot = self.lot([spot("M1", 0, Size.MEDIUM, 1, 1)])
t = lot.enter(Vehicle("CAR-1", VehicleType.CAR), "north")
self.clock.advance(timedelta(minutes=15, seconds=1))
self.assertEqual(lot.exit(t.id).fee_cents, 200)
def test_van_never_takes_a_medium_spot(self):
lot = self.lot([spot("M1", 0, Size.MEDIUM, 1, 1)])
self.assertIsNone(lot.enter(Vehicle("VAN-1", VehicleType.VAN), "north"))
self.assertEqual(lot.free_spots_for(VehicleType.CAR), 1)
def test_failed_entry_does_not_block_the_plate(self):
lot = self.lot([spot("S1", 0, Size.SMALL, 1, 1)])
self.assertIsNone(lot.enter(Vehicle("CAR-1", VehicleType.CAR), "north"))
self.assertIsNone(lot.enter(Vehicle("CAR-1", VehicleType.CAR), "south")) # no "already inside" error
def test_spot_is_reusable_after_exit(self):
lot = self.lot([spot("M1", 0, Size.MEDIUM, 1, 1)])
t = lot.enter(Vehicle("CAR-1", VehicleType.CAR), "north")
lot.exit(t.id)
self.assertEqual(lot.enter(Vehicle("CAR-2", VehicleType.CAR), "north").spot.id, "M1")
def test_racing_gates_never_double_assign(self):
spots = [spot(f"M{i}", 0, Size.MEDIUM, i, i) for i in range(10)]
lot = self.lot(spots)
barrier = threading.Barrier(8)
tickets = []
def gate(g):
barrier.wait()
for c in range(5):
t = lot.enter(Vehicle(f"G{g}-{c}", VehicleType.CAR), "north")
if t:
tickets.append(t)
threads = [threading.Thread(target=gate, args=(g,)) for g in range(8)]
[t.start() for t in threads]
[t.join() for t in threads]
self.assertEqual(len(tickets), 10)
self.assertEqual(len({t.spot.id for t in tickets}), 10) # ten distinct spots
if __name__ == "__main__":
unittest.main()
Testing Strategy
| Test Type | What to Test |
|---|---|
| Unit | canFit() — motorcycle fits all spots, car fits medium/large, truck only large |
| Unit | HourlyPricing.calculate() — 0 hours, 1 hour, partial hours round up |
| Unit | ParkingSpot.park() throws when occupied |
| Integration | Full enter → park → calculate fee → exit → spot freed |
| Edge case | Lot full returns null |
| Edge case | Same vehicle can't park twice |
| Concurrency | 100 threads entering simultaneously — no double-booked spots |
// Example test
describe('ParkingLot', () => {
it('should assign smallest fitting spot', () => {
const floor = new ParkingFloor(1);
floor.addSpot(new ParkingSpot('S1', SpotType.SMALL, 1));
floor.addSpot(new ParkingSpot('M1', SpotType.MEDIUM, 1));
floor.addSpot(new ParkingSpot('L1', SpotType.LARGE, 1));
const car = new Car('ABC-123');
const spot = floor.assignSpot(car);
expect(spot?.type).toBe(SpotType.MEDIUM); // not LARGE
});
it('should return null when full', () => {
const floor = new ParkingFloor(1);
floor.addSpot(new ParkingSpot('S1', SpotType.SMALL, 1));
const car = new Car('ABC-123');
floor.assignSpot(car); // takes the only spot (won't fit — small)
expect(floor.assignSpot(new Car('DEF-456'))).toBeNull();
});
});
Correction (2026-11-10): the "should return null when full" test doesn't test fullness
The second sample test puts a car on a floor whose only spot is SMALL. The car never fits, so the floor is never full and the test passes for the wrong reason. Add a MEDIUM spot, park one car, then assert that the second car gets null.
10. Common mistakes
- "Use a
ConcurrentHashMap" as the whole concurrency answer. The invariant spans a check and a write, so it needs a compare-and-set or a lock around both. See Common LLD Mistakes. - Allocation logic in
SpotorFloor. The rule ranks spots across the whole lot. - A strategy that claims the spot, so every new strategy must get locking right again.
doublefor money, orDate.now()inside pricing. Boundary tests become flaky or impossible.- No single-use ticket. Retries happen, and a double exit corrupts occupancy.
- Forgetting the failure path in
enter. A plate reserved and never released can't enter again.
11. Interview follow-ups
How would you make spot lookup O(1)?
Keep a concurrent free-list per size. enter polls the smallest fitting list and falls back to larger ones, and exit pushes the spot back. poll() is atomic, so the CAS becomes a safety check. You lose arbitrary rankings such as nearest to gate, so for most lots the O(n) scan is the better trade.
Two cars get the same spot in production anyway. Where do you look?
At anything that writes occupancy without going through tryOccupy: an admin "force free" tool, a sensor reconciliation job, or a restart from a stale snapshot. Then at the release path: would a stale exit free a re-occupied spot? Enforce the invariant in one method and route everything through it.
What changes if the lot state lives in a database and there are several servers?
The compare-and-set moves into the database: UPDATE spot SET plate = ? WHERE id = ? AND plate IS NULL, and check that one row changed. The plate rule becomes a unique index on plate among open tickets. Single-use tickets become UPDATE ticket SET closed_at = ? WHERE id = ? AND closed_at IS NULL. Only the place where the atomic step runs changes. Booking and Inventory Concurrency covers the database side.
How do you handle a lost ticket?
Look up the plate in ticketByPlate, which already exists for the "inside once" rule, and add exitByPlate(plate) that reuses exit.
How do you pick between best fit and nearest to gate?
Ask what the business is short of. Vans turned away means best fit. Complaints about walking means nearest to gate. Both are strategies, so the lot can switch at runtime, say to best fit above 80% full.