40 — LLD: Parking Lot

Frequently Asked at Salesforce — Reported repeatedly in SMTS technical rounds (2024-2026).

Understanding the Problem

A parking lot system manages multiple floors and many spots of varying sizes, lets vehicles of different classes enter, assigns an appropriate spot, issues a ticket, and charges on exit based on how long the vehicle stayed.

What is a Parking Lot system?

Think of it as a hotel check-in desk crossed with a vending machine — vehicles are matched to spots that can fit them, each stay has a receipt, and the whole thing must survive many concurrent arrivals at multiple gates.

---

Requirements

Clarifying Questions

You: Do we need to support reservations, or is it walk-in only?

Interviewer: Walk-in only for v1.

Scoped: no booking API, no held-spot concept.

You: Do spot sizes map one-to-one with vehicle types, or can a car take a truck spot?

Interviewer: A bigger spot can fit a smaller vehicle, but not the other way around.

Size is a dominance relationship — drives the allocation loop.

You: Is pricing time-based flat or slab-based?

Interviewer: Hourly slab — first hour flat, then per-hour.

Pricing must be pluggable; interviewer likely probes other policies later.

You: Multi-threaded? Many entry gates concurrently?

Interviewer: Yes, assume concurrent parks.

Thread-safety is in scope — this is the core Salesforce probe.

You: In-memory or persisted?

Interviewer: In-memory, but design so storage can be swapped.

Repository interface so persistence becomes a strategy later.

You: Do we need a display board showing free counts per floor?

Interviewer: Yes, and it should update live.

Observer pattern for display boards subscribing to spot changes.

Final Requirements

1. Multiple floors, each with a configurable mix of Small, Medium, and Large spots.
2. Park a vehicle — allocate the smallest fitting spot and return a ticket.
3. Unpark with a ticket — release the spot and compute fee.
4. Pluggable spot allocation strategy (nearest, fill-by-floor).
5. Pluggable pricing strategy (slab hourly).
6. Live display boards observe spot availability per floor.
7. Thread-safe park / unpark under concurrent gate access.

Out of scope: reservations, payment provider integration, physical hardware, tenant isolation across multiple sites.

---

Core Entities and Relationships

Entity	Responsibility
VehicleType / SpotSize	Enums. Ordered so bigger can fit smaller.
Vehicle	License plate and required size.
ParkingSpot	Knows its size, floor, and current ticket.
Floor	Aggregates spots. Tracks free counts. Publishes events.
Ticket	Issued on entry. Binds vehicle to spot with entry time.
SpotAllocationStrategy	Pluggable policy picking the next free spot.
PricingStrategy	Pluggable policy computing fee from duration.
DisplayBoard	Observer of floor-level spot events.
ParkingLot	Aggregate root. Owns floors, strategies, tickets.

Why does Ticket deserve its own class? Because the relationship between a vehicle and a spot only exists while it is parked, and it carries temporal state (entry time) that belongs neither to Vehicle nor ParkingSpot.

Why not put allocation inside Floor? A single floor cannot know the site-wide preference order. That is what a strategy injected into ParkingLot is for.

Design is iterative — start with these entities and add only when a requirement forces it.

---

Class Design

ParkingSpot

State:

• id: string
• floorNumber: int
• size: SpotSize
• ticket: Ticket | null

Methods:

• isFree(), canFit(vehicle)
• assign(ticket), release()

Floor

State:

• number: int
• spots: ParkingSpot[]
• observers: Set<SpotObserver>

Methods:

• freeCount(size)
• findFirstFreeSpot(vehicle)
• subscribe(observer), emit(event)

ParkingLot

State:

• floors: Floor[]
• allocation: SpotAllocationStrategy
• pricing: PricingStrategy
• tickets: Map<string, Ticket>

Methods:

• park(vehicle) -> Ticket
• unpark(ticketId, now) -> fee

Design principles at play:

• Single Responsibility — Spot, Floor, Lot, Strategy, Display each own one concern.
• Open/Closed — adding EV-charging spots or monthly-pass pricing does not touch existing classes.
• Dependency Inversion — ParkingLot depends on strategy interfaces, not concrete classes.
• Strategy Pattern — SpotAllocationStrategy and PricingStrategy are pluggable.
• Observer Pattern — display boards subscribe to Floor events.
• Singleton — one ParkingLot per physical site.

---

Implementation

Core Logic: Spot Allocation

You want the smallest spot the vehicle fits, chosen per the current strategy (nearest-to-entrance by default).

Bad approach: random free spot.

• Wastes large spots on bikes; lot fills prematurely.

Good approach: iterate floors, scan spots linearly.

• Simple, O(n) per park. Fine for a few hundred spots.

Great approach: pre-bucket free spots per floor per size (like Amazon Locker) for O(1) allocation.

• Trades memory for speed; worth it at high concurrency.

Verification

Floors F0 (S1, S2, M1), F1 (L1). Nearest-to-entrance strategy.

1. Motorcycle arrives → park finds S1 on F0 → ticket T1 issued, F0 emits TAKEN → display shows F0 small=1, medium=1.
2. Car arrives → park scans F0, needs medium, finds M1 → ticket T2, F0 emits TAKEN → display updates.
3. Truck arrives → park scans F0 (no large), falls to F1 → L1 allocated.
4. T1 unpark after 70 minutes → slab pricing: motorcycle base 10, plus ceil(70/60)=2h so 10 + 1100.8 = 18. Spot released; F0 emits FREED.
5. Concurrent park on S2 from two gates → without a lock both threads see S2 free and call assign; second call throws. With CAS tryAssign, the loser retries and picks a different spot.

Thread Safety

• park has a find-then-assign race. Options:
  • Global lock — simplest, but serialises every gate.
  • Per-floor lock — good because parking is floor-local.
  • CAS on ParkingSpot.tryAssign(ticket) using AtomicReference<Ticket> — strategy returns a candidate, assignment may fail and retry. Best throughput.
• tickets map must be a ConcurrentHashMap.
• Observer callbacks should run outside the lock to avoid priority inversion and slow subscribers blocking allocation.

Complete Code Implementation

Java

import java.util.*;
import java.util.concurrent.*;
import java.util.concurrent.atomic.AtomicReference;

enum VehicleType { MOTORCYCLE, CAR, TRUCK }
enum SpotSize {
    SMALL(1), MEDIUM(2), LARGE(3);
    public final int rank;
    SpotSize(int r) { this.rank = r; }
}

class Vehicle {
    public final String licensePlate;
    public final VehicleType type;
    public final SpotSize requiredSize;
    public Vehicle(String lp, VehicleType t, SpotSize rs) {
        this.licensePlate = lp; this.type = t; this.requiredSize = rs;
    }
}

class Ticket {
    public final String id;
    public final Vehicle vehicle;
    public final ParkingSpot spot;
    public final long entryTime;
    public Ticket(String id, Vehicle v, ParkingSpot s) {
        this.id = id; this.vehicle = v; this.spot = s;
        this.entryTime = System.currentTimeMillis();
    }
}

class ParkingSpot {
    public final String id;
    public final int floorNumber;
    public final SpotSize size;
    private final AtomicReference<Ticket> ticket = new AtomicReference<>(null);

    public ParkingSpot(String id, int f, SpotSize s) {
        this.id = id; this.floorNumber = f; this.size = s;
    }
    public boolean isFree() { return ticket.get() == null; }
    public boolean canFit(Vehicle v) { return size.rank >= v.requiredSize.rank; }
    public boolean tryAssign(Ticket t) { return ticket.compareAndSet(null, t); }
    public void release() { ticket.set(null); }
}

interface SpotObserver { void onChange(String kind, int floor, SpotSize size); }

class Floor {
    public final int number;
    private final List<ParkingSpot> spots;
    private final Set<SpotObserver> observers = ConcurrentHashMap.newKeySet();

    public Floor(int n, List<ParkingSpot> s) { this.number = n; this.spots = s; }

    public ParkingSpot findFirstFreeSpot(Vehicle v) {
        for (ParkingSpot s : spots) if (s.isFree() && s.canFit(v)) return s;
        return null;
    }
    public int freeCount(SpotSize min) {
        int c = 0;
        for (ParkingSpot s : spots) if (s.isFree() && s.size.rank >= min.rank) c++;
        return c;
    }
    public void subscribe(SpotObserver o) { observers.add(o); }
    public void emit(String kind, SpotSize size) {
        for (SpotObserver o : observers) {
            try { o.onChange(kind, number, size); } catch (Exception ignored) {}
        }
    }
}

interface SpotAllocationStrategy { ParkingSpot findSpot(List<Floor> floors, Vehicle v); }

class NearestToEntranceStrategy implements SpotAllocationStrategy {
    public ParkingSpot findSpot(List<Floor> floors, Vehicle v) {
        for (Floor f : floors) {
            ParkingSpot s = f.findFirstFreeSpot(v);
            if (s != null) return s;
        }
        return null;
    }
}

interface PricingStrategy { double priceFor(VehicleType t, long minutes); }

class SlabHourlyPricing implements PricingStrategy {
    public double priceFor(VehicleType t, long minutes) {
        double base = switch (t) { case MOTORCYCLE -> 10; case CAR -> 20; case TRUCK -> 40; };
        long hours = (minutes + 59) / 60;
        return base + Math.max(0, hours - 1) * base * 0.8;
    }
}

class ParkingLot {
    private static volatile ParkingLot instance;
    private final List<Floor> floors;
    private final SpotAllocationStrategy allocation;
    private final PricingStrategy pricing;
    private final ConcurrentHashMap<String, Ticket> tickets = new ConcurrentHashMap<>();

    private ParkingLot(List<Floor> f, SpotAllocationStrategy a, PricingStrategy p) {
        this.floors = f; this.allocation = a; this.pricing = p;
    }
    public static ParkingLot init(List<Floor> f, SpotAllocationStrategy a, PricingStrategy p) {
        if (instance == null) {
            synchronized (ParkingLot.class) {
                if (instance == null) instance = new ParkingLot(f, a, p);
            }
        }
        return instance;
    }
    public static ParkingLot get() { return instance; }

    public Ticket park(Vehicle v) {
        // CAS retry loop — allocation may race with other gates
        while (true) {
            ParkingSpot spot = allocation.findSpot(floors, v);
            if (spot == null) throw new RuntimeException("LOT_FULL");
            Ticket t = new Ticket(UUID.randomUUID().toString(), v, spot);
            if (spot.tryAssign(t)) {
                tickets.put(t.id, t);
                floors.get(spot.floorNumber).emit("TAKEN", spot.size);
                return t;
            }
        }
    }

    public double unpark(String ticketId) {
        Ticket t = tickets.remove(ticketId);
        if (t == null) throw new RuntimeException("TICKET_NOT_FOUND");
        long mins = Math.max(1, (System.currentTimeMillis() - t.entryTime) / 60000);
        double fee = pricing.priceFor(t.vehicle.type, mins);
        t.spot.release();
        floors.get(t.spot.floorNumber).emit("FREED", t.spot.size);
        return fee;
    }
}

C++

#include <atomic>
#include <chrono>
#include <memory>
#include <mutex>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <vector>

enum class VehicleType { Motorcycle, Car, Truck };
enum class SpotSize { Small = 1, Medium = 2, Large = 3 };

struct Vehicle {
    std::string licensePlate;
    VehicleType type;
    SpotSize requiredSize;
};

class ParkingSpot;
struct Ticket {
    std::string id;
    Vehicle vehicle;
    ParkingSpot* spot;
    long long entryTime;
};

class ParkingSpot {
public:
    std::string id;
    int floorNumber;
    SpotSize size;
    ParkingSpot(std::string i, int f, SpotSize s) : id(std::move(i)), floorNumber(f), size(s), ticket(nullptr) {}
    bool isFree() const { return ticket.load() == nullptr; }
    bool canFit(const Vehicle& v) const { return static_cast<int>(size) >= static_cast<int>(v.requiredSize); }
    bool tryAssign(Ticket* t) { Ticket* expected = nullptr; return ticket.compare_exchange_strong(expected, t); }
    void release() { ticket.store(nullptr); }
private:
    std::atomic<Ticket*> ticket;
};

struct SpotObserver { virtual void onChange(const std::string& kind, int floor, SpotSize sz) = 0; };

class Floor {
public:
    int number;
    std::vector<std::shared_ptr<ParkingSpot>> spots;
    Floor(int n, std::vector<std::shared_ptr<ParkingSpot>> s) : number(n), spots(std::move(s)) {}

    std::shared_ptr<ParkingSpot> findFirstFreeSpot(const Vehicle& v) {
        for (auto& s : spots) if (s->isFree() && s->canFit(v)) return s;
        return nullptr;
    }
    void subscribe(SpotObserver* o) { std::lock_guard<std::mutex> g(obsMu); observers.insert(o); }
    void emit(const std::string& kind, SpotSize sz) {
        std::unordered_set<SpotObserver*> snap;
        { std::lock_guard<std::mutex> g(obsMu); snap = observers; }
        for (auto* o : snap) { try { o->onChange(kind, number, sz); } catch (...) {} }
    }
private:
    std::unordered_set<SpotObserver*> observers;
    std::mutex obsMu;
};

struct SpotAllocationStrategy {
    virtual std::shared_ptr<ParkingSpot> findSpot(std::vector<std::shared_ptr<Floor>>& floors, const Vehicle& v) = 0;
};

class NearestToEntranceStrategy : public SpotAllocationStrategy {
public:
    std::shared_ptr<ParkingSpot> findSpot(std::vector<std::shared_ptr<Floor>>& floors, const Vehicle& v) override {
        for (auto& f : floors) if (auto s = f->findFirstFreeSpot(v)) return s;
        return nullptr;
    }
};

struct PricingStrategy { virtual double priceFor(VehicleType t, long long minutes) = 0; };

class ParkingLot {
public:
    ParkingLot(std::vector<std::shared_ptr<Floor>> f, std::shared_ptr<SpotAllocationStrategy> a, std::shared_ptr<PricingStrategy> p)
        : floors(std::move(f)), allocation(std::move(a)), pricing(std::move(p)) {}

    std::shared_ptr<Ticket> park(const Vehicle& v) {
        while (true) {
            auto spot = allocation->findSpot(floors, v);
            if (!spot) throw std::runtime_error("LOT_FULL");
            auto t = std::make_shared<Ticket>();
            t->id = std::to_string(std::chrono::steady_clock::now().time_since_epoch().count());
            t->vehicle = v; t->spot = spot.get();
            t->entryTime = std::chrono::system_clock::now().time_since_epoch().count() / 1'000'000;
            if (spot->tryAssign(t.get())) {
                std::lock_guard<std::mutex> g(mu);
                tickets[t->id] = t;
                floors[spot->floorNumber]->emit("TAKEN", spot->size);
                return t;
            }
        }
    }

    double unpark(const std::string& id) {
        std::shared_ptr<Ticket> t;
        { std::lock_guard<std::mutex> g(mu);
          auto it = tickets.find(id);
          if (it == tickets.end()) throw std::runtime_error("TICKET_NOT_FOUND");
          t = it->second; tickets.erase(it); }
        long long now = std::chrono::system_clock::now().time_since_epoch().count() / 1'000'000;
        long long mins = std::max(1LL, (now - t->entryTime) / 60000);
        double fee = pricing->priceFor(t->vehicle.type, mins);
        t->spot->release();
        floors[t->spot->floorNumber]->emit("FREED", t->spot->size);
        return fee;
    }

private:
    std::vector<std::shared_ptr<Floor>> floors;
    std::shared_ptr<SpotAllocationStrategy> allocation;
    std::shared_ptr<PricingStrategy> pricing;
    std::unordered_map<std::string, std::shared_ptr<Ticket>> tickets;
    std::mutex mu;
};

TypeScript

enum VehicleType { Motorcycle = "MOTORCYCLE", Car = "CAR", Truck = "TRUCK" }
enum SpotSize { Small = 1, Medium = 2, Large = 3 }

interface Vehicle {
  readonly licensePlate: string;
  readonly type: VehicleType;
  readonly requiredSize: SpotSize;
}

class ParkingSpot {
  private _ticket: Ticket | null = null;
  constructor(
    public readonly id: string,
    public readonly floorNumber: number,
    public readonly size: SpotSize,
  ) {}
  isFree(): boolean { return this._ticket === null; }
  canFit(vehicle: Vehicle): boolean { return this.size >= vehicle.requiredSize; }
  assign(ticket: Ticket): void {
    if (!this.isFree()) throw new Error(`Spot ${this.id} not free`);
    this._ticket = ticket;
  }
  release(): void { this._ticket = null; }
}

interface SpotAllocationStrategy {
  findSpot(floors: Floor[], vehicle: Vehicle): ParkingSpot | null;
}

class NearestToEntranceStrategy implements SpotAllocationStrategy {
  findSpot(floors: Floor[], vehicle: Vehicle): ParkingSpot | null {
    for (const floor of floors) {
      const spot = floor.findFirstFreeSpot(vehicle);
      if (spot) return spot;
    }
    return null;
  }
}

class FillByFloorStrategy implements SpotAllocationStrategy {
  findSpot(floors: Floor[], vehicle: Vehicle): ParkingSpot | null {
    return floors
      .map((f) => ({ f, free: f.freeCount(vehicle.requiredSize) }))
      .filter((x) => x.free > 0)
      .sort((a, b) => a.f.number - b.f.number)[0]?.f.findFirstFreeSpot(vehicle) ?? null;
  }
}

interface PricingStrategy { priceFor(vehicleType: VehicleType, minutes: number): number; }

class SlabHourlyPricing implements PricingStrategy {
  priceFor(type: VehicleType, minutes: number): number {
    const base = { MOTORCYCLE: 10, CAR: 20, TRUCK: 40 }[type];
    const hours = Math.ceil(minutes / 60);
    return base + Math.max(0, hours - 1) * base * 0.8;
  }
}

type SpotEvent = { kind: "FREED" | "TAKEN"; floor: number; size: SpotSize };
interface SpotObserver { onChange(event: SpotEvent): void; }

class Floor {
  private observers = new Set<SpotObserver>();
  constructor(public readonly number: number, private spots: ParkingSpot[]) {}

  freeCount(size: SpotSize): number {
    return this.spots.filter((s) => s.isFree() && s.size >= size).length;
  }
  findFirstFreeSpot(vehicle: Vehicle): ParkingSpot | null {
    return this.spots.find((s) => s.isFree() && s.canFit(vehicle)) ?? null;
  }
  subscribe(o: SpotObserver) { this.observers.add(o); }
  emit(event: SpotEvent) {
    for (const o of this.observers) {
      try { o.onChange(event); } catch { /* isolated */ }
    }
  }
}

class Ticket {
  constructor(
    public readonly id: string,
    public readonly vehicle: Vehicle,
    public readonly spot: ParkingSpot,
    public readonly entryTime: number = Date.now(),
  ) {}
}

class ParkingLot {
  private static instance: ParkingLot | null = null;
  private tickets = new Map<string, Ticket>();

  private constructor(
    private floors: Floor[],
    private allocation: SpotAllocationStrategy,
    private pricing: PricingStrategy,
  ) {}

  static init(floors: Floor[], allocation: SpotAllocationStrategy, pricing: PricingStrategy) {
    if (this.instance) throw new Error("Already initialised");
    this.instance = new ParkingLot(floors, allocation, pricing);
    return this.instance;
  }
  static get(): ParkingLot {
    if (!this.instance) throw new Error("Call init first");
    return this.instance;
  }

  park(vehicle: Vehicle): Ticket {
    const spot = this.allocation.findSpot(this.floors, vehicle);
    if (!spot) throw new Error("LOT_FULL");
    const ticket = new Ticket(crypto.randomUUID(), vehicle, spot);
    spot.assign(ticket);
    this.tickets.set(ticket.id, ticket);
    this.floors[spot.floorNumber].emit({ kind: "TAKEN", floor: spot.floorNumber, size: spot.size });
    return ticket;
  }

  unpark(ticketId: string, now = Date.now()): number {
    const ticket = this.tickets.get(ticketId);
    if (!ticket) throw new Error("TICKET_NOT_FOUND");
    const minutes = Math.max(1, Math.ceil((now - ticket.entryTime) / 60000));
    const fee = this.pricing.priceFor(ticket.vehicle.type, minutes);
    ticket.spot.release();
    this.tickets.delete(ticketId);
    this.floors[ticket.spot.floorNumber].emit({
      kind: "FREED", floor: ticket.spot.floorNumber, size: ticket.spot.size,
    });
    return fee;
  }
}

---

Extensibility

1. "Add EV charging spots"

You would introduce a SpotFeature enum and add a features: Set<SpotFeature> to ParkingSpot. Vehicle gains requiredFeatures. The allocation strategy interface does not change — you just augment the canFit check.

interface Vehicle {
  readonly requiredFeatures?: Set<SpotFeature>;
}
class ParkingSpot {
  features: Set<SpotFeature> = new Set();
  canFit(v: Vehicle): boolean {
    if (this.size < v.requiredSize) return false;
    if (!v.requiredFeatures) return true;
    for (const f of v.requiredFeatures) if (!this.features.has(f)) return false;
    return true;
  }
}

Tradeoff: A set lookup per spot adds a small constant factor. Alternative: separate sub-pools per feature for O(1) allocation.

2. "Monthly passes"

Composition on the pricing side. PassAwarePricing decorates a base strategy, short-circuiting fee calculation for pass-holding plates. Decorator pattern preserves the base strategy.

class PassAwarePricing implements PricingStrategy {
  constructor(private passes: Set<string>, private inner: PricingStrategy) {}
  priceFor(type: VehicleType, minutes: number, plate?: string): number {
    if (plate && this.passes.has(plate)) return 0;
    return this.inner.priceFor(type, minutes);
  }
}

3. "Multi-site deployment"

Promote ParkingLot from Singleton to a ParkingLotRegistry keyed by site ID. Each lot keeps its own strategies. Shared display board aggregates events across sites.

---

What is Expected at Each Level

Level	Expectations
Mid (IC3)	Solid classes, one allocation strategy, happy path, mentions locks exist.
Senior / SMTS (IC4)	Strategy + Observer patterns named, explicit concurrency story with CAS or per-floor locks, pricing decoupled, extensibility walkthrough, draws class diagram unprompted.
Staff (IC5)	Multi-site, tenancy, backpressure when lot is full, capacity planning, API contract and deployment topology, metrics and observability.