Parking Lot

Design a multi-floor parking lot that issues tickets, finds a free spot of the right size and charges a fee on exit. It is the most common first LLD question.

Design a parking lot for a mall. It has several floors with spots for bikes, cars and large vehicles. A vehicle gets a ticket at entry and pays at exit based on how long it stayed.

Questions to ask first

  • How many floors, gates and spots? Assume 3 floors of about 100 spots each, with 2 entry gates and 2 exit gates.
  • Which vehicle types? Assume bikes, cars and large vehicles (vans and small trucks), each needing its own spot size.
  • Can a bike park in a car spot? Assume no for now: each vehicle needs its exact spot type. We can relax this later.
  • How is the fee worked out? Assume an hourly rate per spot type, rounded up to the next hour.
  • Do we need real payments, reservations or a display board? Assume payment is one call that always succeeds, and no reservations.
  • Can two gates work at the same time? Yes. Two cars must never get the same spot.

Requirements

  • Park a vehicle: find a free spot of the right type, mark it taken and issue a ticket.
  • Unpark: take a ticket, work out the fee, free the spot and close the ticket.
  • Refuse entry with a clear error when no spot of the needed type is free.
  • Let the spot-finding rule and the pricing rule change without editing ParkingLot.
  • Stay correct when several gates park vehicles at the same moment.

Out of scope

  • Real payment gateways, UPI and card handling.
  • Booking spots in advance.
  • Number-plate cameras and boom-barrier hardware.
  • Saving data to a database (in-memory storage is enough).

Entities

  • ParkingLot: park(vehicle), unpark(ticketId)
  • ParkingFloor: holds spots; findFreeSpot(type)
  • ParkingSpot: id, type; tryAssign(vehicle), release()
  • Vehicle (Car, Bike, Truck): number; requiredSpot()
  • Ticket: id, vehicle, spot, entryTime
  • SpotFinder: find(floors, type), the rule for picking a spot
  • FeeStrategy: fee(ticket, exitTime), the rule for pricing
  • SpotType: BIKE, CAR, LARGE

Classes in the model design

  • ParkingLot (class)
  • ParkingFloor (class)
  • ParkingSpot (class)
  • SpotType (enum)
  • Vehicle (abstract)
  • Car (class)
  • Bike (class)
  • Truck (class)
  • Ticket (class)
  • SpotFinder (interface)
  • NearestFirstFinder (class)
  • FeeStrategy (interface)
  • HourlyFeeStrategy (class)

The main use case, step by step

  1. A car reaches entry gate 1. The gate code calls `parkingLot.park(car)`.
  2. ParkingLot asks the car for its size with `car.requiredSpot()`, which returns `SpotType.CAR`. There is no `if` on vehicle type: each subclass answers for itself.
  3. ParkingLot passes the floors and the type to its `SpotFinder`. `NearestFirstFinder` walks the floors from the ground up and returns the first free CAR spot.
  4. ParkingLot calls `spot.tryAssign(car)`. This method is synchronized. If gate 2 took the same spot a moment earlier, it returns false and ParkingLot asks the finder again.
  5. On success, ParkingLot creates a `Ticket` with the vehicle, the spot and the entry time. It stores the ticket in `active` and returns it to the gate.
  6. At exit, `unpark(ticketId)` removes the ticket, asks the `FeeStrategy` for the fee, releases the spot and returns the amount to collect.

Patterns used

  • Strategy: SpotFinder (NearestFirstFinder) and FeeStrategy (HourlyFeeStrategy), both held by ParkingLot.. The rule for picking a spot and the rule for pricing change often. With an interface, a new rule is a new class and ParkingLot stays untouched (the open/closed principle).
  • Polymorphism instead of type checks: Each Vehicle subclass answers requiredSpot().. ParkingLot never writes an if on vehicle type. Adding an electric scooter means one new subclass and no edits elsewhere.
  • Composition: ParkingLot owns ParkingFloor, which owns ParkingSpot.. Floors and spots do not exist outside their lot. The filled diamond tells the reader that removing the lot removes them too.

Key code

Vehicles, spots and the two strategy interfaces

public enum SpotType { BIKE, CAR, LARGE }

public abstract class Vehicle {
    private final String number;
    protected Vehicle(String number) { this.number = number; }
    public String number() { return number; }
    public abstract SpotType requiredSpot();
}

public final class Car extends Vehicle {
    public Car(String number) { super(number); }
    @Override public SpotType requiredSpot() { return SpotType.CAR; }
}

public interface SpotFinder {
    Optional<ParkingSpot> find(List<ParkingFloor> floors, SpotType type);
}

public interface FeeStrategy {
    long fee(Ticket ticket, Instant exitTime);   // rupees
}

public final class ParkingSpot {
    private final String id;
    private final SpotType type;
    private Vehicle vehicle;                     // null when free

    public ParkingSpot(String id, SpotType type) { this.id = id; this.type = type; }

    /** Two gates may pick this spot at once. Only one of them gets true. */
    public synchronized boolean tryAssign(Vehicle v) {
        if (vehicle != null) return false;
        vehicle = v;
        return true;
    }

    public synchronized void release() { vehicle = null; }
    public synchronized boolean isFree() { return vehicle == null; }
    public SpotType type() { return type; }
    public String id() { return id; }
}

ParkingLot: park and unpark

public final class ParkingLot {
    private final List<ParkingFloor> floors;
    private final SpotFinder finder;
    private final FeeStrategy feeStrategy;
    private final Clock clock;                   // java.time.Clock, fixed in tests
    private final Map<String, Ticket> active = new ConcurrentHashMap<>();

    public ParkingLot(List<ParkingFloor> floors, SpotFinder finder, FeeStrategy feeStrategy, Clock clock) {
        this.floors = List.copyOf(floors);
        this.finder = finder;
        this.feeStrategy = feeStrategy;
        this.clock = clock;
    }

    public Ticket park(Vehicle vehicle) {
        SpotType type = vehicle.requiredSpot();
        while (true) {
            ParkingSpot spot = finder.find(floors, type)
                .orElseThrow(() -> new LotFullException(type));
            if (spot.tryAssign(vehicle)) {
                Ticket ticket = new Ticket(UUID.randomUUID().toString(), vehicle, spot, clock.instant());
                active.put(ticket.id(), ticket);
                return ticket;
            }
            // Another gate took this spot between find and assign: look again.
        }
    }

    public long unpark(String ticketId) {
        Ticket ticket = active.remove(ticketId);   // remove is atomic: a ticket is used once
        if (ticket == null) throw new IllegalArgumentException("Unknown or used ticket: " + ticketId);
        long fee = feeStrategy.fee(ticket, clock.instant());
        ticket.spot().release();
        return fee;
    }
}

Deep dives

Two gates, one free spot

Weak: Find a free spot, then set its vehicle with no locking. Gate 1 and gate 2 both read spot A-12 as free and both write to it. Two cars now hold tickets for one spot. This is a race condition: the result depends on which thread runs first.

Good: Make ParkingLot.park synchronized. Only one gate runs it at a time, so the race is gone. It is easy to explain and correct. But every gate now waits for every other gate, even when they want spots on different floors.

Great: Lock only the spot. ParkingSpot.tryAssign is synchronized on the spot and returns false if another gate won. ParkingLot then asks the finder again. Gates that want different spots never wait for each other. An AtomicReference<Vehicle> with compareAndSet(null, car) does the same without a lock.

Trade-off: The lot-wide lock is simpler and fine for 4 gates. The per-spot check scales to many gates but adds a retry loop. Say which one you chose and why.

Pricing rules that keep changing

Weak: A long if inside unpark: bikes pay 20 per hour, cars 40, large vehicles 100. Every new rule edits this method. Weekend rates, a free first 15 minutes and a daily cap all land in the same place, and each edit can break an old rule.

Good: A FeeStrategy interface with HourlyFeeStrategy. ParkingLot receives it through the constructor. A new pricing scheme is a new class, and tests can pass a strategy with fixed numbers.

Great: Keep FeeStrategy, and build complex schemes from small ones. FirstFreeMinutes wraps another strategy and returns 0 for short stays. DailyCap wraps another and limits the total. These wrappers are decorators: classes that implement the same interface and add one rule around an inner object. Pass a Clock into ParkingLot so tests control time.

Trade-off: Decorators give many combinations with few classes, but the order of wrapping matters and must be written down. In an interview the plain strategy is enough. Mention decorators when the interviewer adds rules.

Vehicles: subclasses or an enum?

Weak: A String type field on Vehicle, compared as text in many places. A typo such as "cra" becomes a bug that shows only at runtime.

Good: An abstract Vehicle with Car, Bike and Truck. Each returns its own requiredSpot(). This shows polymorphism, which interviewers like to see, and removes type checks from ParkingLot.

Great: Ask whether vehicle types differ in behaviour or only in data. Here they differ only in the spot they need. A VehicleType enum with a spotType field is then enough, and fewer classes is a plus. Keep subclasses if types will gain different behaviour, such as an EV that needs charging.

Trade-off: Subclasses make new behaviour easy to add. An enum makes new types cheap but pushes behaviour into switch statements. Both are acceptable if you can explain the choice.

Now add one more feature

  • Now add EV charging spots. What changes? Add `EV_CHARGING` to SpotType and an `ElectricCar` that needs it. Charging is billed per kWh, so add a `ChargingFeeStrategy` and add its amount to the parking fee. ParkingLot and the finder do not change.
  • Now let a bike use a car spot when all bike spots are full. Change only the finder. Give each vehicle an ordered list of spot types it fits, and let the finder try them in order. Pricing still uses the vehicle type.
  • Now show free spots per floor on a board at the entrance. ParkingFloor publishes an event when a spot is taken or freed. A `DisplayBoard` subscribes to it (the observer pattern), so ParkingSpot does not know that boards exist.
  • Now add a monthly pass. Look up the vehicle number in a `PassRegistry` at the exit gate. Pass holders get a FeeStrategy that returns 0. The strategy is chosen per ticket instead of once for the whole lot.

What each level is expected to show

SDE-1: A clean diagram with lot, floor, spot, vehicle and ticket, correct composition, and working `park` and `unpark`. Pricing sits behind an interface. Knows that two gates can race and can make `park` synchronized.

SDE-2: All of SDE-1, plus per-spot atomic assignment with a retry, a Clock passed in for testable fees, and a clear reason for subclasses or an enum. Answers extensions like EV spots by naming the exact classes that change and the ones that do not.

Common mistakes

  • Putting finding, pricing, ticketing and printing in one ParkingLot class with 20 methods.
  • Writing `instanceof Car` checks in the lot instead of asking the vehicle for its spot type.
  • Making CarSpot and BikeSpot subclasses when they differ only in a type field. An enum is enough.
  • Ignoring two gates at once. Interviewers often ask what happens when two cars arrive together.
  • Storing the price rule inside Ticket, so a price change means editing the ticket class.
  • Drawing composition from Ticket to Vehicle. The car exists before and after the ticket, so it is an association.

Lessons behind this answer