Chapter 28 of 33

LLD: Design a Parking Lot

"Design a parking lot" is probably the most asked Low-Level Design question in Indian placement interviews. It looks simple, everyone has seen a mall parking, yet it tests everything from the chapter Introduction to Low-Level Design: finding entities, assigning responsibilities, using enums and interfaces, applying the Strategy pattern, and handling two cars racing for the last spot. In this chapter we solve it step by step, exactly the way you should in an interview, and finish with complete Java 17 code that compiles and runs.

Goal: design the classes of a multi-floor parking lot that issues tickets at entry, assigns a suitable free spot, charges a fee at exit, shows availability, and stays correct when many vehicles arrive at once.


Step 1: Clarify Requirements

Never start coding immediately. Ask questions and write the agreed scope down.

Functional Requirements

  1. The lot has multiple floors; each floor has spots of different sizes: small, medium, large.

  2. It supports bikes, cars and trucks. A bike fits any spot, a car fits medium or large, a truck needs a large spot.

  3. At entry, the system finds a suitable free spot and issues a ticket (ticket ID, vehicle, spot, entry time). If nothing fits, the vehicle is turned away.

  4. At exit, the driver hands in the ticket; the system computes the fee and frees the spot. A ticket can be used only once.

  5. The system can show free spots per floor and type (for display boards).

Non-Functional Requirements

  • Correctness under concurrency: several entry gates work in parallel; two vehicles must never get the same spot.

  • Extensibility: pricing rules and spot-assignment rules will change (weekend rates, EV spots, VIP floors).

Out of Scope (say it explicitly)

Online reservations, real payment gateway integration, number-plate recognition cameras and multiple parking lots. Mentioning these shows you thought about them; leaving them out keeps the 45-minute round focused.


Step 2: Identify Entities

Underline the nouns: parking lot, floor, spot, spot type, vehicle, vehicle type, ticket, fee, gate, display board. Now decide what each becomes.

Noun

Becomes

Responsibility

Vehicle type

enum VehicleType

Fixed set: BIKE, CAR, TRUCK

Spot type

enum SpotType

Fixed set plus the rule "which vehicle fits me" (canFit)

Vehicle

record Vehicle

Number plate + type; pure data

Spot

class ParkingSpot

Owns its occupied/free state; occupy and release safely

Floor

class ParkingFloor

Holds spots; counts free spots by type

Ticket

class Ticket (immutable)

Records who parked where and when

Assignment rule

interface SpotAllocationStrategy

Chooses a spot; swappable

Fee rule

interface PricingStrategy

Computes fee; swappable

Parking lot

class ParkingLot (facade)

Entry point for gates: park, unpark, availability

Why is Vehicle a record with a type, not an inheritance tree (Car extends Vehicle)? In this problem, bikes, cars and trucks have no different behaviour; only their size category differs. A class hierarchy would add three classes that do nothing. If later a vehicle type gains real behaviour (for example, an electric car that needs charging), introducing a subclass or a capability interface then is reasonable. Interviewers accept both approaches if you justify the choice.


Step 3: Class Diagram

                    +----------------------------------+
                    |            ParkingLot            |   (facade used by gates)
                    +----------------------------------+
                    | - floors: List<ParkingFloor>     |
                    | - allocator: SpotAllocationStrat.|
                    | - pricing: PricingStrategy       |
                    | - activeTickets: Map<id, Ticket> |
                    +----------------------------------+
                    | + park(vehicle, time): Ticket    |
                    | + unpark(ticketId, time): int    |
                    | + availability(): String         |
                    +----------------------------------+
                      ◆ 1..*            |  uses           |  uses
                      |                 v                 v
              +---------------+   <<interface>>          <<interface>>
              | ParkingFloor  |   SpotAllocationStrategy  PricingStrategy
              +---------------+          ^                        ^
              | - spots       |          :                        :
              +---------------+   NearestSmallestFit        HourlyPricing
                      ◆ 1..*
                      |
              +-------------------------+          +-------------------+
              |       ParkingSpot       |          |      Ticket       |
              +-------------------------+          +-------------------+
              | - id, type: SpotType    |<---------| - id              |
              | - vehicle: Vehicle      |          | - vehicle, spot   |
              | + tryOccupy(v): boolean |          | - entryTime       |
              | + release()             |          +-------------------+
              +-------------------------+

  ◆ = composition (floors and spots do not exist without the lot)
  :  = implements (realisation)

Step 4: Spot Variation Points

Ask: "what will the business change next?" Two answers stand out, and each gets an interface (the Strategy pattern):

  • How to choose a spot. Today: lowest floor first, smallest spot that fits (so a bike does not waste a truck spot). Tomorrow: nearest to the lift, or EV spots first for electric cars.

  • How to price. Today: per started hour, minimum one hour, rate by vehicle type. Tomorrow: flat weekend rate, free first 30 minutes, monthly passes.

Because ParkingLot receives both strategies through its constructor, changing a rule means writing a new class and passing it in. ParkingLot itself never changes (Open/Closed and Dependency Inversion).


Step 5: The Entry and Exit Flows

ENTRY                                         EXIT
Gate          ParkingLot        Allocator      Gate        ParkingLot       Pricing
 |  park(v,t)     |                 |           | unpark(id,t)  |              |
 |--------------->| allocate(floors,v)          |------------->| remove ticket from map
 |                |---------------->|           |              | (null -> reject)
 |                |   spot.tryOccupy(v)          |              | spot.release()
 |                |<---- spot -----|           |              | fee(type, duration)
 |                | create Ticket, store in map |              |------------->|
 |<--- ticket ----|                             |<---- fee ----|<-------------|
 |  (or ParkingFullException if no spot)        |

Step 6: Complete Code (Java 17)

Everything is in one file so you can compile and run it directly (javac ParkingLotDemo.java then java ParkingLotDemo). In a real project each type would get its own file. Times are passed in explicitly instead of reading the system clock, which makes the program repeatable and easy to test.

import java.time.Duration;
import java.time.LocalDateTime;
import java.util.ArrayList;
import java.util.List;
import java.util.Map;
import java.util.Optional;
import java.util.concurrent.ConcurrentHashMap;
import java.util.concurrent.CountDownLatch;
import java.util.concurrent.atomic.AtomicInteger;

// ---------- Enums: fixed categories ----------
enum VehicleType { BIKE, CAR, TRUCK }

enum SpotType {
    SMALL, MEDIUM, LARGE;

    // Which vehicles may use this spot type?
    boolean canFit(VehicleType v) {
        return switch (this) {
            case SMALL -> v == VehicleType.BIKE;
            case MEDIUM -> v == VehicleType.BIKE || v == VehicleType.CAR;
            case LARGE -> true;
        };
    }
}

// ---------- Entities ----------
record Vehicle(String number, VehicleType type) {}

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

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

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

    // Atomic check-and-set: only one thread can win a free spot
    synchronized boolean tryOccupy(Vehicle v) {
        if (vehicle != null || !type.canFit(v.type())) return false;
        vehicle = v;
        return true;
    }

    synchronized void release() { vehicle = null; }
}

class ParkingFloor {
    private final int number;
    private final List<ParkingSpot> spots = new ArrayList<>();

    ParkingFloor(int number, int small, int medium, int large) {
        this.number = number;
        int n = 1;
        for (int i = 0; i < small; i++) spots.add(new ParkingSpot(number + "-S" + n++, SpotType.SMALL));
        for (int i = 0; i < medium; i++) spots.add(new ParkingSpot(number + "-M" + n++, SpotType.MEDIUM));
        for (int i = 0; i < large; i++) spots.add(new ParkingSpot(number + "-L" + n++, SpotType.LARGE));
    }

    int number() { return number; }
    List<ParkingSpot> spots() { return spots; }

    long freeCount(SpotType t) {
        return spots.stream().filter(s -> s.type() == t && s.isFree()).count();
    }
}

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

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

    String id() { return id; }
    Vehicle vehicle() { return vehicle; }
    ParkingSpot spot() { return spot; }
    LocalDateTime entryTime() { return entryTime; }
}

// ---------- Strategies: the variation points ----------
interface SpotAllocationStrategy {
    Optional<ParkingSpot> allocate(List<ParkingFloor> floors, Vehicle v);
}

// Lowest floor first, and the smallest spot type that fits (keeps big spots for big vehicles)
class NearestSmallestFitStrategy implements SpotAllocationStrategy {
    public Optional<ParkingSpot> allocate(List<ParkingFloor> floors, Vehicle v) {
        for (ParkingFloor f : floors) {
            for (SpotType t : SpotType.values()) {          // SMALL, MEDIUM, LARGE in order
                if (!t.canFit(v.type())) continue;
                for (ParkingSpot s : f.spots()) {
                    if (s.type() == t && s.tryOccupy(v)) return Optional.of(s);
                }
            }
        }
        return Optional.empty();
    }
}

interface PricingStrategy {
    int fee(VehicleType type, Duration parked);
}

// Pay per started hour, minimum one hour
class HourlyPricing implements PricingStrategy {
    private final Map<VehicleType, Integer> ratePerHour =
            Map.of(VehicleType.BIKE, 20, VehicleType.CAR, 40, VehicleType.TRUCK, 100);

    public int fee(VehicleType type, Duration parked) {
        long minutes = parked.toMinutes();
        long hours = Math.max(1, (minutes + 59) / 60);      // ceiling division
        return (int) hours * ratePerHour.get(type);
    }
}

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

// ---------- Facade: what the entry and exit gates call ----------
class ParkingLot {
    private final List<ParkingFloor> floors;
    private final SpotAllocationStrategy allocator;
    private final PricingStrategy pricing;
    private final Map<String, Ticket> activeTickets = new ConcurrentHashMap<>();
    private final AtomicInteger ticketSeq = new AtomicInteger(1000);

    ParkingLot(List<ParkingFloor> floors, SpotAllocationStrategy allocator, PricingStrategy pricing) {
        this.floors = floors;
        this.allocator = allocator;
        this.pricing = pricing;
    }

    Ticket park(Vehicle v, LocalDateTime now) {
        ParkingSpot spot = allocator.allocate(floors, v)
                .orElseThrow(() -> new ParkingFullException("No spot for " + v.type() + " " + v.number()));
        Ticket t = new Ticket("T" + ticketSeq.incrementAndGet(), v, spot, now);
        activeTickets.put(t.id(), t);
        return t;
    }

    int unpark(String ticketId, LocalDateTime now) {
        Ticket t = activeTickets.remove(ticketId);           // remove() makes a ticket single-use
        if (t == null) throw new IllegalArgumentException("Invalid or already used ticket " + ticketId);
        t.spot().release();
        return pricing.fee(t.vehicle().type(), Duration.between(t.entryTime(), now));
    }

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

public class ParkingLotDemo {
    public static void main(String[] args) throws InterruptedException {
        ParkingLot lot = new ParkingLot(
                List.of(new ParkingFloor(0, 1, 2, 1), new ParkingFloor(1, 1, 1, 0)),
                new NearestSmallestFitStrategy(), new HourlyPricing());
        LocalDateTime nine = LocalDateTime.of(2026, 11, 2, 9, 0);

        System.out.println(lot.availability());
        Ticket bike = lot.park(new Vehicle("KA01AB1234", VehicleType.BIKE), nine);
        Ticket car = lot.park(new Vehicle("MH12CD5678", VehicleType.CAR), nine);
        Ticket truck = lot.park(new Vehicle("DL03EF9012", VehicleType.TRUCK), nine);
        for (Ticket t : List.of(bike, car, truck))
            System.out.println(t.id() + " " + t.vehicle().number() + " -> spot " + t.spot().id());

        try {
            lot.park(new Vehicle("TN09GH3456", VehicleType.TRUCK), nine);
        } catch (ParkingFullException e) {
            System.out.println("Rejected: " + e.getMessage());
        }

        System.out.println("Car fee after 2h 10m: Rs " + lot.unpark(car.id(), nine.plusMinutes(130)));
        System.out.println("Bike fee after 25m: Rs " + lot.unpark(bike.id(), nine.plusMinutes(25)));
        try {
            lot.unpark(car.id(), nine.plusHours(3));
        } catch (IllegalArgumentException e) {
            System.out.println("Rejected: " + e.getMessage());
        }
        System.out.println(lot.availability());

        // Concurrency check: 8 cars arrive at the same instant
        CountDownLatch start = new CountDownLatch(1);
        AtomicInteger parked = new AtomicInteger();
        AtomicInteger rejected = new AtomicInteger();
        List<Thread> threads = new ArrayList<>();
        for (int i = 0; i < 8; i++) {
            String plate = "UP16XY" + (1000 + i);
            Thread th = new Thread(() -> {
                try {
                    start.await();
                    lot.park(new Vehicle(plate, VehicleType.CAR), nine);
                    parked.incrementAndGet();
                } catch (ParkingFullException e) {
                    rejected.incrementAndGet();
                } catch (InterruptedException e) {
                    Thread.currentThread().interrupt();
                }
            });
            threads.add(th);
            th.start();
        }
        start.countDown();                                   // release all threads together
        for (Thread th : threads) th.join();
        System.out.println("Race: parked=" + parked + ", rejected=" + rejected);
        System.out.println(lot.availability());
    }
}

Output:

Floor 0: SMALL=1 MEDIUM=2 LARGE=1
Floor 1: SMALL=1 MEDIUM=1 LARGE=0
T1001 KA01AB1234 -> spot 0-S1
T1002 MH12CD5678 -> spot 0-M2
T1003 DL03EF9012 -> spot 0-L4
Rejected: No spot for TRUCK TN09GH3456
Car fee after 2h 10m: Rs 120
Bike fee after 25m: Rs 20
Rejected: Invalid or already used ticket T1002
Floor 0: SMALL=1 MEDIUM=2 LARGE=0
Floor 1: SMALL=1 MEDIUM=1 LARGE=0
Race: parked=3, rejected=5
Floor 0: SMALL=1 MEDIUM=0 LARGE=0
Floor 1: SMALL=1 MEDIUM=0 LARGE=0

Reading the Output

  • The bike gets 0-S1 (the small spot), the car 0-M2 (the first medium spot), the truck 0-L4, the only large spot. The second truck is rejected because floor 1 has no large spot: the "smallest spot that fits" rule kept the large spot available for a truck instead of giving it to the bike or car.

  • The car stayed 2 hours 10 minutes. Started hours = ⌈130 / 60⌉ = 3, so the fee is 3 × ₹40 = ₹120. The bike stayed 25 minutes; the minimum charge is 1 hour = ₹20.

  • Using ticket T1002 a second time is rejected, because unpark removes the ticket from the map.

  • In the race, 8 threads try to park cars at the same instant. Exactly 3 car-capable spots are free (0-M2, 0-M3, 1-M2; the small spots do not fit cars), and exactly 3 succeed. No spot is given twice. Running it repeatedly always gives the same counts.


Step 7: Concurrency, Explained

The dangerous moment is check-then-act: thread A sees spot M2 is free, thread B sees it is free, both set themselves as the occupant. That is a race condition.

WITHOUT locking                         WITH synchronized tryOccupy
A: isFree(M2)? yes                      A: lock M2, free? yes, occupy, unlock -> true
B: isFree(M2)? yes                      B: lock M2, free? no, unlock          -> false
A: occupy M2                            B moves on to the next spot
B: occupy M2   <-- two cars, one spot!

Our design makes the check and the update one atomic operation inside ParkingSpot.tryOccupy, locking only that single spot. This is finer-grained than locking the whole lot (synchronized park()), so different gates can assign different spots in parallel. Other shared state is also thread-safe: tickets live in a ConcurrentHashMap, IDs come from an AtomicInteger, and activeTickets.remove() guarantees only one exit can redeem a ticket.

What if the lot runs on several servers? In-memory locks no longer help. The spot state moves to a database, and the atomic step becomes a conditional update, for example UPDATE spot SET vehicle_no = ? WHERE id = ? AND vehicle_no IS NULL, which succeeds for exactly one caller (the database row lock does the job of synchronized). This links LLD back to the consistency ideas in Consistency Models.


Step 8: Extensions Interviewers Ask About

New requirement

Change in this design

Weekend flat rate

New PricingStrategy class, or a composite that picks a strategy by day

EV charging spots

Add SpotType.EV (with its canFit rule) and an allocation strategy that tries EV spots first for electric vehicles

Live display boards on each floor

Observer pattern: boards subscribe; ParkingLot publishes an event after each park/unpark

Multiple payment modes (cash, UPI, card)

PaymentMethod interface with one class per mode; exit flow calls it after computing the fee

Lost ticket

Look up the active ticket by vehicle number (add a second map) and charge a lost-ticket penalty via pricing

Only one ParkingLot instance

Could be a Singleton, but creating one instance at startup and injecting it is easier to test

Notice that none of these requires editing ParkingSpot, ParkingFloor or Ticket. That is the payoff of good LLD.


Common Mistakes

  • Starting with code before agreeing on vehicle and spot types and the fit rules.

  • Hard-coding pricing inside unpark with if (type == CAR) ..., so every rate change edits core logic.

  • Separate isFree() and occupy() calls from the outside: a race condition even if each method is synchronized on its own.

  • Rounding duration down (2 h 10 min billed as 2 h) when the stated rule is "per started hour"; always confirm the rounding rule.

  • Reusable tickets: forgetting to invalidate a ticket after exit.

  • Giving a bike the large spot because it was "first free", which turns away a truck later.

  • Over-engineering: separate classes for Car, Bike, Truck, SmallSpot, MediumSpot and LargeSpot that contain no different behaviour.


Interview Questions

1. Which design patterns did you use in the parking lot, and why?

Strategy for spot allocation and pricing, because these rules change often and must be swappable without touching ParkingLot. A facade (ParkingLot) gives gates a simple park/unpark API. Observer is the natural extension for display boards, and a Factory could create vehicles or spots from input strings.

2. How do you make sure two entry gates never assign the same spot?

Make check-and-occupy a single atomic operation. In memory, a synchronized tryOccupy on each spot (or a compare-and-set on an atomic reference). Across servers, a conditional database update such as UPDATE ... WHERE id = ? AND vehicle_no IS NULL, and treat "0 rows updated" as "spot taken, try another".

3. A car parks from 10:05 to 13:06 at ₹40 per started hour. What is the fee?

Duration = 3 h 1 min = 181 minutes. Started hours = ⌈181 / 60⌉ = 4. Fee = 4 × ₹40 = ₹160.

4. Why lock each spot rather than the whole parking lot?

A single global lock serialises all gates, so only one vehicle can be processed at a time. Per-spot locks let gates allocate different spots in parallel and contend only when they try the same spot. With our "nearest first" strategy, gates arriving together do try the same first spot, but each lock is held only for a tiny check-and-set, and the loser simply moves on to the next spot. The trade-off is slightly more complex reasoning (for example, the availability counts are a snapshot that may change while being read).

5. How would you find a free spot without scanning all spots?

Keep, per floor and spot type, a pool of free spots. With a concurrent queue (for example ConcurrentLinkedQueue), allocation polls from the right pool and release offers the spot back, both O(1). If you need "nearest spot first", use a priority queue ordered by distance instead, which costs O(log n) per operation. Scanning is fine for an interview-sized lot, but pools scale to thousands of spots.


Summary

  • Start with requirements: floors, spot sizes, vehicle types and fit rules, entry/exit flow, pricing rule, concurrency, and what is out of scope.

  • Entities: VehicleType, SpotType (enums), Vehicle, ParkingSpot, ParkingFloor, Ticket, and the ParkingLot facade.

  • Put changeable rules behind Strategy interfaces: spot allocation and pricing.

  • Use "smallest spot that fits" to avoid wasting large spots.

  • Make occupy an atomic check-and-set per spot; use a concurrent map for tickets and remove a ticket on exit so it is single-use.

  • At scale, the same atomic step becomes a conditional database update.

A parking lot design is judged on three things: clean entities, swappable rules, and never giving one spot to two cars.