Design a Parking Lot (LLD Interview) in Java
A parking lot program with spot types, a nearest-spot index for each gate, a ticket from entry to exit, and prices you can swap. The Java program on this page proves that cars racing for the last spot never share a spot.
Where it shows up
A classic warm-up question in low level design (LLD) and machine coding rounds. LLD means designing the classes and methods of one program. System design is the version with many servers. Interviewers like it because it stretches well: electric car charging, many gates, reservations, a database, many lots.
Two courses by the author of this page:
770 lessons · 18 free to read
₹1,111 in India · $25 elsewhere, once
Get System DesignYou own this course
214 lessons · 10 free to read
₹1,333 in India · $35 elsewhere, once
Get Generative AI and Agentic AIYou own this course
Spec sheetParking Lot
- 01Core classes
- ParkingLot, SpotIndex, ParkingSpot, Vehicle, FitRules, Ticket, PricingStrategy, PaymentProcessor, Clock
- 02Design patterns
- Strategy, Facade, State, Compare-and-set, Passing time in
- 03Enums
- VehicleType, SpotType, TicketStatus
- 04Key methods
- 5 signatures, with the code skeleton
worked through below, with the maths
Why this is asked
It checks four skills in one small problem. First, can you turn a loose story into a few classes, each with one job? Second, can you spot the parts that change, like the price rule, and put them behind an interface so new rules do not touch old code? An interface is a list of methods that many classes can provide in their own way. Third, can you find a free spot fast, without checking every spot for every car? Fourth, can you handle threads? A thread is one line of work that runs alongside others. Two gates are two threads. If two cars arrive at two gates for the last spot, a weak design gives both cars that spot. Most candidates mention a lock. Few can show why their fix works. This page shows it with a test.
Requirements
Functional
- A vehicle comes in at an entry gate and gets a ticket. The ticket records the vehicle, its spot, the gate and the entry time.
- Spots come in types: MOTORCYCLE, COMPACT, LARGE and ELECTRIC (with a charger).
- Each vehicle type may use only some spot types, smallest first. A motorcycle may use a motorcycle, compact or large spot. A car may use compact or large. A truck needs large. An electric car tries a charger spot first, then compact or large.
- Give the nearest free spot that fits, measured from the gate the car came in at.
- At exit, work out the fee from the time parked, take payment, then free the spot.
- Several entry and exit gates work at once.
- Show how many spots of each type are free.
- Refuse entry cleanly when no spot fits. Refuse a number plate that is already inside.
Constraints & non-functional
- Two cars must never get one spot, even when they arrive at one instant at different gates.
- Finding a spot must not check every spot. Keep the free spots in a sorted index, so the nearest one comes out in about log n steps (n is the number of free spots of that type).
- Price rules must be swappable without changing the lot code.
- A ticket can be paid once. Scanning it twice, or at two lanes at once, must not charge twice.
- The spot stays taken until payment succeeds.
- Time comes from a Clock passed in, so tests can move time forward without waiting.
- Everything is in memory. A database and many lots are follow-ups, covered in the FAQ.
Core classes & entities
ParkingLot
The one entry point every gate calls. park() finds a spot and makes a ticket. exit() prices the stay, takes payment and frees the spot. It hands the real work to the spot index, the pricing rule and the payment processor.
attrs: index: SpotIndex, pricing: PricingStrategy, clock: Clock, tickets: ConcurrentHashMap<String, Ticket>, platesInside: Set<String>
methods: park(vehicle, gate): Ticket, exit(ticketId, payment): long, free(type): int
SpotIndex
Keeps the free spots, sorted by distance, one sorted set for each gate and each spot type. take() pulls the nearest free spot for a gate. giveBack() puts a spot back in every gate's set.
attrs: byGate: List<Map<SpotType, ConcurrentSkipListSet<ParkingSpot>>>
methods: take(gate, type, vehicle): ParkingSpot, giveBack(spot), freeCount(gate, type): int
ParkingSpot
One physical spot. It knows its type and its distance from each gate. It holds its current vehicle in an AtomicReference, and tryOccupy() is the single place that decides who gets the spot.
attrs: id, type: SpotType, distanceFromGate: int[], occupant: AtomicReference<Vehicle>
methods: tryOccupy(vehicle): boolean, release(), occupant(): Vehicle
Vehicle
A number plate and a vehicle type. It is a Java record, a small class that only holds values. Vehicle types differ only in which spots they may use, so one class with a type field is enough. A class per vehicle type would add code and teach nothing.
attrs: plate, type: VehicleType
FitRules
For each vehicle type, the spot types it may use, in the order to try them. Smallest fit first, so large spots stay free for trucks.
methods: preference(vehicleType): List<SpotType>
Ticket
Made at entry and settled at exit. It records the vehicle, the spot, the gate and the entry time. Its status moves ACTIVE, then EXITING, then PAID, and each move is a compare-and-set, so only one exit can run.
attrs: id, vehicle, spot, gate, entry: Instant, status: AtomicReference<TicketStatus>, paidCents
PricingStrategy
Works out the fee from the spot type and the time parked. HourlyPricing counts any part of an hour as a full hour, after a free grace period. FlatDailyPricing charges per started day.
methods: feeCents(spotType, parked): long
PaymentProcessor
Takes the payment and says yes or no. Card, cash or app payments each become one class behind this interface.
methods: charge(ticketId, cents): boolean
Clock
Gives the current time. Tests use a FakeClock that they move forward by exact amounts.
methods: now(): Instant
Relationships
- ParkingLot → composition → SpotIndex. The lot owns its index of free spots.
- SpotIndex → aggregation → ParkingSpot. Every gate's sorted sets point at one shared set of spot objects. The spot decides who owns it. The sets only suggest.
- ParkingLot → composition → Ticket. The lot keeps every ticket it issued, looked up by id.
- Ticket → association → ParkingSpot. The ticket names its spot, so exit frees exactly that spot.
- Ticket → association → Vehicle. The ticket names the vehicle it was issued for.
- ParkingLot → association → PricingStrategy. The price rule is passed in, so it can change without touching the lot.
- ParkingLot → association → FitRules. park() asks which spot types to try, in order.
- PricingStrategy → implements → HourlyPricing. One class per price rule. FlatDailyPricing is the other.
- ParkingLot → association → PaymentProcessor. Passed to exit(), so each lane can use its own payment method.
- ParkingLot → association → Clock. All times come from the clock passed in.
Design patterns used
Strategy in PricingStrategy and PaymentProcessor
A strategy is a rule kept behind an interface, so you can swap one rule for another. The price rule is the part interviewers change most. The program swaps hourly pricing for a flat daily price, and the lot code does not change.
Facade in ParkingLot.park and ParkingLot.exit
A facade is one simple front door to a group of classes. Gates call two methods. They never see the index, the fit rules or the ticket states.
State in Ticket status: ACTIVE, EXITING, PAID
The ticket moves through fixed steps, and each move checks the step it came from. So a paid ticket cannot be paid again, and a failed payment puts it back to ACTIVE.
Compare-and-set in ParkingSpot.tryOccupy and the ticket status
Compare-and-set (CAS) is one step the processor does without a gap: set the value only if it still holds what I expect. If two threads try at once, exactly one sees true. The program runs 1,000 rounds of 32 cars racing for 1 spot, and every round has 1 winner.
Passing time in in Clock with FakeClock
Fees depend on time. With the clock passed in, a test can say 61 minutes passed and check the fee at once.
Enums
Key API / methods
Ticket park(Vehicle v, int gate)Tries each fitting spot type in order, smallest first. For each type, takes the nearest free spot for this gate. Throws LotFullException if nothing fits.
long exit(String ticketId, PaymentProcessor pay)Moves the ticket from ACTIVE to EXITING with a compare-and-set, works out the fee and charges it. On success the ticket becomes PAID and the spot goes back to every gate's index. On failure the ticket goes back to ACTIVE and the spot stays taken.
ParkingSpot SpotIndex.take(int gate, SpotType type, Vehicle v)Pulls the nearest spot from this gate's sorted set with pollFirst(), then calls tryOccupy(). If another gate won that spot a moment earlier, it tries the next one.
boolean ParkingSpot.tryOccupy(Vehicle v)occupant.compareAndSet(null, v). True for exactly one caller. This one line is what stops two cars getting one spot.
long PricingStrategy.feeCents(SpotType type, Duration parked)The fee in cents. It depends only on its inputs, so it is easy to test.
Code skeleton
import java.time.Duration;
import java.time.Instant;
import java.util.*;
import java.util.concurrent.*;
import java.util.concurrent.atomic.*;
// ---------- Enums ----------
enum VehicleType { MOTORCYCLE, CAR, TRUCK, ELECTRIC_CAR }
enum SpotType { MOTORCYCLE, COMPACT, LARGE, ELECTRIC }
enum TicketStatus { ACTIVE, EXITING, PAID }
record Vehicle(String plate, VehicleType type) {}
// ---------- Fit rules: which spot types a vehicle may use, best fit first ----------
// Smallest fitting type first, so large spots stay free for trucks.
final class FitRules {
static List<SpotType> preference(VehicleType t) {
return switch (t) {
case MOTORCYCLE -> List.of(SpotType.MOTORCYCLE, SpotType.COMPACT, SpotType.LARGE);
case CAR -> List.of(SpotType.COMPACT, SpotType.LARGE);
case TRUCK -> List.of(SpotType.LARGE);
case ELECTRIC_CAR -> List.of(SpotType.ELECTRIC, SpotType.COMPACT, SpotType.LARGE); // no charger outside ELECTRIC
};
}
}
// ---------- A spot: the one place that decides who owns it ----------
final class ParkingSpot {
final String id; final SpotType type; final int[] distanceFromGate;
private final AtomicReference<Vehicle> occupant = new AtomicReference<>();
ParkingSpot(String id, SpotType type, int[] distanceFromGate) { this.id = id; this.type = type; this.distanceFromGate = distanceFromGate; }
// compare-and-set: succeeds only if the spot is empty right now. Exactly one caller can win.
boolean tryOccupy(Vehicle v) { return occupant.compareAndSet(null, v); }
void release() { occupant.set(null); }
Vehicle occupant() { return occupant.get(); }
public String toString() { return id; }
}
// ---------- Free-spot index: per gate, per type, nearest first ----------
// Each gate keeps its own sorted set of free spots for each type, ordered by distance from that gate.
// pollFirst() removes and returns the nearest one in O(log n). Two gates can pull the same spot from
// their own sets at the same moment, so the spot's compare-and-set has the final say.
final class SpotIndex {
private final List<Map<SpotType, ConcurrentSkipListSet<ParkingSpot>>> byGate = new ArrayList<>();
SpotIndex(List<ParkingSpot> spots, int gates) {
for (int g = 0; g < gates; g++) {
final int gate = g;
Map<SpotType, ConcurrentSkipListSet<ParkingSpot>> m = new EnumMap<>(SpotType.class);
for (SpotType t : SpotType.values())
m.put(t, new ConcurrentSkipListSet<>(Comparator.<ParkingSpot>comparingInt(s -> s.distanceFromGate[gate]).thenComparing(s -> s.id)));
for (ParkingSpot s : spots) m.get(s.type).add(s);
byGate.add(m);
}
}
ParkingSpot take(int gate, SpotType type, Vehicle v) {
ConcurrentSkipListSet<ParkingSpot> free = byGate.get(gate).get(type);
while (true) {
ParkingSpot s = free.pollFirst(); // nearest free spot of this type, for this gate
if (s == null) return null; // none left of this type
if (s.tryOccupy(v)) { // we won the spot
for (int g = 0; g < byGate.size(); g++) if (g != gate) byGate.get(g).get(type).remove(s);
return s;
}
// another gate won it a moment ago; it is already gone from our set, try the next one
}
}
void giveBack(ParkingSpot s) { s.release(); for (var m : byGate) m.get(s.type).add(s); }
int freeCount(int gate, SpotType t) { return byGate.get(gate).get(t).size(); } // size() walks the set: fine for a display, not a hot path
}
// ---------- Pricing: a Strategy, so the rule can change without touching the lot ----------
interface PricingStrategy { long feeCents(SpotType type, Duration parked); }
final class HourlyPricing implements PricingStrategy {
private final Map<SpotType, Long> centsPerHour; private final Duration grace;
HourlyPricing(Map<SpotType, Long> centsPerHour, Duration grace) { this.centsPerHour = centsPerHour; this.grace = grace; }
public long feeCents(SpotType type, Duration parked) {
if (parked.compareTo(grace) <= 0) return 0; // left inside the grace period
long minutes = parked.toMinutes();
long hours = (minutes + 59) / 60; // any part of an hour counts as a full hour
return hours * centsPerHour.get(type);
}
}
final class FlatDailyPricing implements PricingStrategy {
private final long centsPerDay;
FlatDailyPricing(long centsPerDay) { this.centsPerDay = centsPerDay; }
public long feeCents(SpotType type, Duration parked) { return ((parked.toMinutes() + 1439) / 1440) * centsPerDay; }
}
interface PaymentProcessor { boolean charge(String ticketId, long cents); }
interface Clock { Instant now(); }
final class FakeClock implements Clock {
private Instant t = Instant.parse("2026-10-07T09:00:00Z");
public synchronized Instant now() { return t; }
synchronized void advance(Duration d) { t = t.plus(d); }
}
// ---------- Ticket: created at entry, settled at exit ----------
final class Ticket {
final String id; final Vehicle vehicle; final ParkingSpot spot; final int gate; final Instant entry;
final AtomicReference<TicketStatus> status = new AtomicReference<>(TicketStatus.ACTIVE);
volatile long paidCents;
Ticket(String id, Vehicle v, ParkingSpot s, int gate, Instant entry) { this.id = id; this.vehicle = v; this.spot = s; this.gate = gate; this.entry = entry; }
}
final class LotFullException extends RuntimeException {
private static final long serialVersionUID = 1L;
LotFullException(String m) { super(m); }
}
// ---------- The lot: one entry point for every gate ----------
final class ParkingLot {
private final SpotIndex index; private final PricingStrategy pricing; private final Clock clock;
private final Map<String, Ticket> tickets = new ConcurrentHashMap<>();
private final Set<String> platesInside = ConcurrentHashMap.newKeySet();
private final AtomicLong nextId = new AtomicLong(1);
ParkingLot(List<ParkingSpot> spots, int gates, PricingStrategy pricing, Clock clock) {
this.index = new SpotIndex(spots, gates); this.pricing = pricing; this.clock = clock;
}
Ticket park(Vehicle v, int gate) {
if (!platesInside.add(v.plate())) throw new IllegalStateException(v.plate() + " is already inside");
for (SpotType t : FitRules.preference(v.type())) {
ParkingSpot s = index.take(gate, t, v);
if (s != null) {
Ticket tk = new Ticket("T" + nextId.getAndIncrement(), v, s, gate, clock.now());
tickets.put(tk.id, tk);
return tk;
}
}
platesInside.remove(v.plate());
throw new LotFullException("no spot fits " + v.type());
}
// Returns the fee paid. The spot is freed only after the payment succeeds.
long exit(String ticketId, PaymentProcessor pay) {
Ticket tk = tickets.get(ticketId);
if (tk == null) throw new IllegalArgumentException("unknown ticket " + ticketId);
if (!tk.status.compareAndSet(TicketStatus.ACTIVE, TicketStatus.EXITING)) // a second scan of the same ticket stops here
throw new IllegalStateException(ticketId + " is " + tk.status.get());
long fee = pricing.feeCents(tk.spot.type, Duration.between(tk.entry, clock.now()));
if (!pay.charge(ticketId, fee)) {
tk.status.set(TicketStatus.ACTIVE); // car stays, spot stays taken
throw new IllegalStateException("payment failed for " + ticketId);
}
tk.paidCents = fee;
tk.status.set(TicketStatus.PAID);
index.giveBack(tk.spot);
platesInside.remove(tk.vehicle.plate());
return fee;
}
int free(SpotType t) { return index.freeCount(0, t); }
int free(int gate, SpotType t) { return index.freeCount(gate, t); }
}
// ---------- The bug this design avoids: check, then act, with a gap between ----------
final class NaiveLot {
private final boolean[] taken; private final String[] holder;
NaiveLot(int n) { taken = new boolean[n]; holder = new String[n]; }
int park(String plate, CyclicBarrier gap) throws Exception {
for (int i = 0; i < taken.length; i++) {
if (!taken[i]) { // check: the spot looks free
gap.await(); // both threads reach here before either writes (forces the unlucky timing)
taken[i] = true; // act: both mark it taken
holder[i] = plate;
return i;
}
}
return -1;
}
}
// ---------- Demo: every behaviour is checked ----------
public class ParkingLotDemo {
static final Map<SpotType, Long> RATES = Map.of(SpotType.MOTORCYCLE, 100L, SpotType.COMPACT, 300L, SpotType.LARGE, 500L, SpotType.ELECTRIC, 400L);
// Two gates: gate 0 at slot 0, gate 1 at slot 9. A spot's distance from a gate is how many slots away it is.
static ParkingSpot spot(String id, SpotType t, int slot) { return new ParkingSpot(id, t, new int[] { slot, 9 - slot }); }
public static void main(String[] args) throws Exception {
FakeClock clock = new FakeClock();
PricingStrategy hourly = new HourlyPricing(RATES, Duration.ofMinutes(10));
PaymentProcessor ok = (id, c) -> true;
System.out.println("1. Fit rules and nearest spot");
List<ParkingSpot> spots = List.of(
spot("M1", SpotType.MOTORCYCLE, 1),
spot("C2", SpotType.COMPACT, 2), spot("C5", SpotType.COMPACT, 5), spot("C8", SpotType.COMPACT, 8),
spot("L3", SpotType.LARGE, 3), spot("L7", SpotType.LARGE, 7),
spot("E4", SpotType.ELECTRIC, 4));
ParkingLot lot = new ParkingLot(spots, 2, hourly, clock);
Ticket car0 = lot.park(new Vehicle("CAR-A", VehicleType.CAR), 0);
Ticket car1 = lot.park(new Vehicle("CAR-B", VehicleType.CAR), 1);
check(car0.spot.id.equals("C2"), "a car at gate 0 gets C2, the nearest compact spot to gate 0 (" + car0.spot + ")");
check(car1.spot.id.equals("C8"), "a car at gate 1 gets C8, the nearest compact spot to gate 1 (" + car1.spot + ")");
Ticket bike = lot.park(new Vehicle("BIKE-1", VehicleType.MOTORCYCLE), 0);
Ticket bike2 = lot.park(new Vehicle("BIKE-2", VehicleType.MOTORCYCLE), 0);
check(bike.spot.id.equals("M1") && bike2.spot.id.equals("C5"), "motorcycles take M1 first, then the next motorcycle falls back to a compact spot (" + bike2.spot + ")");
Ticket ev = lot.park(new Vehicle("EV-1", VehicleType.ELECTRIC_CAR), 0);
check(ev.spot.id.equals("E4"), "an electric car takes the charger spot E4 first");
Ticket truck = lot.park(new Vehicle("TRUCK-1", VehicleType.TRUCK), 1);
check(truck.spot.id.equals("L7"), "a truck at gate 1 gets L7, the nearest large spot to gate 1");
Ticket car3 = lot.park(new Vehicle("CAR-C", VehicleType.CAR), 0);
check(car3.spot.id.equals("L3"), "compact spots are full, so a car falls back to the last large spot L3");
boolean refused = false;
try { lot.park(new Vehicle("TRUCK-2", VehicleType.TRUCK), 0); } catch (LotFullException e) { refused = true; }
check(refused, "a second truck is refused: no large spot is left, and a truck never goes in a smaller spot");
boolean dup = false;
try { lot.park(new Vehicle("CAR-A", VehicleType.CAR), 1); } catch (IllegalStateException e) { dup = true; }
check(dup, "the same number plate cannot enter twice");
System.out.println("2. Pricing (example rates: compact $3.00 an hour, large $5.00 an hour, 10 minute grace)");
check(hourly.feeCents(SpotType.COMPACT, Duration.ofMinutes(9)) == 0, "9 minutes in a compact spot: $0.00 (inside the grace period)");
check(hourly.feeCents(SpotType.COMPACT, Duration.ofMinutes(61)) == 600, "61 minutes in a compact spot: 2 hours, $6.00");
check(hourly.feeCents(SpotType.LARGE, Duration.ofMinutes(150)) == 1500, "150 minutes in a large spot: 3 hours, $15.00");
check(new FlatDailyPricing(2000).feeCents(SpotType.COMPACT, Duration.ofHours(30)) == 4000, "swap in a flat daily price: 30 hours is 2 days, $40.00, and the lot code does not change");
System.out.println("3. Ticket lifecycle");
clock.advance(Duration.ofMinutes(61));
int compactFree = lot.free(SpotType.COMPACT);
boolean failed = false;
try { lot.exit(car0.id, (id, c) -> false); } catch (IllegalStateException e) { failed = true; }
check(failed && car0.status.get() == TicketStatus.ACTIVE && car0.spot.occupant() != null && lot.free(SpotType.COMPACT) == compactFree,
"payment fails: the ticket stays ACTIVE and spot C2 stays taken");
long fee = lot.exit(car0.id, ok);
check(fee == 600 && car0.status.get() == TicketStatus.PAID && lot.free(SpotType.COMPACT) == compactFree + 1,
"payment works: $" + fee / 100 + "." + String.format("%02d", fee % 100) + " paid, ticket PAID, C2 is free again");
boolean twice = false;
try { lot.exit(car0.id, ok); } catch (IllegalStateException e) { twice = true; }
check(twice, "a second exit with the same ticket is refused, so nobody pays twice");
Ticket again = lot.park(new Vehicle("CAR-D", VehicleType.CAR), 0);
check(again.spot.id.equals("C2"), "the freed spot C2 is given to the next car at gate 0");
// the same ticket scanned at 8 exit lanes at once: exactly one charge
AtomicInteger charges = new AtomicInteger();
int exits = race(8, () -> { lot.exit(again.id, (id, c) -> { charges.incrementAndGet(); return true; }); return true; });
check(exits == 1 && charges.get() == 1, "one ticket scanned at 8 exit lanes at the same instant: 1 exit, 1 charge");
System.out.println("4. The race for the last spot");
NaiveLot naive = new NaiveLot(1);
CyclicBarrier gap = new CyclicBarrier(2);
ExecutorService two = Executors.newFixedThreadPool(2);
Future<Integer> a = two.submit(() -> naive.park("CAR-X", gap));
Future<Integer> b = two.submit(() -> naive.park("CAR-Y", gap));
int ga = a.get(), gb = b.get();
two.shutdown();
check(ga == 0 && gb == 0, "naive check-then-act, with both cars checking before either writes: BOTH get spot 0 (the bug)");
int rounds = 1000, threads = 32, extra = 0;
for (int r = 0; r < rounds; r++) {
ParkingLot one = new ParkingLot(List.of(spot("C5", SpotType.COMPACT, 5)), 2, hourly, clock);
AtomicInteger n = new AtomicInteger();
int won = race(threads, () -> one.park(new Vehicle("R" + n.incrementAndGet(), VehicleType.CAR), n.get() % 2) != null);
if (won != 1) extra++;
}
check(extra == 0, String.format("%,d", rounds) + " rounds of " + threads + " cars from 2 gates racing for 1 last spot: exactly 1 winner every round");
List<ParkingSpot> big = new ArrayList<>();
for (int i = 0; i < 300; i++) big.add(new ParkingSpot("S" + i, SpotType.COMPACT, new int[] { i, 299 - i }));
ParkingLot busy = new ParkingLot(big, 2, hourly, clock);
Map<String, String> owner = new ConcurrentHashMap<>();
AtomicInteger doubles = new AtomicInteger(), seq = new AtomicInteger();
List<Ticket> issued = Collections.synchronizedList(new ArrayList<>());
ExecutorService pool = Executors.newFixedThreadPool(16);
CountDownLatch go = new CountDownLatch(1);
List<Future<?>> fs = new ArrayList<>();
for (int t = 0; t < 16; t++) fs.add(pool.submit(() -> {
go.await();
for (int k = 0; k < 50; k++) {
int id = seq.incrementAndGet();
try {
Ticket tk = busy.park(new Vehicle("P" + id, VehicleType.CAR), id % 2);
if (owner.putIfAbsent(tk.spot.id, tk.vehicle.plate()) != null) doubles.incrementAndGet();
issued.add(tk);
} catch (LotFullException full) { /* expected once all 300 are taken */ }
}
return null;
}));
go.countDown();
for (Future<?> f : fs) f.get();
pool.shutdown();
check(issued.size() == 300 && doubles.get() == 0 && busy.free(SpotType.COMPACT) == 0,
"800 cars from 16 threads at 2 gates into 300 spots: 300 tickets, 0 spots given twice, 0 left free");
for (Ticket tk : issued) busy.exit(tk.id, ok);
check(busy.free(0, SpotType.COMPACT) == 300 && busy.free(1, SpotType.COMPACT) == 300, "after all 300 exit, every spot is back in both gates' indexes");
System.out.println("all checks passed");
}
// Start `threads` threads at the same instant; count how many returned true without throwing.
static int race(int threads, Callable<Boolean> body) throws Exception {
ExecutorService pool = Executors.newFixedThreadPool(threads);
CountDownLatch go = new CountDownLatch(1);
List<Future<Boolean>> fs = new ArrayList<>();
for (int i = 0; i < threads; i++) fs.add(pool.submit(() -> { go.await(); try { return body.call(); } catch (RuntimeException e) { return false; } }));
go.countDown();
int wins = 0;
for (Future<Boolean> f : fs) if (f.get()) wins++;
pool.shutdown();
return wins;
}
static void check(boolean ok, String what) { System.out.println((ok ? " ok " : " FAIL ") + what); if (!ok) System.exit(1); }
}
/* Output of this exact program (javac + java 21, 2026-10-07):
* 1. Fit rules and nearest spot
* ok a car at gate 0 gets C2, the nearest compact spot to gate 0 (C2)
* ok a car at gate 1 gets C8, the nearest compact spot to gate 1 (C8)
* ok motorcycles take M1 first, then the next motorcycle falls back to a compact spot (C5)
* ok an electric car takes the charger spot E4 first
* ok a truck at gate 1 gets L7, the nearest large spot to gate 1
* ok compact spots are full, so a car falls back to the last large spot L3
* ok a second truck is refused: no large spot is left, and a truck never goes in a smaller spot
* ok the same number plate cannot enter twice
* 2. Pricing (example rates: compact $3.00 an hour, large $5.00 an hour, 10 minute grace)
* ok 9 minutes in a compact spot: $0.00 (inside the grace period)
* ok 61 minutes in a compact spot: 2 hours, $6.00
* ok 150 minutes in a large spot: 3 hours, $15.00
* ok swap in a flat daily price: 30 hours is 2 days, $40.00, and the lot code does not change
* 3. Ticket lifecycle
* ok payment fails: the ticket stays ACTIVE and spot C2 stays taken
* ok payment works: $6.00 paid, ticket PAID, C2 is free again
* ok a second exit with the same ticket is refused, so nobody pays twice
* ok the freed spot C2 is given to the next car at gate 0
* ok one ticket scanned at 8 exit lanes at the same instant: 1 exit, 1 charge
* 4. The race for the last spot
* ok naive check-then-act, with both cars checking before either writes: BOTH get spot 0 (the bug)
* ok 1,000 rounds of 32 cars from 2 gates racing for 1 last spot: exactly 1 winner every round
* ok 800 cars from 16 threads at 2 gates into 300 spots: 300 tickets, 0 spots given twice, 0 left free
* ok after all 300 exit, every spot is back in both gates' indexes
* all checks passed
*/How it works
Start with how a car gets a spot, because the rest hangs off it. The gate calls park(vehicle, gate). The lot asks FitRules which spot types this vehicle may use, smallest first. For a car that is COMPACT, then LARGE.
Finding the nearest spot fast is the next problem. Checking every spot for every car is slow in a big lot. So each gate keeps its own sorted set of free spots for each type, ordered by distance from that gate. The set is a ConcurrentSkipListSet. It is a sorted set from the Java library, and many threads can safely use it at once. pollFirst() removes and returns the nearest spot. Its cost grows with the log of the set size. Log base 2 of 10,000 is about 13, so even a big lot needs only a small number of steps. In the program, a car at gate 0 gets C2 and a car at gate 1 gets C8, because each gate sees its own nearest spot.
Now the race. Each gate has its own set, so gate 0 and gate 1 can both pull one spot at one moment. This is safe, because a set only suggests a spot. The spot itself decides who owns it. ParkingSpot keeps its car in an AtomicReference, and tryOccupy() is compareAndSet(null, car): set the car only if the spot is still empty. Exactly one thread sees true. The winner then removes the spot from the other gates' sets. A loser drops it and pulls its next nearest spot.
The program shows the bug first. A naive lot checks that spot 0 is free, then marks it taken. A barrier holds both cars between the check and the write, which forces the unlucky timing. Both cars get spot 0. Then the real lot runs 1,000 rounds. In each, 32 cars from 2 gates start together for 1 last spot. Every round has exactly 1 winner. A bigger test sends 800 cars from 16 threads into 300 spots. It gives out 300 tickets, and no spot goes to two cars.
Exit is the second half. The ticket's status moves from ACTIVE to EXITING with another compare-and-set, so one ticket scanned at 8 lanes at once is charged once. The fee comes from the PricingStrategy. If payment fails, the ticket goes back to ACTIVE and the spot stays taken. If it succeeds, the ticket becomes PAID and the spot goes back into every gate's set.
The parts most likely to change sit behind interfaces: the price rule, the payment method and the clock. Swapping hourly pricing for a flat daily price needs one new class and no change to the lot.
Edge cases & gotchas
- Two cars, two gates, one last spot. Both gates may pull spot C5 from their own sets. tryOccupy() lets one win. The other moves on to its next spot, or is told the lot is full.
- A truck when only compact spots are free. FitRules never lists a smaller spot for a truck, so it is refused. A car, though, can fall back to a large spot.
- An electric car when every charger spot is taken. It parks in a compact or large spot without charging, so it is not turned away.
- Payment fails at exit. The ticket goes back to ACTIVE and the spot stays taken. The driver can try another card.
- A ticket scanned twice, or at two exit lanes at once. Only the first compare-and-set from ACTIVE to EXITING succeeds, so there is one charge.
- Leaving within the grace period, the first 10 free minutes: the fee is zero. 61 minutes is 2 started hours. Counting minutes and rounding up avoids the classic off-by-one bill.
- The same number plate entering twice usually means a bad camera read or a cloned plate. Refuse it and alert staff.
- A spot closed for repair. Remove it from every gate's set and it can never be handed out. Put it back when it reopens.
- Counting free spots. ConcurrentSkipListSet.size() walks the whole set, and its answer can be stale while cars move. That is fine for a display board. For a busy counter, keep a separate atomic count per type.
- Paid tickets stay in the tickets map in this program. A real system moves them to storage after exit, or the map grows forever.
FAQ
Master LLD and system design interviews
770 interactive lessons and 106 real systems taken apart. One payment, lifetime access, no subscription.
course 1
System Design Masterclass
From absolute beginner to principal engineer, drawn step by step.
- 770 interactive lessons
- Step-by-step system design diagrams
- Live code editors
- Quizzes with instant feedback
- Progress tracking and streaks
- Lifetime access and all future lessons
One design is not enough for the machine coding round.
Get all 200 questions in the System Design and Distributed Systems pack
Each question has why it is asked, a full answer, what the interviewer listens for, the follow-ups, the common mistakes and a diagram (268 diagrams in all). A PDF you keep, junior to staff level.
India: UPI, cards or netbanking through Razorpay. Elsewhere: card or PayPal. Download at once from My packs.