vishal maurya

LLD Series: Parking Lot (Low-Level Design)

Overview

Part of the Interview Prep series. Dotted-underline words are glossary terms: hover for the meaning or open the Glossary. Track your progress on the Interview Prep tracker. Series index: Start here.

1. Problem statement and how it is asked

Typical phrasing: "Design a multi-floor parking lot. Vehicles enter, get a ticket and a spot, and pay on exit. Support different vehicle types and pricing. Write working code in 60 minutes."

  • Asked at: Amex, PayU, Visa (machine-coding rounds), and almost every product company as the "warm-up" LLD. The interviewer is looking for: clean entity modelling, a Strategy for allocation and pricing, correct concurrency on spot allocation, and extensibility (EV spots, new vehicle types, new pricing).
  • Fintech angle: they will push on the pricing/payment part (rounding, money as BigDecimal, idempotent exit, no double charge) and on concurrency (two cars, one spot).

2. Requirements clarification

Functional

  1. Multi-floor lot; each floor has spots of types MOTORCYCLE, COMPACT, LARGE.
  2. Vehicle types: motorcycle, car, truck. A vehicle may use its own spot size or a larger one (bike -> any, car -> compact/large, truck -> large only).
  3. park(vehicle) returns a Ticket (spot, entry time). Fails clearly if the lot is full or the vehicle is already inside.
  4. unpark(ticketId) computes the fee and frees the spot.
  5. Pluggable pricing (hourly by vehicle type, grace period) and pluggable spot-allocation strategy.
  6. Show availability per floor and spot type.

Non-functional

  • Thread-safe: many entry/exit gates in parallel; never hand one spot to two vehicles.
  • Allocation fast (O(log n) not O(n) scan).
  • Testable time (inject Clock).

Assumptions: single lot, in-memory; money in BigDecimal; fee = rate x started hours; payment is out of scope (we return a Receipt; in an interview mention a PaymentService hook).

Out of scope: reservations, EV charging, lost tickets, valet, license plate OCR, multi-lot, persistence.

3. Entities, relationships, class diagram

 +-------------------+ 1      * +-----------+ 1     * +--------------+
 |    ParkingLot     |--------->|   Floor   |-------->| ParkingSpot  |
 | park()/unpark()   |          | claim()   |  (free) | id,type,no   |
 +----+---------+----+          | release() |         +--------------+
      |         |               +-----------+
      |uses     |uses
      v         v
+--------------------+   +-------------------+
|<<iface>>           |   |<<iface>>          |
|SpotAllocationStrat.|   | PricingStrategy   |
+---------^----------+   +---------^---------+
          |                        |
 LowestFloorFirstStrategy   HourlyPricingStrategy

 ParkingLot --creates--> Ticket(id, Vehicle, ParkingSpot, entryTime)
 ParkingLot --returns--> Receipt(ticket, duration, fee)
 Vehicle(plate, VehicleType)   VehicleType --compatibleSpots--> SpotType

Key modelling decision: a spot does not carry an occupied flag. The Floor keeps a concurrent sorted set of free spots per type; being in the set means free. Claiming = pollFirst() which is atomic. That removes check-then-act races and gives "nearest spot first" for free.

4. Design patterns and why

PatternWhereWhy / alternative rejected
StrategySpotAllocationStrategy, PricingStrategyRules change often (peak pricing, nearest-to-lift). Rejected: if/else on vehicle type inside ParkingLot (violates OCP).
FacadeParkingLotOne entry point for gates; hides floors/pricing.
Value objectsTicket, Receipt, Vehicle immutableSafe to share across threads without locks.
Enum with behaviourVehicleType.compatibleSpots()Adding a vehicle type is a one-line enum change; no switch statements.
(Mention only) FactoryVehicleFactory, SpotFactoryOverkill for 3 types; say you would add it if construction became non-trivial.
(Mention only) Observeravailability display boardsAdd a listener list on park/unpark if asked.

Rejected: a Spot subclass per type (CompactSpot, LargeSpot) - they differ only in data, not behaviour, so an enum field is enough (avoid class explosion).

5. Complete Java code

All files are in the default package; compile with javac *.java && java Main. Compiled and run with JDK 11+ syntax (the demo uses List.of, var).

5.1 Enums and models

// VehicleType.java
import java.util.List;

/** Vehicle category. Knows which spot sizes it may use, smallest (cheapest to waste) first. */
public enum VehicleType {
    MOTORCYCLE(List.of(SpotType.MOTORCYCLE, SpotType.COMPACT, SpotType.LARGE)),
    CAR(List.of(SpotType.COMPACT, SpotType.LARGE)),
    TRUCK(List.of(SpotType.LARGE));

    private final List<SpotType> compatibleSpots;

    VehicleType(List<SpotType> compatibleSpots) { this.compatibleSpots = compatibleSpots; }

    public List<SpotType> compatibleSpots() { return compatibleSpots; }
}

// SpotType.java
public enum SpotType { MOTORCYCLE, COMPACT, LARGE }

// Vehicle.java
import java.util.Objects;

public final class Vehicle {
    private final String plate;
    private final VehicleType type;

    public Vehicle(String plate, VehicleType type) {
        this.plate = Objects.requireNonNull(plate);
        this.type = Objects.requireNonNull(type);
    }
    public String plate() { return plate; }
    public VehicleType type() { return type; }
    @Override public String toString() { return type + "[" + plate + "]"; }
}

// ParkingSpot.java
/** Immutable identity of a spot. Occupancy is NOT stored here; it is implied by presence in Floor's free-set. */
public final class ParkingSpot implements Comparable<ParkingSpot> {
    private final int floorNo;
    private final int spotNo;
    private final SpotType type;

    public ParkingSpot(int floorNo, int spotNo, SpotType type) {
        this.floorNo = floorNo; this.spotNo = spotNo; this.type = type;
    }
    public int floorNo() { return floorNo; }
    public int spotNo() { return spotNo; }
    public SpotType type() { return type; }
    public String id() { return "F" + floorNo + "-" + type.name().charAt(0) + spotNo; }

    @Override public int compareTo(ParkingSpot o) {          // nearest to entrance == lowest number
        return Integer.compare(spotNo, o.spotNo);
    }
    @Override public String toString() { return id(); }
}

// Ticket.java
import java.time.Instant;

public final class Ticket {
    private final String id;
    private final Vehicle vehicle;
    private final ParkingSpot spot;
    private final Instant entryTime;

    public Ticket(String id, Vehicle vehicle, ParkingSpot spot, Instant entryTime) {
        this.id = id; this.vehicle = vehicle; this.spot = spot; this.entryTime = entryTime;
    }
    public String id() { return id; }
    public Vehicle vehicle() { return vehicle; }
    public ParkingSpot spot() { return spot; }
    public Instant entryTime() { return entryTime; }
}

// Receipt.java
import java.math.BigDecimal;
import java.time.Duration;

public final class Receipt {
    public final Ticket ticket;
    public final Duration duration;
    public final BigDecimal fee;
    public Receipt(Ticket ticket, Duration duration, BigDecimal fee) {
        this.ticket = ticket; this.duration = duration; this.fee = fee;
    }
    @Override public String toString() {
        return "Receipt{" + ticket.vehicle() + " spot=" + ticket.spot() + " minutes=" + duration.toMinutes() + " fee=" + fee + "}";
    }
}

// ParkingException.java
public class ParkingException extends RuntimeException {
    public ParkingException(String msg) { super(msg); }
}

5.2 Floor (concurrency core)

// Floor.java
import java.util.*;
import java.util.concurrent.ConcurrentHashMap;
import java.util.concurrent.ConcurrentSkipListSet;

/**
 * Holds, per spot type, a sorted concurrent set of FREE spots.
 * pollFirst() is atomic => two threads can never claim the same spot, and no scan / no lock is needed.
 */
public final class Floor {
    private final int number;
    private final Map<SpotType, ConcurrentSkipListSet<ParkingSpot>> free = new ConcurrentHashMap<>();

    public Floor(int number, Map<SpotType, Integer> layout) {
        this.number = number;
        int next = 1;
        for (SpotType t : SpotType.values()) {
            ConcurrentSkipListSet<ParkingSpot> set = new ConcurrentSkipListSet<>();
            for (int i = 0; i < layout.getOrDefault(t, 0); i++) set.add(new ParkingSpot(number, next++, t));
            free.put(t, set);
        }
    }

    public int number() { return number; }

    public Optional<ParkingSpot> claim(SpotType type) { return Optional.ofNullable(free.get(type).pollFirst()); }

    public void release(ParkingSpot spot) { free.get(spot.type()).add(spot); }

    public int freeCount(SpotType type) { return free.get(type).size(); }
}

5.3 Strategies

// SpotAllocationStrategy.java
import java.util.List;
import java.util.Optional;

/** Strategy: HOW we pick a spot. Swap for "spread across floors", "closest to lift", EV-charger-first, etc. */
public interface SpotAllocationStrategy {
    Optional<ParkingSpot> allocate(List<Floor> floors, Vehicle vehicle);
}

// LowestFloorFirstStrategy.java
import java.util.List;
import java.util.Optional;

/** Lowest floor first; within a floor, tightest-fitting spot type first (bike->bike spot, not a truck bay). */
public final class LowestFloorFirstStrategy implements SpotAllocationStrategy {
    @Override
    public Optional<ParkingSpot> allocate(List<Floor> floors, Vehicle vehicle) {
        for (Floor floor : floors) {
            for (SpotType type : vehicle.type().compatibleSpots()) {
                Optional<ParkingSpot> spot = floor.claim(type);
                if (spot.isPresent()) return spot;
            }
        }
        return Optional.empty();
    }
}

// PricingStrategy.java
import java.math.BigDecimal;
import java.time.Duration;

public interface PricingStrategy {
    BigDecimal calculate(Vehicle vehicle, Duration parked);
}

// HourlyPricingStrategy.java
import java.math.BigDecimal;
import java.time.Duration;
import java.util.EnumMap;
import java.util.Map;

/** Rate per started hour, per vehicle type. Minimum charge = 1 hour. First {@code graceMinutes} are free. */
public final class HourlyPricingStrategy implements PricingStrategy {
    private final Map<VehicleType, BigDecimal> ratePerHour = new EnumMap<>(VehicleType.class);
    private final long graceMinutes;

    public HourlyPricingStrategy(Map<VehicleType, BigDecimal> rates, long graceMinutes) {
        this.ratePerHour.putAll(rates);
        this.graceMinutes = graceMinutes;
    }

    @Override
    public BigDecimal calculate(Vehicle vehicle, Duration parked) {
        if (parked.toMinutes() <= graceMinutes) return BigDecimal.ZERO;
        long hours = Math.max(1, (parked.toMinutes() + 59) / 60);   // ceil
        return ratePerHour.get(vehicle.type()).multiply(BigDecimal.valueOf(hours));
    }
}

5.4 Service

// ParkingLot.java
import java.time.Clock;
import java.time.Duration;
import java.time.Instant;
import java.util.*;
import java.util.concurrent.ConcurrentHashMap;
import java.util.concurrent.atomic.AtomicLong;

/**
 * Facade / application service. Stateless apart from the two concurrent maps.
 * Lock granularity: NONE global. Spot claim is atomic inside Floor (skip-list pollFirst);
 * duplicate-entry and double-exit are guarded by atomic add()/remove() on concurrent collections.
 */
public final class ParkingLot {
    private final List<Floor> floors;
    private final SpotAllocationStrategy allocation;
    private final PricingStrategy pricing;
    private final Clock clock;
    private final Map<String, Ticket> activeTickets = new ConcurrentHashMap<>();
    private final Set<String> parkedPlates = ConcurrentHashMap.newKeySet();
    private final AtomicLong seq = new AtomicLong();

    public ParkingLot(List<Floor> floors, SpotAllocationStrategy allocation, PricingStrategy pricing, Clock clock) {
        this.floors = List.copyOf(floors);
        this.allocation = allocation; this.pricing = pricing; this.clock = clock;
    }

    public Ticket park(Vehicle vehicle) {
        if (!parkedPlates.add(vehicle.plate()))
            throw new ParkingException("Vehicle already parked: " + vehicle.plate());
        try {
            ParkingSpot spot = allocation.allocate(floors, vehicle)
                    .orElseThrow(() -> new ParkingException("No spot available for " + vehicle));
            Ticket ticket = new Ticket("T" + seq.incrementAndGet(), vehicle, spot, Instant.now(clock));
            activeTickets.put(ticket.id(), ticket);
            return ticket;
        } catch (RuntimeException e) {
            parkedPlates.remove(vehicle.plate());   // roll back the plate reservation
            throw e;
        }
    }

    public Receipt unpark(String ticketId) {
        Ticket ticket = activeTickets.remove(ticketId);          // atomic: only one exit wins
        if (ticket == null) throw new ParkingException("Invalid or already used ticket: " + ticketId);
        Duration parked = Duration.between(ticket.entryTime(), Instant.now(clock));
        var receipt = new Receipt(ticket, parked, pricing.calculate(ticket.vehicle(), parked));
        floors.get(ticket.spot().floorNo()).release(ticket.spot());
        parkedPlates.remove(ticket.vehicle().plate());
        return receipt;
    }

    public String availability() {
        StringBuilder sb = new StringBuilder();
        for (Floor f : floors) {
            sb.append("Floor ").append(f.number()).append(": ");
            for (SpotType t : SpotType.values()) sb.append(t).append('=').append(f.freeCount(t)).append(' ');
            sb.append('\n');
        }
        return sb.toString().trim();
    }
}

5.5 Demo driver

// Main.java
import java.math.BigDecimal;
import java.time.*;
import java.util.*;
import java.util.concurrent.*;
import java.util.concurrent.atomic.AtomicInteger;

public class Main {
    static final class MutableClock extends Clock {
        private volatile Instant now = Instant.parse("2025-01-01T10:00:00Z");
        void advance(Duration d) { now = now.plus(d); }
        public ZoneId getZone() { return ZoneOffset.UTC; }
        public Clock withZone(ZoneId z) { return this; }
        public Instant instant() { return now; }
    }

    public static void main(String[] args) throws Exception {
        MutableClock clock = new MutableClock();
        // floor 0: 2 bike, 2 compact, 1 large ; floor 1: 0 bike, 2 compact, 1 large   (floor index == list index)
        List<Floor> floors = List.of(
                new Floor(0, Map.of(SpotType.MOTORCYCLE, 2, SpotType.COMPACT, 2, SpotType.LARGE, 1)),
                new Floor(1, Map.of(SpotType.COMPACT, 2, SpotType.LARGE, 1)));
        PricingStrategy pricing = new HourlyPricingStrategy(Map.of(
                VehicleType.MOTORCYCLE, new BigDecimal("10"),
                VehicleType.CAR, new BigDecimal("30"),
                VehicleType.TRUCK, new BigDecimal("60")), 10);
        ParkingLot lot = new ParkingLot(floors, new LowestFloorFirstStrategy(), pricing, clock);

        System.out.println("--- initial ---\n" + lot.availability());
        Ticket bike = lot.park(new Vehicle("KA01-BIKE", VehicleType.MOTORCYCLE));
        Ticket car1 = lot.park(new Vehicle("KA01-CAR1", VehicleType.CAR));
        Ticket truck = lot.park(new Vehicle("KA01-TRK1", VehicleType.TRUCK));
        Ticket truck2 = lot.park(new Vehicle("KA01-TRK2", VehicleType.TRUCK));   // floor 0 large taken -> floor 1
        System.out.println("bike->" + bike.spot() + " car->" + car1.spot() + " truck->" + truck.spot() + " truck2->" + truck2.spot());
        try { lot.park(new Vehicle("KA01-TRK3", VehicleType.TRUCK)); }
        catch (ParkingException e) { System.out.println("Expected: " + e.getMessage()); }
        try { lot.park(new Vehicle("KA01-CAR1", VehicleType.CAR)); }
        catch (ParkingException e) { System.out.println("Expected: " + e.getMessage()); }

        clock.advance(Duration.ofMinutes(135));
        System.out.println(lot.unpark(car1.id()));          // 3 started hours * 30 = 90
        try { lot.unpark(car1.id()); }
        catch (ParkingException e) { System.out.println("Expected: " + e.getMessage()); }
        System.out.println("--- after exit ---\n" + lot.availability());

        // Concurrency: 200 cars race for the remaining COMPACT spots (4 free compact; large bays are taken)
        ExecutorService pool = Executors.newFixedThreadPool(16);
        AtomicInteger ok = new AtomicInteger(), full = new AtomicInteger();
        List<Future<?>> fs = new ArrayList<>();
        for (int i = 0; i < 200; i++) {
            final int n = i;
            fs.add(pool.submit(() -> {
                try { lot.park(new Vehicle("RACE-" + n, VehicleType.CAR)); ok.incrementAndGet(); }
                catch (ParkingException e) { full.incrementAndGet(); }
            }));
        }
        for (Future<?> f : fs) f.get();
        pool.shutdown();
        System.out.println("Race result: parked=" + ok + " rejected=" + full + " (expected parked=4: exactly the 4 free COMPACT spots; LARGE bays are taken by trucks)");
        System.out.println(lot.availability());
    }
}

Real output (from java Main)

--- initial ---
Floor 0: MOTORCYCLE=2 COMPACT=2 LARGE=1 
Floor 1: MOTORCYCLE=0 COMPACT=2 LARGE=1
bike->F0-M1 car->F0-C3 truck->F0-L5 truck2->F1-L3
Expected: No spot available for TRUCK[KA01-TRK3]
Expected: Vehicle already parked: KA01-CAR1
Receipt{CAR[KA01-CAR1] spot=F0-C3 minutes=135 fee=90}
Expected: Invalid or already used ticket: T2
--- after exit ---
Floor 0: MOTORCYCLE=1 COMPACT=2 LARGE=0 
Floor 1: MOTORCYCLE=0 COMPACT=2 LARGE=0
Race result: parked=4 rejected=196 (expected parked=4: exactly the 4 free COMPACT spots; LARGE bays are taken by trucks)
Floor 0: MOTORCYCLE=1 COMPACT=0 LARGE=0 
Floor 1: MOTORCYCLE=0 COMPACT=0 LARGE=0

Note the race: 200 threads compete, exactly 4 succeed (the 4 free compact spots), 196 are rejected, no spot is double-booked.

6. Walkthrough of key flows

Park:
Gate        ParkingLot            Strategy            Floor(s)
 |--park(v)-->|                      |                   |
 |            |-plates.add(plate)?   |                   |
 |            |  (false => already parked, reject)       |
 |            |--allocate(floors,v)->|                   |
 |            |                      |--claim(type)----->| pollFirst() atomic
 |            |                      |<--Optional spot---|
 |            |<---spot--------------|                   |
 |            |-new Ticket, put in activeTickets         |
 |<--Ticket---|
 (no spot => remove plate reservation, throw ParkingException)

Unpark:
Gate        ParkingLot                         Pricing        Floor
 |-unpark(t)->|                                  |             |
 |            |-activeTickets.remove(t) (atomic; null => double exit)
 |            |--calculate(vehicle,duration)---->|             |
 |            |--------------------------------------release-->| add back to free set
 |<--Receipt--|

7. Extensibility (no modification of existing classes)

  • New vehicle type (e.g. BUS, EV_CAR): add enum constant with its compatible spots; add a rate to the pricing map. ParkingLot untouched.
  • New spot type (EV_CHARGER): add SpotType value, give Floor layout entries; EV cars list it first in compatibleSpots().
  • New pricing (weekend surcharge, slab, flat daily cap): implement PricingStrategy; decorate: new DailyCapPricing(new HourlyPricingStrategy(...), cap).
  • New allocation (spread evenly, nearest to lift): implement SpotAllocationStrategy.
  • Payment: ExitService composes ParkingLot.unpark + PaymentProcessor (Strategy per mode: cash/card/UPI); the ticket id is the natural idempotency key.

8. Concurrency and edge cases

  • Spot claim: ConcurrentSkipListSet.pollFirst() is atomic and lock-free -> no global lock; contention only on the same (floor,type) set. A synchronized ParkingLot would serialise all gates; per-floor locks would work but need ordering across floors. Skip-list gives both sorted order and atomic remove.
  • Same vehicle entering twice (two gates): ConcurrentHashMap.newKeySet().add() returns false for the second one. We roll back the plate reservation if no spot is found (try/catch).
  • Double exit / forged ticket: activeTickets.remove(id) returns the ticket exactly once.
  • Spot released before fee computed? Fee is computed first, release after; if pricing throws, the ticket is already removed - in production do release in finally or compute before removal then remove(id, ticket).
  • Edge: parked < grace period -> free; parked 0 min -> still minimum 1h if beyond grace; clock skew -> use a monotonic/ injected Clock; lost ticket -> flat penalty policy by plate lookup (maintain plate->ticket map).
  • Edge: lot full for trucks but free compact spots: truck is rejected (a bigger vehicle must never use a smaller spot).

9. Follow-up questions and model answers

  1. How do you prevent two cars getting the same spot? Atomic pollFirst on a concurrent set; claim is the linearisation point. Not a read-then-write on an occupied boolean.
  2. Why not a lock around park()? Throughput: all gates serialise. Our contention is only per spot-type set.
  3. How to give nearest spot to the entrance for multiple entrances? Allocation strategy takes the gate id; keep a distance matrix, or per-gate priority comparator. Skip-list comparator becomes a Comparator<ParkingSpot> per gate (or use a PriorityQueue under a floor lock).
  4. How do you support reservations? Spot state machine FREE->RESERVED->OCCUPIED with expiry; reserved spots removed from the free set and stored in a map with TTL (scheduled executor releases).
  5. Persist it? Tables: spot(id, floor, type), ticket(id, plate, spot_id, entry_ts, exit_ts, fee, status). Claiming a spot = UPDATE spot SET status='OCCUPIED' WHERE id=? AND status='FREE' (optimistic, check rows=1) or SELECT ... FOR UPDATE SKIP LOCKED LIMIT 1. Unique index on (plate) where status='ACTIVE' replaces the plate set.
  6. Distributed / multiple lots? Lot is the shard key: each lot has its own service instance + DB partition; no cross-lot transactions. A central service handles search/availability via cached counts (eventually consistent) published as events.
  7. Fee dispute / idempotent payment? Receipt has ticket id; payment keyed by ticket id so retries do not double charge.
  8. Testing time-based pricing? Injected Clock (shown in demo).

10. Common mistakes, red flags, rubric

Red flags

  • boolean occupied + if (!spot.occupied) spot.occupied = true (race).
  • Subclass explosion (CarSpot, BikeSpot, Car extends Vehicle with no behaviour).
  • double for money; Date instead of java.time.
  • Pricing hard-coded in ParkingLot; switch(vehicleType) scattered.
  • Giant ParkingLot doing allocation + pricing + payment.
  • Forgetting rollback when allocation fails after reserving something.

Mini rubric (20 pts)

AreaPoints
Requirements clarified, scope stated3
Entity model and relationships sensible4
Strategy for pricing + allocation4
Concurrency-correct allocation, double-exit safe4
Working, runnable code with demo3
Extensibility discussion and follow-ups2