codefarm
06-lld-interview-problems
Guides06-lld-interview-problems

Design a Parking Lot

A full low-level design for a multi-floor parking lot: spot assignment strategy, fee calculation, entry/exit gates, and the concurrency bugs that show up when two cars race for the same spot.

August 11, 2026
lldparking-lotstrategy-patternfee-calculationconcurrency

Design a Parking Lot

Parking Lot is the "hello world" of LLD interviews — not because it's trivial, but because it cleanly exercises every skill the interviewer wants to see: modeling a physical hierarchy (lot → floor → spot), picking the right allocation strategy, handling a pricing policy that varies by input, and reasoning about concurrency without over-engineering. This guide works the problem end-to-end using the same six-step framework used throughout this phase: requirements → actors → class diagram → class design → patterns → algorithms/concurrency → trade-offs.

1. Requirements

Functional requirements

  • The lot has multiple floors; each floor has a fixed number of parking spots.
  • Spots come in types: Compact, Medium, Large, Handicapped (and optionally Motorcycle/Electric with charging).
  • A vehicle entering the lot is assigned a spot compatible with its size, and issues a parking ticket recording entry time and spot.
  • A vehicle exiting the lot pays a fee computed from time parked and vehicle type, then the spot is released.
  • A display board (per floor and lot-wide) shows the count of free spots by type in near real time.
  • The system must reject entry (or queue) when the lot — or the required spot type — is full.

Non-functional requirements

  • Concurrency-safe: two vehicles must never be assigned the same physical spot.
  • Extensible pricing: hourly flat rate today, but the design should absorb "first hour free," "weekend surcharge," or "EV charging fee" without rewriting the core.
  • Extensible spot-assignment: "nearest to entrance" today, "load balance across floors" tomorrow — swappable without touching ParkingLot.
  • Reasonably low latency on entry/exit (spot lookup should not be a full table scan under load).

Out of scope (state this explicitly in an interview): reservations ahead of time, automated license-plate recognition, and multi-lot federation across a city.

✅

Always spend the first two minutes of the interview narrowing scope out loud. "I'll assume single lot, no pre-booking, cash/card payment abstracted behind an interface" turns a 45-minute open-ended problem into something you can finish.

2. Actors & Use Cases

ActorDescription
DriverOwns a vehicle, drives in/out of the lot.
Entry Gate Operator (system, kiosk, or automated barrier)Issues a ticket and directs the driver to an assigned spot.
Exit Gate OperatorComputes the fee, accepts payment, raises the barrier.
Lot AdministratorConfigures floors, spot counts, and pricing rules.

Primary use cases

  1. Park a vehicle — driver arrives → entry gate finds a compatible free spot → ticket issued → spot marked occupied → display board decremented.
  2. Exit a vehicle — driver presents ticket at exit gate → fee calculated from (exitTime - entryTime) and vehicle type → payment processed → spot released → display board incremented.
  3. Check availability — display board (or an API) reports free-spot counts per type, per floor.
  4. Handle full lot — entry gate has no compatible spot → reject entry (or redirect to another floor/lot).

3. Class Diagram

4. Core Class Design

Enums and Vehicle

java
enum VehicleType { MOTORCYCLE, CAR, TRUCK, ELECTRIC }
enum SpotType { COMPACT, MEDIUM, LARGE, HANDICAPPED, ELECTRIC_CHARGING }
 
final class Vehicle {
    private final String licensePlate;
    private final VehicleType type;
 
    Vehicle(String licensePlate, VehicleType type) {
        this.licensePlate = licensePlate;
        this.type = type;
    }
 
    String getLicensePlate() { return licensePlate; }
    VehicleType getType() { return type; }
}

ParkingSpot — the concurrency-critical class

java
class ParkingSpot {
    private final String id;
    private final SpotType type;
    private final int floorNumber;
    private final AtomicReference<Vehicle> currentVehicle = new AtomicReference<>(null);
 
    ParkingSpot(String id, SpotType type, int floorNumber) {
        this.id = id;
        this.type = type;
        this.floorNumber = floorNumber;
    }
 
    /** Atomically claims the spot. Returns false if another thread got here first. */
    boolean tryOccupy(Vehicle vehicle) {
        return currentVehicle.compareAndSet(null, vehicle);
    }
 
    void release() {
        currentVehicle.set(null);
    }
 
    boolean isAvailable() { return currentVehicle.get() == null; }
    SpotType getType() { return type; }
    String getId() { return id; }
    int getFloorNumber() { return floorNumber; }
}

Vehicle-to-spot compatibility

java
final class SpotCompatibility {
    // A vehicle can use its natural spot type, or any larger spot (never smaller).
    private static final Map<VehicleType, List<SpotType>> COMPATIBLE = Map.of(
        VehicleType.MOTORCYCLE, List.of(SpotType.COMPACT, SpotType.MEDIUM, SpotType.LARGE),
        VehicleType.CAR,        List.of(SpotType.MEDIUM, SpotType.LARGE),
        VehicleType.TRUCK,      List.of(SpotType.LARGE),
        VehicleType.ELECTRIC,   List.of(SpotType.ELECTRIC_CHARGING, SpotType.MEDIUM, SpotType.LARGE)
    );
 
    static List<SpotType> acceptableSpotTypes(VehicleType vehicleType) {
        return COMPATIBLE.getOrDefault(vehicleType, List.of());
    }
}

Floor

java
class Floor {
    private final int floorNumber;
    private final List<ParkingSpot> spots;
    // Index for O(1) filtering by type instead of scanning all spots on every lookup.
    private final Map<SpotType, List<ParkingSpot>> spotsByType;
 
    Floor(int floorNumber, List<ParkingSpot> spots) {
        this.floorNumber = floorNumber;
        this.spots = spots;
        this.spotsByType = spots.stream().collect(Collectors.groupingBy(ParkingSpot::getType));
    }
 
    Optional<ParkingSpot> findAvailableSpot(VehicleType vehicleType) {
        for (SpotType candidateType : SpotCompatibility.acceptableSpotTypes(vehicleType)) {
            for (ParkingSpot spot : spotsByType.getOrDefault(candidateType, List.of())) {
                if (spot.isAvailable()) {
                    return Optional.of(spot); // caller claims it atomically via tryOccupy
                }
            }
        }
        return Optional.empty();
    }
 
    int countAvailable(SpotType type) {
        return (int) spotsByType.getOrDefault(type, List.of()).stream()
                .filter(ParkingSpot::isAvailable).count();
    }
 
    int getFloorNumber() { return floorNumber; }
}

ParkingTicket, Receipt

java
final class ParkingTicket {
    private final String ticketId;
    private final String spotId;
    private final Vehicle vehicle;
    private final LocalDateTime entryTime;
 
    ParkingTicket(String ticketId, String spotId, Vehicle vehicle, LocalDateTime entryTime) {
        this.ticketId = ticketId;
        this.spotId = spotId;
        this.vehicle = vehicle;
        this.entryTime = entryTime;
    }
 
    String getTicketId() { return ticketId; }
    String getSpotId() { return spotId; }
    Vehicle getVehicle() { return vehicle; }
    LocalDateTime getEntryTime() { return entryTime; }
}
 
final class Receipt {
    final String ticketId;
    final double amount;
    final LocalDateTime exitTime;
 
    Receipt(String ticketId, double amount, LocalDateTime exitTime) {
        this.ticketId = ticketId;
        this.amount = amount;
        this.exitTime = exitTime;
    }
}

FeeCalculator strategy

java
interface FeeCalculator {
    double calculate(ParkingTicket ticket, LocalDateTime exitTime, VehicleType type);
}
 
class HourlyFeeCalculator implements FeeCalculator {
    private final Map<VehicleType, Double> ratePerHour;
 
    HourlyFeeCalculator(Map<VehicleType, Double> ratePerHour) {
        this.ratePerHour = ratePerHour;
    }
 
    public double calculate(ParkingTicket ticket, LocalDateTime exitTime, VehicleType type) {
        long minutes = Duration.between(ticket.getEntryTime(), exitTime).toMinutes();
        long billableHours = Math.max(1, (long) Math.ceil(minutes / 60.0)); // round up, 1hr minimum
        return billableHours * ratePerHour.getOrDefault(type, 0.0);
    }
}
 
// Extension example: first 30 minutes free — added WITHOUT touching HourlyFeeCalculator (OCP).
class GracePeriodFeeCalculator implements FeeCalculator {
    private final FeeCalculator delegate;
    private final int graceMinutes;
 
    GracePeriodFeeCalculator(FeeCalculator delegate, int graceMinutes) {
        this.delegate = delegate;
        this.graceMinutes = graceMinutes;
    }
 
    public double calculate(ParkingTicket ticket, LocalDateTime exitTime, VehicleType type) {
        long minutes = Duration.between(ticket.getEntryTime(), exitTime).toMinutes();
        if (minutes <= graceMinutes) return 0.0;
        return delegate.calculate(ticket, exitTime, type);
    }
}

Spot assignment strategy

java
interface SpotAssignmentStrategy {
    Optional<ParkingSpot> assign(List<Floor> floors, Vehicle vehicle);
}
 
/** Scans floors in order (ground floor first) — proxy for "nearest to entrance." */
class NearestToEntranceStrategy implements SpotAssignmentStrategy {
    public Optional<ParkingSpot> assign(List<Floor> floors, Vehicle vehicle) {
        for (Floor floor : floors) { // floors pre-sorted by proximity to entrance
            Optional<ParkingSpot> spot = floor.findAvailableSpot(vehicle.getType());
            if (spot.isPresent()) return spot;
        }
        return Optional.empty();
    }
}
 
/** Load-balances across floors instead of always filling the ground floor first. */
class LeastOccupiedFloorStrategy implements SpotAssignmentStrategy {
    public Optional<ParkingSpot> assign(List<Floor> floors, Vehicle vehicle) {
        return floors.stream()
                .sorted(Comparator.comparingInt(f -> -f.countAvailable(SpotType.MEDIUM)))
                .map(f -> f.findAvailableSpot(vehicle.getType()))
                .filter(Optional::isPresent)
                .map(Optional::get)
                .findFirst();
    }
}

ParkingLot — the orchestrator

java
class ParkingLot {
    private final List<Floor> floors;
    private final SpotAssignmentStrategy assignmentStrategy;
    private final FeeCalculator feeCalculator;
    private final DisplayBoard displayBoard;
    private final ConcurrentHashMap<String, ParkingTicket> activeTickets = new ConcurrentHashMap<>();
 
    ParkingLot(List<Floor> floors, SpotAssignmentStrategy assignmentStrategy,
               FeeCalculator feeCalculator, DisplayBoard displayBoard) {
        this.floors = floors;
        this.assignmentStrategy = assignmentStrategy;
        this.feeCalculator = feeCalculator;
        this.displayBoard = displayBoard;
    }
 
    ParkingTicket parkVehicle(Vehicle vehicle) {
        Optional<ParkingSpot> spot = assignmentStrategy.assign(floors, vehicle);
        if (spot.isEmpty()) {
            throw new LotFullException("No compatible spot for " + vehicle.getType());
        }
        // tryOccupy is the atomic compare-and-set that resolves the entry race (see §6).
        if (!spot.get().tryOccupy(vehicle)) {
            // Lost the race to another thread between "find" and "occupy" — retry once.
            return parkVehicle(vehicle);
        }
        ParkingTicket ticket = new ParkingTicket(
                UUID.randomUUID().toString(), spot.get().getId(), vehicle, LocalDateTime.now());
        activeTickets.put(ticket.getTicketId(), ticket);
        displayBoard.update(spot.get().getType(), -1);
        return ticket;
    }
 
    Receipt unparkVehicle(String ticketId) {
        ParkingTicket ticket = activeTickets.remove(ticketId);
        if (ticket == null) throw new InvalidTicketException(ticketId);
 
        LocalDateTime exitTime = LocalDateTime.now();
        double amount = feeCalculator.calculate(ticket, exitTime, ticket.getVehicle().getType());
 
        ParkingSpot spot = findSpotById(ticket.getSpotId());
        spot.release();
        displayBoard.update(spot.getType(), +1);
 
        return new Receipt(ticketId, amount, exitTime);
    }
 
    private ParkingSpot findSpotById(String spotId) { /* O(1) index lookup, built at construction */ return null; }
}
⚠️

findSpotById should be backed by a Map&lt;String, ParkingSpot&gt; built once at construction time — not a linear scan across floors on every exit. At scale this is the difference between O(1) and O(spots) per exit.

5. Design Patterns Applied

PatternWhere usedWhy
StrategySpotAssignmentStrategy, FeeCalculatorAssignment policy and pricing policy both vary independently and need to be swapped without touching ParkingLot — textbook OCP via Strategy.
DecoratorGracePeriodFeeCalculator wrapping HourlyFeeCalculatorLayers a "first N minutes free" rule on top of any base calculator without subclassing or modifying it.
Factory MethodParkingLotFactory.createLot(config) (not shown above, but standard)Encapsulates the multi-step construction of floors + spots from a configuration object.
Observer (optional extension)DisplayBoard subscribing to spot occupy/release eventsDecouples "a spot changed state" from "who needs to know" — lets you add a mobile-app push notifier later without touching ParkingSpot.
Singleton (careful use)ParkingLot instance itself, if the app manages exactly one lotCommon in textbook solutions; in a real service this is usually just a Spring-managed bean, not a hand-rolled Singleton.

6. Key Algorithms, Concurrency & Edge Cases

The core race: two cars, one spot

The dangerous window is between finding a candidate spot and claiming it. If findAvailableSpot returns a spot and a second thread claims it before the first thread marks it occupied, both drivers get directed to spot A-1.

The fix is to never trust a "check" result as still true by the time you "act" — collapse check-and-act into one atomic operation using compareAndSet:

java
// ParkingSpot.tryOccupy — the linearization point for spot assignment.
boolean tryOccupy(Vehicle vehicle) {
    return currentVehicle.compareAndSet(null, vehicle); // atomic: fails if already occupied
}

ParkingLot.parkVehicle then treats a failed tryOccupy as "someone beat me to it" and retries against the next candidate spot rather than assuming success. This avoids a lot-wide lock — contention is scoped to a single spot, not the whole floor.

🚨

A common bug: checking spot.isAvailable() and then, in a separate step, calling a non-atomic spot.occupy(vehicle). Between those two calls another thread can interleave. Always make "check" and "claim" the same atomic operation — compareAndSet, a synchronized block, or a database row lock (SELECT ... FOR UPDATE) if spots are persisted in a relational store.

Full-lot handling

java
class LotFullException extends RuntimeException {
    LotFullException(String message) { super(message); }
}

Two defensible choices, and an interviewer wants to hear you name both:

  • Throw a checked/unchecked exception — forces the entry gate to handle the "no spot" case explicitly; good when full-lot is an exceptional, rare condition.
  • Return Optional<ParkingTicket> — treats full-lot as an expected, common outcome (e.g., during rush hour); the caller decides whether to redirect to another lot without a try/catch.

Either is acceptable if justified; Optional scales better when "full" is common rather than exceptional.

Exit flow ordering: pay, then release

java
Receipt unparkVehicle(String ticketId) {
    ParkingTicket ticket = activeTickets.remove(ticketId);
    // 1. compute fee based on the CLOSED ticket (immutable entry time)
    // 2. process payment (external call — can fail/retry)
    // 3. only release the spot AFTER payment succeeds
    // ...
}

Releasing the spot before payment confirms would let a second car be assigned that spot while the first car is still physically parked in it (payment kiosk jam, card decline, retry). The spot should only flip back to available once payment is confirmed and the driver has actually exited — in a real system this is often gated by a physical sensor or barrier event, not just the payment call returning.

Vehicle-size-to-spot mapping

The SpotCompatibility lookup in §4 encodes the rule "a vehicle may use its own spot size or any larger one, never smaller" — a motorcycle in a compact, medium, or large spot; a truck only in large. This is intentionally a static table, not a chain of if statements, so adding VehicleType.BUS is a one-line map entry.

Other edge cases worth naming out loud

  • Ticket lost/damaged: fall back to license-plate lookup against activeTickets values.
  • Vehicle re-enters on an already-active ticket: reject — a ticket ID must map to exactly one open parking session.
  • Floor taken fully offline for maintenance: Floor needs an active flag so SpotAssignmentStrategy skips it without deleting spot records.
  • Clock skew / negative duration: guard FeeCalculator against exitTime earlier than entryTime (NTP hiccup, testing artifact) by clamping to zero.

7. Trade-offs & Extensions

DecisionTrade-off
In-memory ConcurrentHashMap for spots/ticketsSimple and fast for a single-process demo; a real deployment needs the "one spot, one vehicle" invariant enforced at the database layer (unique constraint or row lock) since multiple app instances share state.
compareAndSet per-spot lockingScales far better than a lot-wide synchronized block, but pushes complexity into retry logic on contention.
Nearest-to-entrance vs. load-balanced assignmentNearest-to-entrance is driver-friendly but clusters wear on ground-floor spots and can strand upper floors as "always empty, always far."
Static spot-to-vehicle compatibility tableCheap to reason about and test; doesn't handle dynamic constraints (e.g., "trucks banned from floor 3 due to a low ceiling beam on one section only") without extending the model.

Natural extensions an interviewer may probe:

  • Reservations: pre-book a spot for a future time window — requires a Reservation entity and changes findAvailableSpot to also check reservation overlap, not just current occupancy.
  • Dynamic pricing: surge pricing when the lot is >90% full — swap in a SurgeFeeCalculator decorator, no core changes (same Decorator seam as the grace-period example).
  • Multi-lot search: a ParkingLotAggregator that queries several ParkingLot instances and routes drivers — composition over inheritance, ParkingLot stays unaware it's one of many.
  • EV charging billing: spots of type ELECTRIC_CHARGING bill by kWh delivered in addition to time — a second FeeCalculator implementation, composed via the same Strategy seam.

Interview Questions

  • Where exactly is the race condition when two cars are directed to the same spot, and how does compareAndSet eliminate it without a lot-wide lock?
  • Why compute the fee before releasing the spot on exit, rather than the other way around?
  • How would you extend the fee calculator to support "first 30 minutes free" without modifying HourlyFeeCalculator? Name the pattern.
  • What's the trade-off between throwing LotFullException and returning Optional<ParkingTicket> when the lot is full?
  • How would spot assignment change if you wanted to load-balance across floors instead of always filling the entrance floor first?
  • If spot and ticket state moved from an in-memory map to a relational database shared by multiple app servers, what changes to guarantee the "one spot, one vehicle" invariant?
  • How would you extend this design to support reservations made ahead of arrival time?
Previous

UML Diagrams for LLD Interviews

Next

Design an Elevator System