Design a Parking Lot

Why the parking lot is the classic first case study

The parking lot is the most commonly asked low-level design (LLD) problem. Low-level design means turning a set of requirements into classes, interfaces, relationships and working code, as opposed to high-level design, which is about servers, databases and networks. The parking lot is popular because everybody already understands the domain, so the interviewer can spend the whole round on how you model it rather than on explaining what a parking lot is.

That familiarity is also a trap. Candidates rush to draw Vehicle, Car, Bike and ParkingSpot and then run out of time before reaching the parts the interviewer actually scores: where the pricing rules live, how the display boards learn about changes, and what stops two cars at two different entry gates from being given the same spot. This lesson walks through the full interview flow and ends with a complete Java program, around 300 lines, that compiles, runs and proves it never double-books a spot even when 200 threads race for two spaces.

If the patterns used here are new to you, read Behavioural patterns first, especially Strategy and Observer.

What interviewers typically probe:

• Do you ask clarifying questions before drawing classes, and do you write down assumptions?
• Do you separate stable data (spots, tickets) from rules that change (pricing, allocation)?
• Can you name the patterns you used and say why, without forcing patterns where none are needed?
• Can you explain the concurrency problem at the entry gates and fix it with the right locking granularity?
• When they add a new requirement (electric charging spots, reservations, monthly passes), does your design absorb it with a new class rather than edits all over the code?

Problem statement

Design the software for a multi-storey parking lot. Vehicles of different types arrive at one of several entry gates, receive a ticket and are assigned a spot that fits them. When they leave through an exit gate, the system computes the fee from the time spent, collects payment and frees the spot. Display boards at the entrance and on each floor show how many free spots of each type remain.

That is all the interviewer will usually say. The rest you must draw out by asking.

Clarifying questions and assumed requirements

Spend the first five minutes asking questions. Each answer either adds a class or removes one, so these questions directly shape the design. Here are the questions worth asking and the answers we will assume.

Functional requirements

These describe what the system must do:

1. Model floors with spots of three sizes.
2. Issue a ticket at an entry gate, assigning the best-fitting free spot.
3. Reject a vehicle when no fitting spot is free, and reject a number plate that is already inside.
4. At an exit gate, compute the fee, take payment, and free the spot only after a successful payment.
5. Let the operator change the pricing scheme without changing parking logic.
6. Keep display boards up to date with free counts per floor and size.

Non-functional requirements

These describe qualities the system must have:

• Correctness under concurrency: two gates must never assign the same spot. This is the most important property.
• Low latency at the gate: a driver should not wait; allocation should be quick and should not block other gates for long.
• Extensibility: new vehicle types, pricing rules and payment methods are added by writing new classes.
• Testability: time must be injectable so that fee tests are deterministic.

Core use cases

A use case is one complete interaction a user has with the system. Listing them keeps you from designing classes nobody calls.

1. Park: driver arrives at entry gate E1 with a car; system finds a spot, occupies it, prints ticket T1.
2. Quote: driver (or exit gate) asks how much ticket T1 costs right now.
3. Exit and pay: driver presents T1 at exit gate X1, pays by card, gate opens, spot is freed.
4. Payment failure: card is declined; ticket stays active, spot stays occupied, driver retries with cash.
5. Lot full: truck arrives, no large spot is free, driver is turned away.
6. Board update: any park or exit refreshes the free counts on every board.
7. Change tariff: operator switches from hourly to "flat for two hours, then hourly".

Entities and relationships

Nouns in the requirements are candidate classes. Verbs become methods. Then decide which nouns hold data and which hold rules.

+----------------+ 1      * +--------------+ 1     * +-------------+
|  ParkingLot    |----------| ParkingFloor |---------| ParkingSpot |
|----------------|          |--------------|         |-------------|
| park(vehicle)  |          | spotsOf(size)|         | id, floor   |
| exit(id, pay)  |          | freeCount()  |         | size        |
| quote(id)      |          +--------------+         | tryOccupy() |
+----------------+                                   | release()   |
   |  |  |   |                                       +-------------+
   |  |  |   | uses       +------------------------+       ^
   |  |  |   +----------->| SpotAllocationStrategy |       | refers to
   |  |  | uses           +------------------------+       |
   |  |  +--------------->| PricingStrategy        |  +---------+
   |  |                   +------------------------+  | Ticket  |
   |  | notifies *        +------------------------+  |---------|
   |  +------------------>| AvailabilityListener   |  | vehicle |
   |                      +------------------------+  | spot    |
   | owns active tickets            ^ implements      | entry   |
   +------------------------------> DisplayBoard      | status  |
                                                      +---------+
EntryGate --admit()--> ParkingLot <--release()-- ExitGate
ExitGate uses PaymentMethod (CashPayment, CardPayment)

Read the diagram like this:

• Composition (the lot owns floors, floors own spots): spots do not exist without their floor, so the floor creates them.
• Association (a ticket refers to a vehicle and a spot): the ticket does not own the spot; it just remembers which one it holds.
• Dependency on interfaces (the lot uses PricingStrategy, not HourlyPricing): the lot can be given any pricing class at construction time or later.

Notice what is not a class: there is no Car, Truck or Motorcycle subclass. They would have no behaviour of their own. A vehicle type differs only in which spots it fits, and an enum captures that in one line. Subclassing each vehicle is the most common over-design in this problem.

Design decisions and patterns

Strategy for pricing

The Strategy pattern puts a family of interchangeable algorithms behind one interface so the caller can switch between them without changing its own code. Pricing is the textbook case: weekday hourly, weekend flat, festival surge, first 15 minutes free. Each scheme is a class implementing:

interface PricingStrategy {
    long feeInRupees(Ticket ticket, Instant exitTime);
}

The lot calls pricing.feeInRupees(...) and never learns which scheme it is. Adding "free for the first 15 minutes" means writing one new class; the lot, the ticket and the gates do not change. This is the Open/Closed principle from SOLID principles: open for extension, closed for modification.

Two schemes are implemented. Let us work out both by hand so you can trust the program's output later.

Hourly pricing, car rate Rs 50 per started hour, minimum one hour. A car parked for 61 minutes:

started hours = ceil(61 / 60) = (61 + 59) / 60 = 120 / 60 = 2
fee           = 2 * 50 = Rs 100

The (minutes + 59) / 60 trick computes the ceiling with integer division. Math.max(1, ...) ensures a car that leaves after 0 minutes still pays for one hour.

Flat then hourly, Rs 60 for the first two hours, then Rs 30 per started extra hour. A motorcycle parked for 181 minutes:

minutes beyond 120 = 181 - 120 = 61
extra hours        = (61 + 59) / 60 = 2
fee                = 60 + 2 * 30 = Rs 120

At exactly 120 minutes the extra-hours term is (0 + 59) / 60 = 0, so the fee is the flat Rs 60. For stays under two hours the subtraction goes negative, and Math.max(0, ...) keeps it at zero.

Strategy for spot allocation

Choosing a spot is also a rule that changes. Our default, BestFitLowestFloor, tries the smallest size that fits first, across all floors from the lowest, and only then moves to bigger sizes. This keeps large spots free for trucks. A different lot might prefer "nearest to the lift" or "spread load across floors". Each is a new strategy class.

Order of loops matters, and it is worth showing the interviewer why. Suppose floor 1 has spots M1, M2 and L1, floor 2 has M1 and M2, and three cars then a truck arrive.

Floor-first loop (for floor, for size):
  car 1 -> F1-M1, car 2 -> F1-M2, car 3 -> F1-L1  (floor 1 not full yet)
  truck -> no large spot left anywhere: REJECTED

Size-first loop (for size, for floor):
  car 1 -> F1-M1, car 2 -> F1-M2, car 3 -> F2-M1  (all mediums first)
  truck -> F1-L1: PARKED

The floor-first loop is the natural first draft, and it quietly wastes the only large spot. Running a small scenario by hand on the whiteboard is how you catch this kind of bug before the interviewer does.

The strategy returns an ordered list of candidates rather than one spot. That small decision is what makes the concurrency fix simple: if another gate grabs the first candidate a moment earlier, the lot just tries the next one.

Observer for display boards

The Observer pattern lets one object (the subject) notify any number of other objects (observers) when its state changes, without knowing what they are. The lot is the subject; display boards are observers.

interface AvailabilityListener {
    void onAvailabilityChanged(int floor, SpotSize size, long freeNow);
}

Why not have the lot call entranceBoard.update() directly? Because next month someone will want an SMS alert when the lot is 90% full, a mobile app feed and a metrics counter. With Observer, each is a new listener registered at start-up; the lot's code does not change.

The listener list is a CopyOnWriteArrayList. Every add copies the array, which is expensive, but iteration needs no lock and never throws ConcurrentModificationException. That trade-off suits listeners: registered once, notified constantly.

Composition over inheritance for gates

EntryGate and ExitGate are thin wrappers that hold an id and a reference to the lot. They exist because real gates have hardware (ticket printers, barrier arms), and that code should not live inside the lot. They contain no parking logic, so all rules stay in one place.

Should the lot be a Singleton?

Many tutorials make ParkingLot a Singleton (a class that allows only one instance). Avoid it. A Singleton is global state: it makes tests share one lot and makes "operate two lots" a rewrite. Create one lot in main and pass it to the gates. If the interviewer asks, say: "There is one lot per deployment, but I enforce that by wiring, not by a static instance, so tests can create fresh lots." See Creational patterns for the full Singleton discussion.

Injecting the clock

Fees depend on time. If the code calls Instant.now() directly, a test of "61 minutes costs Rs 100" would need to sleep for 61 minutes. Instead the lot receives a java.time.Clock. Production passes Clock.systemUTC(); the demo passes a ManualClock it can move forward. This is dependency injection applied to time, and interviewers notice it.

Ticket state

A ticket moves through a tiny state machine:

          park()                    exit() with successful payment
 (none) ---------> ACTIVE  -------------------------------------> PAID
                     |  ^
                     |  | payment declined: stays ACTIVE
                     +--+

A ticket that is PAID cannot be used again. That blocks a classic bug where a driver passes their paid ticket to a friend who then exits for free, or where a double click at the exit gate charges twice.

Complete Java implementation

The whole program is one file so you can compile and run it with no build tool. Every class except ParkingLotDemo is package-private (no public keyword), which Java allows for any number of top-level classes in a file. In an interview you would split these into files and packages; the code is the same.

Save it as ParkingLotDemo.java, then run javac ParkingLotDemo.java and java ParkingLotDemo. It needs Java 17 or later because it uses records.

import java.time.Duration;
import java.time.Instant;
import java.time.ZoneId;
import java.time.Clock;
import java.util.*;
import java.util.concurrent.*;
import java.util.concurrent.atomic.*;

// ---------- Vehicles and spots ----------

enum SpotSize { SMALL, MEDIUM, LARGE }

enum VehicleType {
    MOTORCYCLE(SpotSize.SMALL), CAR(SpotSize.MEDIUM), TRUCK(SpotSize.LARGE);

    final SpotSize minimumSpot;
    VehicleType(SpotSize minimumSpot) { this.minimumSpot = minimumSpot; }

    boolean fits(SpotSize size) { return size.ordinal() >= minimumSpot.ordinal(); }
}

record Vehicle(String plate, VehicleType type) {
    Vehicle {
        plate = plate.trim().toUpperCase();
        if (plate.isEmpty()) throw new IllegalArgumentException("plate is empty");
    }
}

final class ParkingSpot {
    private final String id;
    private final int floor;
    private final SpotSize size;
    // null = free. Compare-and-set makes "check free, then occupy" one atomic step.
    private final AtomicReference<Vehicle> occupant = new AtomicReference<>();

    ParkingSpot(String id, int floor, SpotSize size) {
        this.id = id; this.floor = floor; this.size = size;
    }

    boolean tryOccupy(Vehicle v) { return occupant.compareAndSet(null, v); }
    void release() { occupant.set(null); }
    boolean isFree() { return occupant.get() == null; }
    String id() { return id; }
    int floor() { return floor; }
    SpotSize size() { return size; }
}

final class ParkingFloor {
    private final int number;
    private final Map<SpotSize, List<ParkingSpot>> spots = new EnumMap<>(SpotSize.class);

    ParkingFloor(int number, int small, int medium, int large) {
        this.number = number;
        add(SpotSize.SMALL, small, "S");
        add(SpotSize.MEDIUM, medium, "M");
        add(SpotSize.LARGE, large, "L");
    }

    private void add(SpotSize size, int count, String prefix) {
        List<ParkingSpot> list = new ArrayList<>();
        for (int i = 1; i <= count; i++) list.add(new ParkingSpot("F" + number + "-" + prefix + i, number, size));
        spots.put(size, List.copyOf(list));
    }

    int number() { return number; }
    List<ParkingSpot> spotsOf(SpotSize size) { return spots.get(size); }

    long freeCount(SpotSize size) {
        return spots.get(size).stream().filter(ParkingSpot::isFree).count();
    }
}

// ---------- Strategies ----------

interface SpotAllocationStrategy {
    /** Candidate spots in the order they should be tried. */
    List<ParkingSpot> candidates(List<ParkingFloor> floors, VehicleType type);
}

/** Smallest spot size that fits first (saves big spots), then the lowest floor. */
final class BestFitLowestFloor implements SpotAllocationStrategy {
    public List<ParkingSpot> candidates(List<ParkingFloor> floors, VehicleType type) {
        List<ParkingSpot> out = new ArrayList<>();
        for (SpotSize s : SpotSize.values())
            if (type.fits(s))
                for (ParkingFloor f : floors)
                    for (ParkingSpot spot : f.spotsOf(s)) if (spot.isFree()) out.add(spot);
        return out;
    }
}

interface PricingStrategy {
    long feeInRupees(Ticket ticket, Instant exitTime);
}

/** Every started hour is charged; the first hour is always charged. */
final class HourlyPricing implements PricingStrategy {
    private final Map<VehicleType, Long> ratePerHour;
    HourlyPricing(Map<VehicleType, Long> ratePerHour) { this.ratePerHour = Map.copyOf(ratePerHour); }

    public long feeInRupees(Ticket t, Instant exit) {
        long minutes = Duration.between(t.entryTime(), exit).toMinutes();
        long hours = Math.max(1, (minutes + 59) / 60);
        return hours * ratePerHour.get(t.vehicle().type());
    }
}

/** Flat amount for the first two hours, then a per-hour rate. */
final class FlatThenHourlyPricing implements PricingStrategy {
    private final long flat, perExtraHour;
    FlatThenHourlyPricing(long flat, long perExtraHour) { this.flat = flat; this.perExtraHour = perExtraHour; }

    public long feeInRupees(Ticket t, Instant exit) {
        long minutes = Duration.between(t.entryTime(), exit).toMinutes();
        long extraHours = Math.max(0, (minutes - 120 + 59) / 60);
        return flat + extraHours * perExtraHour;
    }
}

// ---------- Tickets and payment ----------

enum TicketStatus { ACTIVE, PAID }

final class Ticket {
    private final String id;
    private final Vehicle vehicle;
    private final ParkingSpot spot;
    private final Instant entryTime;
    private final AtomicReference<TicketStatus> status = new AtomicReference<>(TicketStatus.ACTIVE);

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

    boolean markPaid() { return status.compareAndSet(TicketStatus.ACTIVE, TicketStatus.PAID); }
    String id() { return id; }
    Vehicle vehicle() { return vehicle; }
    ParkingSpot spot() { return spot; }
    Instant entryTime() { return entryTime; }
    TicketStatus status() { return status.get(); }
}

interface PaymentMethod {
    boolean pay(long amountInRupees);
    String name();
}

final class CashPayment implements PaymentMethod {
    private final long tendered;
    CashPayment(long tendered) { this.tendered = tendered; }
    public boolean pay(long amount) { return tendered >= amount; }
    public String name() { return "cash"; }
}

final class CardPayment implements PaymentMethod {
    private final boolean approved;
    CardPayment(boolean approved) { this.approved = approved; }
    public boolean pay(long amount) { return approved; }
    public String name() { return "card"; }
}

record Receipt(String ticketId, String plate, long minutes, long amount, String method) {}

// ---------- Observer ----------

interface AvailabilityListener {
    void onAvailabilityChanged(int floor, SpotSize size, long freeNow);
}

final class DisplayBoard implements AvailabilityListener {
    private final String name;
    private final Map<String, Long> latest = new ConcurrentSkipListMap<>();
    DisplayBoard(String name) { this.name = name; }

    public void onAvailabilityChanged(int floor, SpotSize size, long freeNow) {
        latest.put("F" + floor + " " + size, freeNow);
    }

    String render() { return name + " " + latest; }
}

// ---------- The lot ----------

final class ParkingFullException extends RuntimeException {
    ParkingFullException(String msg) { super(msg); }
}

final class ParkingLot {
    private final List<ParkingFloor> floors;
    private final Clock clock;
    private volatile SpotAllocationStrategy allocation;
    private volatile PricingStrategy pricing;
    private final Map<String, Ticket> activeByTicketId = new ConcurrentHashMap<>();
    private final Map<String, Ticket> activeByPlate = new ConcurrentHashMap<>();
    private final List<AvailabilityListener> listeners = new CopyOnWriteArrayList<>();
    private final AtomicLong ticketSeq = new AtomicLong();

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

    void addListener(AvailabilityListener l) { listeners.add(l); }
    void setPricing(PricingStrategy p) { this.pricing = p; }

    Ticket park(Vehicle v) {
        for (ParkingSpot spot : allocation.candidates(floors, v.type())) {
            if (!spot.tryOccupy(v)) continue;            // someone else won this spot; try the next
            Ticket t = new Ticket("T" + ticketSeq.incrementAndGet(), v, spot, clock.instant());
            if (activeByPlate.putIfAbsent(v.plate(), t) != null) {
                spot.release();                          // undo: this plate is already inside
                throw new IllegalStateException(v.plate() + " is already parked");
            }
            activeByTicketId.put(t.id(), t);
            notifyChange(spot);
            return t;
        }
        throw new ParkingFullException("no free spot for " + v.type());
    }

    long quote(String ticketId) {
        return pricing.feeInRupees(find(ticketId), clock.instant());
    }

    Receipt exit(String ticketId, PaymentMethod method) {
        Ticket t = find(ticketId);
        Instant now = clock.instant();
        long amount;
        synchronized (t) {                               // one payment attempt per ticket at a time
            if (t.status() != TicketStatus.ACTIVE) throw new IllegalStateException("ticket " + ticketId + " already used");
            amount = pricing.feeInRupees(t, now);
            if (!method.pay(amount)) throw new IllegalStateException("payment declined, gate stays closed");
            t.markPaid();
        }
        activeByTicketId.remove(t.id());
        activeByPlate.remove(t.vehicle().plate());
        t.spot().release();
        notifyChange(t.spot());
        long minutes = Duration.between(t.entryTime(), now).toMinutes();
        return new Receipt(t.id(), t.vehicle().plate(), minutes, amount, method.name());
    }

    private Ticket find(String ticketId) {
        Ticket t = activeByTicketId.get(ticketId);
        if (t == null) throw new NoSuchElementException("unknown or closed ticket " + ticketId);
        return t;
    }

    private void notifyChange(ParkingSpot spot) {
        ParkingFloor floor = floors.get(spot.floor() - 1);
        long free = floor.freeCount(spot.size());
        for (AvailabilityListener l : listeners) l.onAvailabilityChanged(spot.floor(), spot.size(), free);
    }

    int activeCount() { return activeByTicketId.size(); }
}

// ---------- Gates ----------

final class EntryGate {
    private final String id; private final ParkingLot lot;
    EntryGate(String id, ParkingLot lot) { this.id = id; this.lot = lot; }
    Ticket admit(Vehicle v) { return lot.park(v); }
    String id() { return id; }
}

final class ExitGate {
    private final String id; private final ParkingLot lot;
    ExitGate(String id, ParkingLot lot) { this.id = id; this.lot = lot; }
    Receipt release(String ticketId, PaymentMethod m) { return lot.exit(ticketId, m); }
    String id() { return id; }
}

/** A clock the demo can move forward, so fees are deterministic. */
final class ManualClock extends Clock {
    private Instant now;
    ManualClock(Instant start) { this.now = start; }
    void advanceMinutes(long m) { now = now.plus(Duration.ofMinutes(m)); }
    public Instant instant() { return now; }
    public ZoneId getZone() { return ZoneId.of("UTC"); }
    public Clock withZone(ZoneId zone) { return this; }
}

public class ParkingLotDemo {
    public static void main(String[] args) throws Exception {
        ManualClock clock = new ManualClock(Instant.parse("2026-10-10T09:00:00Z"));
        List<ParkingFloor> floors = List.of(new ParkingFloor(1, 1, 2, 1), new ParkingFloor(2, 2, 2, 0));
        PricingStrategy hourly = new HourlyPricing(Map.of(
                VehicleType.MOTORCYCLE, 20L, VehicleType.CAR, 50L, VehicleType.TRUCK, 100L));
        ParkingLot lot = new ParkingLot(floors, clock, new BestFitLowestFloor(), hourly);
        DisplayBoard board = new DisplayBoard("Entrance board");
        lot.addListener(board);
        EntryGate entry = new EntryGate("E1", lot);
        ExitGate exit = new ExitGate("X1", lot);

        System.out.println("== 1. Parking ==");
        Ticket bike = entry.admit(new Vehicle("ka01ab1234", VehicleType.MOTORCYCLE));
        Ticket car1 = entry.admit(new Vehicle("KA02CD5678", VehicleType.CAR));
        Ticket car2 = entry.admit(new Vehicle("KA03EF0001", VehicleType.CAR));
        Ticket car3 = entry.admit(new Vehicle("KA04GH0002", VehicleType.CAR));
        Ticket truck = entry.admit(new Vehicle("KA05TR9999", VehicleType.TRUCK));
        for (Ticket t : List.of(bike, car1, car2, car3, truck))
            System.out.println(t.id() + " " + t.vehicle().plate() + " -> " + t.spot().id());
        System.out.println(board.render());

        System.out.println("== 2. Rejections ==");
        try { entry.admit(new Vehicle("KA02CD5678", VehicleType.CAR)); }
        catch (IllegalStateException e) { System.out.println("rejected: " + e.getMessage()); }
        try { entry.admit(new Vehicle("KA06XY1111", VehicleType.TRUCK)); }
        catch (ParkingFullException e) { System.out.println("rejected: " + e.getMessage()); }

        System.out.println("== 3. Exit and pricing ==");
        clock.advanceMinutes(61);
        System.out.println("quote for " + car1.id() + " after 61 min: Rs " + lot.quote(car1.id()));
        try { exit.release(car1.id(), new CardPayment(false)); }
        catch (IllegalStateException e) { System.out.println("rejected: " + e.getMessage()); }
        System.out.println(exit.release(car1.id(), new CardPayment(true)));
        try { exit.release(car1.id(), new CashPayment(500)); }
        catch (NoSuchElementException e) { System.out.println("rejected: " + e.getMessage()); }
        lot.setPricing(new FlatThenHourlyPricing(60, 30));
        clock.advanceMinutes(120);                       // bike has now been inside 181 minutes
        System.out.println(exit.release(bike.id(), new CashPayment(200)));
        System.out.println(board.render());

        System.out.println("== 4. 200 threads race for the free car spots ==");
        lot.setPricing(hourly);
        int before = lot.activeCount();
        ExecutorService pool = Executors.newFixedThreadPool(16);
        CountDownLatch start = new CountDownLatch(1);
        List<Future<String>> results = new ArrayList<>();
        for (int i = 0; i < 200; i++) {
            final int n = i;
            results.add(pool.submit(() -> {
                start.await();
                try { return lot.park(new Vehicle("RACE" + n, VehicleType.CAR)).spot().id(); }
                catch (ParkingFullException e) { return null; }
            }));
        }
        start.countDown();
        List<String> won = new ArrayList<>();
        for (Future<String> f : results) if (f.get() != null) won.add(f.get());
        pool.shutdown();
        Collections.sort(won);
        System.out.println("active before race: " + before);
        System.out.println("cars parked in race: " + won.size());
        System.out.println("distinct spots: " + new HashSet<>(won).size() + " " + won);
        System.out.println("active after race: " + lot.activeCount());
    }
}

What the demo does

The demo builds two floors:

Floor 1:  S1 (small)  M1 M2 (medium)  L1 (large)
Floor 2:  S1 S2 (small)  M1 M2 (medium)  no large spots

Then it runs four scenarios:

1. Park a motorcycle, three cars and a truck, and print each assignment and the board.
2. Try a duplicate number plate and a second truck, both rejected.
3. Move the clock 61 minutes, quote the first car, decline a card, pay by card, try to reuse the ticket, switch to flat pricing, move 120 more minutes and let the motorcycle leave.
4. Start 200 threads at the same instant, each trying to park a car, and check how many win and whether any spot was given twice.

Real output

This is the actual output from running the program with Temurin JDK 21:

== 1. Parking ==
T1 KA01AB1234 -> F1-S1
T2 KA02CD5678 -> F1-M1
T3 KA03EF0001 -> F1-M2
T4 KA04GH0002 -> F2-M1
T5 KA05TR9999 -> F1-L1
Entrance board {F1 LARGE=0, F1 MEDIUM=0, F1 SMALL=0, F2 MEDIUM=1}
== 2. Rejections ==
rejected: KA02CD5678 is already parked
rejected: no free spot for TRUCK
== 3. Exit and pricing ==
quote for T2 after 61 min: Rs 100
rejected: payment declined, gate stays closed
Receipt[ticketId=T2, plate=KA02CD5678, minutes=61, amount=100, method=card]
rejected: unknown or closed ticket T2
Receipt[ticketId=T1, plate=KA01AB1234, minutes=181, amount=120, method=cash]
Entrance board {F1 LARGE=0, F1 MEDIUM=1, F1 SMALL=1, F2 MEDIUM=1}
== 4. 200 threads race for the free car spots ==
active before race: 3
cars parked in race: 2
distinct spots: 2 [F1-M1, F2-M2]
active after race: 5

Check it against the hand calculations:

• The plate ka01ab1234 was typed in lower case and stored as KA01AB1234, because the Vehicle record normalises it in its compact constructor.
• The third car went to F2-M1, not the large spot, so the truck got F1-L1. The size-first loop works.
• The board only lists sections that changed since start-up; F2 MEDIUM=1 means one medium spot remains on floor 2.
• The car's fee after 61 minutes is Rs 100 and the motorcycle's after 181 minutes on the flat scheme is Rs 120, matching the worked examples.
• The declined card left the ticket active; the later card payment succeeded; reusing ticket T2 was rejected.
• In the race, exactly two car-compatible spots were free (F1-M1, freed by the first car, and F2-M2). Exactly two of the 200 threads won, the two spots are distinct, and the active count went from 3 to 5. Run it many times and the counts never change; only which threads win does.

Concurrency considerations

The double-booking race

Multiple entry gates call park at the same time. A naive implementation looks like this:

for (ParkingSpot spot : candidates) {
    if (spot.isFree()) {          // step 1: check
        spot.setOccupant(v);      // step 2: act
        return newTicket(spot);
    }
}

This is a check-then-act race: the result of step 1 can be out of date by the time step 2 runs. Here is the interleaving that double-books spot F1-M1:

time   Gate E1 (car A)                Gate E2 (car B)
 t1    isFree(F1-M1) -> true
 t2                                   isFree(F1-M1) -> true
 t3    setOccupant(A)
 t4                                   setOccupant(B)   overwrites A
 t5    ticket says F1-M1              ticket says F1-M1

Both drivers receive a ticket for the same spot. The fix is to make check and act a single indivisible step. Read Synchronization if race conditions and atomicity are new to you.

Option 1: one big lock

Mark park and exit as synchronized on the lot. Only one gate works at a time, so the race cannot happen. This is correct and is a perfectly good first answer in an interview. The cost is that all gates queue behind each other, even when they want spots on different floors. For a lot with four gates and a few hundred cars per hour that is fine; say so.

Option 2: per-floor locks

Give each floor its own lock. Gates looking at different floors proceed in parallel. This is a common middle ground, but the allocator now has to lock floors in a fixed order (say, floor 1 then 2) if it ever holds more than one, or it can deadlock. See Deadlocks for why a fixed lock order prevents circular wait.

Option 3: per-spot compare-and-set (what the code uses)

Each ParkingSpot holds an AtomicReference<Vehicle>. Compare-and-set (CAS) is a single CPU-level operation that says "set this field to X only if it currently holds Y, and tell me whether it worked". The code calls occupant.compareAndSet(null, v): set the occupant to this vehicle only if it is still empty.

time   Gate E1 (car A)                    Gate E2 (car B)
 t1    CAS(F1-M1, null -> A) = true
 t2                                       CAS(F1-M1, null -> B) = false
 t3    ticket for F1-M1                   try next candidate: F2-M2
 t4                                       CAS(F2-M2, null -> B) = true

Exactly one CAS on a given spot can succeed while it is free. The loser does not wait; it moves to the next candidate in the list the strategy returned. This is the finest locking granularity possible, one spot, and it never blocks.

The other shared state

Claiming the spot is not the only shared state:

• Active tickets by plate: activeByPlate.putIfAbsent(plate, ticket) is atomic in ConcurrentHashMap, so two gates cannot both admit the same plate. If it fails, the code releases the spot it just claimed. This "claim, then undo on failure" step is called a compensating action.
• Ticket numbers: AtomicLong.incrementAndGet() gives unique ids without a lock. A side effect is that a rejected duplicate still consumes a number; gaps in ticket numbers are harmless.
• Exit: a synchronized (ticket) block covers check status, compute fee, charge and mark paid. Locking on the ticket (not the lot) means two different cars exit in parallel, but a double click on the same ticket cannot charge twice.
• Strategy swap: pricing is volatile, so a new scheme set by the operator is seen by all gate threads immediately. A volatile field guarantees visibility of the latest write across threads.

Is the board exact?

freeCount scans a floor's spots without a lock, so under heavy concurrency a board might show a number that is one step behind for a moment. That is acceptable for a display: the next event corrects it. Allocation correctness never depends on the board. If the interviewer asks for exact counts, keep an AtomicInteger per floor and size, decremented after a successful CAS and incremented on release.

When there are many servers

Everything above assumes one Java process. If several application servers share a database, in-memory locks do not protect anything across machines. Use the database instead: either UPDATE spot SET vehicle = ? WHERE id = ? AND vehicle IS NULL and check that one row changed (the SQL version of CAS), or a unique constraint on active spot assignments. See Concurrency control for row locks and isolation levels.

Extensions interviewers ask, and how the design absorbs them

A good design is judged by how small the change is when a requirement arrives. For each common follow-up, here is the change.

1. Electric vehicle (EV) charging spots. Add a features set on ParkingSpot (for example EV_CHARGER) and an ElectricCar need on the vehicle. A new allocation strategy prefers charger spots for EVs and avoids them for others. Pricing becomes a composite: parking fee plus energy used. Use a CompositePricing that sums two strategies. No existing class changes except adding a field.

2. Reservations. Add a RESERVED state to the spot claim: CAS from null to a reservation marker, with an expiry time. At arrival, the driver's reservation id lets the lot CAS from that marker to the vehicle. A background task clears expired reservations. This is the same seat-hold idea used in movie ticket booking.

3. Monthly passes. A pass holder pays nothing at exit. Add a PassPricing decorator: it checks the plate against active passes and returns 0, otherwise delegates to the wrapped strategy. The Decorator pattern wraps an object to add behaviour while keeping the same interface; see Structural patterns.

4. Lost ticket. The exit gate looks up the active ticket by plate (activeByPlate already exists) and charges a lost-ticket penalty strategy. The index we added for duplicate checks pays for itself here.

5. Different rates on weekends or at night. A TimeOfDayPricing strategy splits the stay into segments by rate period and sums each. Test it with the injected clock across midnight.

6. Handicapped or reserved-for-staff spots. Same as EV: a spot feature plus an allocation rule. Allocation strategies can be chained: filter by feature, then best fit.

7. Multiple lots in a city. A ParkingLotRegistry maps lot ids to lots. Because the lot is not a Singleton, this is trivial.

8. Pay at a kiosk before reaching the exit. Payment and exit become separate steps. Add a PAID timestamp and a grace period (say 15 minutes) before extra fees apply. The ticket state machine gains a transition; the gates call lot.pay and lot.exit separately.

9. Gate hardware failures. Keep gates as thin adapters. A failed printer means admit must not occupy a spot without a ticket; claim, print, and on print failure release (another compensating action).

Common mistakes

• Starting with classes before requirements. Without asking about vehicle-to-spot fit, you cannot write the allocator.
• A subclass per vehicle type with no behaviour. Use an enum.
• Pricing inside Ticket or ParkingLot as an if-else chain on vehicle type. Every tariff change then edits core code. Use a strategy.
• Freeing the spot before payment succeeds. If the card is declined, the car is still physically there but the spot shows free and gets assigned to someone else.
• Calling isFree() then occupy() as two steps. That is the check-then-act race.
• Using double for money.
• Calling Instant.now() everywhere, making fee tests slow or impossible.
• Making everything a Singleton, then being unable to test two scenarios in one run.
• Forgetting the duplicate-plate rule, which also gives you lost-ticket lookup for free.
• Doing slow work while holding a lock, for example calling a payment gateway inside a lot-wide synchronized block. Every other gate stalls for the network round trip. Our code holds only the ticket's lock during payment.

Interview questions

Q1. Why did you use the Strategy pattern for pricing instead of an if-else on vehicle type?

Pricing rules change far more often than parking logic: weekends, festivals, promotions. With a strategy, each scheme is a separate class behind one interface, so adding a scheme means adding a class and not editing the lot. It also makes each scheme testable on its own with a fake ticket and a fixed time.

Q2. How do you prevent two gates from assigning the same spot?

The assignment must be an atomic check-and-set. I give each spot an AtomicReference and claim it with compareAndSet(null, vehicle); only one caller can succeed while the spot is free, and the loser tries the next candidate. A single synchronized method on the lot also works and is simpler, at the cost of serialising all gates.

Q3. What is the locking granularity in your design, and why?

The finest possible: one spot, using lock-free CAS. Exits lock only the ticket being paid. This means gates never wait on each other unless they target the same spot or ticket, which is rare. I would still start with one coarse lock if the lot were small, because simplicity is worth more than throughput nobody needs.

Q4. Why is Vehicle not an abstract class with Car, Bike and Truck subclasses?

The subclasses would have no different behaviour; they only differ in which spot size they need. An enum with a field holds that difference in one line, avoids instanceof checks, and adding a type is one enum constant. If a type later gains real behaviour, I can introduce a class then.

Q5. How do display boards stay up to date?

They are observers. The lot keeps a list of AvailabilityListener objects and calls each one after a park or exit with the new free count for that floor and size. New consumers, such as a mobile app feed, register as listeners without changes to the lot.

Q6. What happens if payment fails at the exit?

The ticket stays ACTIVE and the spot stays occupied, because the car is still physically there. The driver can retry with another method. The spot is freed only after markPaid succeeds.

Q7. How would you add reservations?

A spot gains a third state besides free and occupied: held for a reservation id until an expiry time. Reserving is a CAS from free to held; arrival with the right id is a CAS from held to occupied; a scheduled task returns expired holds to free. Allocation strategies skip held spots.

Q8. Would you make ParkingLot a Singleton?

No. There is one lot per deployment, but I enforce that by creating one in main and passing it to the gates. A Singleton is global state that makes tests interfere with each other and makes a multi-lot extension a rewrite.

Q9. How do you test the fee calculation?

Inject a Clock. The test creates a manual clock, parks a car, advances 61 minutes and asserts Rs 100, then tests boundaries: 0, 60, 61, 120 and 121 minutes. Without the injected clock the test would have to sleep or would be flaky.

Q10. The lot now has 5 application servers sharing one database. What changes?

In-memory atomics only protect one process, so the database becomes the source of truth for spot state. Allocation becomes a conditional update, WHERE id = ? AND vehicle IS NULL, checking that exactly one row changed, or an insert into an assignments table with a unique constraint on the spot. Boards are fed from events published after commit.

Q11. How do you handle a lost ticket?

Look up the active ticket by number plate, which the lot already indexes to reject duplicate entries. Charge using a lost-ticket strategy, typically a full-day rate. If the plate is not found, staff handle it manually.

Q12. Where would you add logging and metrics?

As another observer on park and exit events, or as a decorator around the lot's public methods. Keeping them out of the core methods means business logic stays readable and metrics can change independently.

Q13. How does the allocator choose a spot, and how would you make it faster for a 5,000-spot lot?

It lists free spots of the smallest fitting size, lowest floor first, and tries them in order. Scanning 5,000 spots per arrival is still microseconds, but for scale I would keep a concurrent free-set per floor and size (for example a ConcurrentSkipListSet ordered by distance) and pollFirst() from it, which is atomic and O(log n).

Key takeaways

• Spend the first minutes on clarifying questions; each answer adds or removes a class.
• Separate stable data (spots, tickets) from changing rules (pricing, allocation) and put the rules behind Strategy interfaces.
• Use Observer for boards and other consumers of availability changes, so new consumers need no changes to the lot.
• Use an enum, not a class hierarchy, when types differ only in values.
• The core correctness problem is the check-then-act race at the gates; fix it with an atomic claim per spot, or one lock if simplicity matters more.
• Free the spot only after payment succeeds, and make a paid ticket unusable.
• Inject the clock so fees are testable, and store money as integers.
• Have a one-line answer for each extension: EV spots, reservations, passes, lost tickets, multiple servers.

Next lesson

Continue with Design an elevator system.