Parking lot
Design a parking lot in a machine-coding interview: requirements, classes, pricing and spot-allocation strategies, full Java and Python code, and race-free spot assignment.
On this page
The problem: a garage that works until Saturday
"Design a parking lot" is the most common low-level design (LLD) question. The interviewer wants working classes in 45 minutes, not boxes and arrows. A first attempt usually looks like this:
class ParkingLot {
boolean[] taken = new boolean[400];
double ratePerHour = 2.0;
int park() {
for (int i = 0; i < taken.length; i++)
if (!taken[i]) { taken[i] = true; return i; }
return -1;
}
double pay(long minutes) {
if (isWeekend()) return 10.0; // the owner asked for this last week
return Math.ceil(minutes / 60.0) * ratePerHour;
}
}
It runs, and it has four problems an interviewer will find in minutes:
- No vehicle sizes. A truck gets spot 7, which is a motorbike bay.
- Pricing is welded in. Every new rule (weekends, events, monthly passes) edits
pay(). - Money is a
double.0.1 + 0.2is not0.3in floating point; prices must be whole cents. - Two gates, one spot. Two threads can both read
taken[i] == falsebefore either writestrue. Both drivers get spoti.
The rest of this page builds a design that fixes all four, in the order you would do it in an interview: requirements, entities, classes, code, concurrency, extensions.
1. Clarify the requirements
Pin down the requirements before any code
- “Design a parking lot” is a classic low-level design question. Step one is always the same: pin down the requirements. How many floors? Which vehicle sizes? How do people pay? What happens when it’s full?
The interviewer says only "Design a parking lot." Write down 5–6 questions you would ask, then the functional requirements you would agree on and two things you would leave out of scope.
Compare with our answer
Questions worth asking: How many floors and spots? Which vehicle types, and can a small vehicle use a bigger spot? Does the system assign a spot, or do drivers park anywhere? How is the price computed? How do people pay? Several entry and exit gates?
A strong answer mentions: vehicle types and spot sizes with a "fits" rule · ticket at entry, pay at exit · a pricing rule that will change · what happens when full · multiple gates working at once (the concurrency hook) · explicit out-of-scope items.
The agreed list for this page:
| Functional | Detail |
|---|---|
| Floors and spots | Several floors; each spot is SMALL, MEDIUM or LARGE |
| Vehicles | Motorbike needs SMALL, car needs MEDIUM, truck needs LARGE; a vehicle may use a bigger spot, never a smaller one |
| Entry | The gate assigns a spot and issues a ticket with the entry time |
| Exit | The gate computes the price, takes payment (card or cash) and frees the spot |
| Full | If nothing fits, the gate says so for that vehicle type |
| Several gates | Entry and exit gates work at the same time |
Pricing: free for the first 15 minutes, then a rate per started hour that depends on vehicle type, with a daily cap. The owner will change this.
Out of scope (say it out loud): reservations, EV charging, number-plate cameras, monthly passes, the display boards. You will offer some of these as extensions at the end.
2. Find the entities
Underline the nouns in the requirements. Most become classes, some become fields, and some are noise.
Nouns become classes or fields, then connect them
- Step two: underline the nouns. Parking lot, floor, spot, vehicle, ticket, gate, payment. Most become classes. Some nouns are just fields, like a spot’s size or a ticket’s entry time, and some aren’t needed at all, like the driver’s name.
- Step three: connect them. A lot is made of floors, a floor is made of spots: composition. A ticket points at the vehicle and the spot it was given. The gate uses the lot to park cars and a payment to take money.
The relationships matter as much as the classes:
- Composition: a lot owns its floors and a floor owns its spots. They are created together and have no life outside the lot.
- Association: a ticket points to a vehicle and a spot. The spot outlives the ticket.
- Dependency: the gate uses a payment method for one call and doesn't keep it.
Verbs become methods: park → ParkingLot.park(vehicle), pay → PaymentMethod.charge(amount), free the spot → Floor.giveBack(spot).
3. The class design
| Class / type | Kind | Responsibility |
|---|---|---|
VehicleType, SpotSize, TicketStatus | enums | Fixed sets of values. VehicleType.fits(size) holds the size rule in one place |
Vehicle | value object (record) | Plate and type; immutable |
ParkingSpot | entity | Id, floor, size, current occupant; tryOccupy is an atomic compare-and-set |
Floor | entity | Owns its spots and keeps an index of free spots per size |
Ticket | entity | Vehicle, spot, entry time, status |
SpotAllocationStrategy | interface | Which free spot a vehicle gets |
PricingStrategy | interface | How much a ticket costs at exit |
PaymentMethod | interface | Card, cash, wallet |
ParkingLot | facade | The one entry point the gates call: park, quote, exit |
Why each pattern is there, in one sentence each, which is what an interviewer wants to hear:
- Strategy for pricing: prices change on the owner's schedule (weekends, events), so each rule is its own class and
ParkingLotnever changes for a new one. - Strategy for allocation: "lowest floor first", "nearest the lift" and "spread across floors" are the same job done differently.
- Facade (
ParkingLot): gates, kiosks and an admin API all call three methods and never touch floors or spots directly. - Enums with behaviour:
VehicleType.fitskeeps the size rule in one place instead ofif (type == TRUCK && size != LARGE)scattered around.
Pricing is the part most likely to change, so it becomes a strategy
- Step five: spot the parts likely to change, and give them a pattern. Prices change (weekends, events), so pricing is a strategy. How to choose a spot (nearest the lift, lowest floor) could be a strategy too.
4. The code
The park flow, before the full listing: find a free spot that fits, take it, return a ticket. If nothing fits, say so clearly.
The park flow in code
- Step four: walk through the main flow in code. To park, find a free spot that fits the vehicle, mark it taken, and hand back a ticket. If nothing fits, say so.
Two details in the code below are worth pointing at in the interview. First, each floor keeps its free spots in a sorted set per size, so finding a spot never scans 400 bays, and removing one from the set is claiming it. Second, time is passed in (park(vehicle, now)) rather than read from the system clock inside the class, which makes pricing testable without waiting three hours.
import java.time.Duration;
import java.time.Instant;
import java.util.*;
import java.util.concurrent.*;
import java.util.concurrent.atomic.AtomicLong;
import java.util.concurrent.atomic.AtomicReference;
// The demo class comes first: `java ParkingDemo.java` runs the first class in the file.
// ---------- Demo ----------
public class ParkingDemo {
public static void main(String[] args) throws Exception {
Map<SpotSize, Integer> layout = Map.of(SpotSize.SMALL, 2, SpotSize.MEDIUM, 3, SpotSize.LARGE, 1);
List<Floor> floors = List.of(new Floor(0, layout), new Floor(1, layout));
PricingStrategy hourly = new HourlyPricing(
Map.of(VehicleType.MOTORBIKE, 100L, VehicleType.CAR, 200L, VehicleType.TRUCK, 400L), 2000);
ParkingLot lot = new ParkingLot(floors, new LowestFloorBestFit(), hourly);
Instant nine = Instant.parse("2026-11-21T09:00:00Z");
Ticket car = lot.park(new Vehicle("KA-01-1234", VehicleType.CAR), nine);
Ticket bike = lot.park(new Vehicle("KA-02-0007", VehicleType.MOTORBIKE), nine);
System.out.println("car -> " + car.spot.id + " (" + car.spot.size + ")");
System.out.println("bike -> " + bike.spot.id + " (" + bike.spot.size + ")");
lot.park(new Vehicle("TR-1", VehicleType.TRUCK), nine);
lot.park(new Vehicle("TR-2", VehicleType.TRUCK), nine);
try { lot.park(new Vehicle("TR-3", VehicleType.TRUCK), nine); }
catch (LotFullException e) { System.out.println("third truck: " + e.getMessage()); }
Instant later = nine.plus(Duration.ofMinutes(2 * 60 + 10)); // 2 h 10 min -> 3 started hours
System.out.println("car pays " + lot.exit(car.id, later, new CardPayment()) + " cents");
// Concurrency: 40 cars race for the remaining MEDIUM and LARGE spots at the same instant.
int before = lot.free(SpotSize.MEDIUM) + lot.free(SpotSize.LARGE);
ExecutorService pool = Executors.newFixedThreadPool(16);
Set<String> spots = ConcurrentHashMap.newKeySet();
List<Future<?>> fs = new ArrayList<>();
for (int i = 0; i < 40; i++) {
final int n = i;
fs.add(pool.submit(() -> {
try { spots.add(lot.park(new Vehicle("RACE-" + n, VehicleType.CAR), nine).spot.id); }
catch (LotFullException ignored) { }
}));
}
for (Future<?> f : fs) f.get();
pool.shutdown();
System.out.println("free car-sized spots before race: " + before + ", tickets issued: " + spots.size()
+ ", all distinct: " + (spots.size() == before));
}
}
// ---------- Enums ----------
enum SpotSize { SMALL, MEDIUM, LARGE } // ordered smallest to largest
enum VehicleType {
MOTORBIKE(SpotSize.SMALL), CAR(SpotSize.MEDIUM), TRUCK(SpotSize.LARGE);
final SpotSize minSize;
VehicleType(SpotSize minSize) { this.minSize = minSize; }
boolean fits(SpotSize s) { return s.compareTo(minSize) >= 0; }
}
enum TicketStatus { ACTIVE, PAID }
// ---------- Entities ----------
record Vehicle(String plate, VehicleType type) {}
final class ParkingSpot implements Comparable<ParkingSpot> {
final String id; final int floor; final int number; final SpotSize size;
private final AtomicReference<Vehicle> occupant = new AtomicReference<>();
ParkingSpot(int floor, int number, SpotSize size) {
this.floor = floor; this.number = number; this.size = size;
this.id = "F" + floor + "-" + number;
}
boolean tryOccupy(Vehicle v) { return occupant.compareAndSet(null, v); } // atomic: one winner
void release() { occupant.set(null); }
public int compareTo(ParkingSpot o) { return Integer.compare(number, o.number); } // low number = near the lift
}
final class Floor {
final int number;
// Free spots per size, kept sorted. pollFirst() removes atomically, so two threads never get the same spot.
private final Map<SpotSize, ConcurrentSkipListSet<ParkingSpot>> free = new EnumMap<>(SpotSize.class);
Floor(int number, Map<SpotSize, Integer> counts) {
this.number = number;
int n = 1;
for (SpotSize s : SpotSize.values()) {
free.put(s, new ConcurrentSkipListSet<>());
for (int i = 0; i < counts.getOrDefault(s, 0); i++) free.get(s).add(new ParkingSpot(number, n++, s));
}
}
ParkingSpot takeFree(SpotSize s) { return free.get(s).pollFirst(); } // null if none
void giveBack(ParkingSpot spot) { free.get(spot.size).add(spot); }
int freeCount(SpotSize s) { return free.get(s).size(); }
}
final class Ticket {
final String id; final Vehicle vehicle; final ParkingSpot spot; final Instant entry;
volatile TicketStatus status = TicketStatus.ACTIVE;
Ticket(String id, Vehicle vehicle, ParkingSpot spot, Instant entry) {
this.id = id; this.vehicle = vehicle; this.spot = spot; this.entry = entry;
}
}
class LotFullException extends RuntimeException {
LotFullException(VehicleType t) { super("No free spot for " + t); }
}
// ---------- What varies: strategies ----------
interface SpotAllocationStrategy {
ParkingSpot allocate(List<Floor> floors, VehicleType type); // returns a spot already removed from the free set, or null
}
/** Lowest floor first, and the smallest spot that fits, so big spots stay free for big vehicles. */
final class LowestFloorBestFit implements SpotAllocationStrategy {
public ParkingSpot allocate(List<Floor> floors, VehicleType type) {
for (Floor f : floors)
for (SpotSize s : SpotSize.values())
if (type.fits(s)) {
ParkingSpot spot = f.takeFree(s);
if (spot != null) return spot;
}
return null;
}
}
interface PricingStrategy {
long priceCents(Ticket t, Instant exit);
}
/** Free for the first 15 minutes, then each started hour is charged, capped per day. */
final class HourlyPricing implements PricingStrategy {
private final Map<VehicleType, Long> centsPerHour;
private final long dailyCapCents;
HourlyPricing(Map<VehicleType, Long> centsPerHour, long dailyCapCents) {
this.centsPerHour = centsPerHour; this.dailyCapCents = dailyCapCents;
}
public long priceCents(Ticket t, Instant exit) {
long minutes = Duration.between(t.entry, exit).toMinutes();
if (minutes <= 15) return 0;
long days = minutes / (24 * 60), rest = minutes % (24 * 60);
long restPrice = Math.min(dailyCapCents, ((rest + 59) / 60) * centsPerHour.get(t.vehicle.type()));
return days * dailyCapCents + restPrice;
}
}
final class FlatPricing implements PricingStrategy { // e.g. event nights
private final long cents;
FlatPricing(long cents) { this.cents = cents; }
public long priceCents(Ticket t, Instant exit) { return cents; }
}
interface PaymentMethod { boolean charge(String ticketId, long cents); }
final class CardPayment implements PaymentMethod {
public boolean charge(String ticketId, long cents) {
System.out.printf(" card charged %d.%02d for %s%n", cents / 100, cents % 100, ticketId);
return true; // a real one calls the card terminal
}
}
// ---------- The facade the gates call ----------
final class ParkingLot {
private final List<Floor> floors;
private final SpotAllocationStrategy allocation;
private volatile PricingStrategy pricing; // swappable at run time
private final ConcurrentHashMap<String, Ticket> active = new ConcurrentHashMap<>(); // by ticket id
private final ConcurrentHashMap<String, String> plateToTicket = new ConcurrentHashMap<>(); // one ticket per plate
private final AtomicLong seq = new AtomicLong();
ParkingLot(List<Floor> floors, SpotAllocationStrategy allocation, PricingStrategy pricing) {
for (int i = 0; i < floors.size(); i++)
if (floors.get(i).number != i) throw new IllegalArgumentException("floors must be numbered 0..n-1");
this.floors = floors; this.allocation = allocation; this.pricing = pricing;
}
void setPricing(PricingStrategy p) { this.pricing = p; }
Ticket park(Vehicle v, Instant now) {
String id = "T" + seq.incrementAndGet();
if (plateToTicket.putIfAbsent(v.plate(), id) != null)
throw new IllegalStateException(v.plate() + " is already parked");
ParkingSpot spot = allocation.allocate(floors, v.type());
if (spot == null) { plateToTicket.remove(v.plate()); throw new LotFullException(v.type()); }
if (!spot.tryOccupy(v)) throw new IllegalStateException("spot " + spot.id + " was handed out twice");
Ticket t = new Ticket(id, v, spot, now);
active.put(id, t);
return t;
}
long quote(String ticketId, Instant now) { return pricing.priceCents(find(ticketId), now); }
long exit(String ticketId, Instant now, PaymentMethod pay) {
Ticket t = find(ticketId);
long due = pricing.priceCents(t, now);
if (!active.remove(ticketId, t)) throw new IllegalStateException("ticket already used"); // claim: one exit wins
if (!pay.charge(ticketId, due)) { active.put(ticketId, t); throw new IllegalStateException("payment declined"); }
t.status = TicketStatus.PAID;
plateToTicket.remove(t.vehicle.plate());
t.spot.release();
floors.get(t.spot.floor).giveBack(t.spot); // spot is free again only after the car has left
return due;
}
int free(SpotSize s) { return floors.stream().mapToInt(f -> f.freeCount(s)).sum(); }
private Ticket find(String id) {
Ticket t = active.get(id);
if (t == null) throw new NoSuchElementException("unknown or used ticket " + id);
return t;
}
}import heapq
import itertools
import threading
from abc import ABC, abstractmethod
from concurrent.futures import ThreadPoolExecutor
from dataclasses import dataclass, field
from datetime import datetime, timedelta
from enum import Enum, IntEnum
from typing import Optional
# ---------- Enums ----------
class SpotSize(IntEnum): # ordered smallest to largest
SMALL = 1
MEDIUM = 2
LARGE = 3
class VehicleType(Enum):
MOTORBIKE = SpotSize.SMALL
CAR = SpotSize.MEDIUM
TRUCK = SpotSize.LARGE
def fits(self, size: SpotSize) -> bool:
return size >= self.value
class TicketStatus(Enum):
ACTIVE = "active"
PAID = "paid"
# ---------- Entities ----------
@dataclass(frozen=True)
class Vehicle:
plate: str
type: VehicleType
@dataclass(eq=False)
class ParkingSpot:
floor: int
number: int
size: SpotSize
occupant: Optional[Vehicle] = None
@property
def id(self) -> str:
return f"F{self.floor}-{self.number}"
class Floor:
def __init__(self, number: int, counts: dict):
self.number = number
self._free = {s: [] for s in SpotSize} # one min-heap per size, by spot number
n = itertools.count(1)
for size in SpotSize:
for _ in range(counts.get(size, 0)):
spot = ParkingSpot(number, next(n), size)
heapq.heappush(self._free[size], (spot.number, spot))
# Not thread-safe on their own: ParkingLot calls them while holding its lock.
def take_free(self, size: SpotSize) -> Optional[ParkingSpot]:
heap = self._free[size]
return heapq.heappop(heap)[1] if heap else None
def give_back(self, spot: ParkingSpot) -> None:
heapq.heappush(self._free[spot.size], (spot.number, spot))
def free_count(self, size: SpotSize) -> int:
return len(self._free[size])
@dataclass
class Ticket:
id: str
vehicle: Vehicle
spot: ParkingSpot
entry: datetime
status: TicketStatus = TicketStatus.ACTIVE
class LotFullError(Exception):
pass
# ---------- What varies: strategies ----------
class SpotAllocationStrategy(ABC):
@abstractmethod
def allocate(self, floors: list, vtype: VehicleType) -> Optional[ParkingSpot]: ...
class LowestFloorBestFit(SpotAllocationStrategy):
"""Lowest floor first, and the smallest spot that fits."""
def allocate(self, floors, vtype):
for f in floors:
for size in SpotSize:
if vtype.fits(size):
spot = f.take_free(size)
if spot is not None:
return spot
return None
class PricingStrategy(ABC):
@abstractmethod
def price_cents(self, ticket: Ticket, exit_time: datetime) -> int: ...
class HourlyPricing(PricingStrategy):
"""Free for 15 minutes, then each started hour is charged, capped per day."""
def __init__(self, cents_per_hour: dict, daily_cap_cents: int):
self.rate = cents_per_hour
self.cap = daily_cap_cents
def price_cents(self, ticket, exit_time):
minutes = int((exit_time - ticket.entry).total_seconds() // 60)
if minutes <= 15:
return 0
days, rest = divmod(minutes, 24 * 60)
hours = -(-rest // 60) # ceiling division
return days * self.cap + min(self.cap, hours * self.rate[ticket.vehicle.type])
class FlatPricing(PricingStrategy):
def __init__(self, cents: int):
self.cents = cents
def price_cents(self, ticket, exit_time):
return self.cents
class PaymentMethod(ABC):
@abstractmethod
def charge(self, ticket_id: str, cents: int) -> bool: ...
class CardPayment(PaymentMethod):
def charge(self, ticket_id, cents):
print(f" card charged {cents // 100}.{cents % 100:02d} for {ticket_id}")
return True
# ---------- The facade the gates call ----------
class ParkingLot:
def __init__(self, floors, allocation: SpotAllocationStrategy, pricing: PricingStrategy):
assert all(f.number == i for i, f in enumerate(floors)), "floors must be numbered 0..n-1"
self.floors = floors
self.allocation = allocation
self.pricing = pricing # swappable at run time
self._lock = threading.Lock() # guards free spots, tickets and plates together
self._active = {} # ticket id -> Ticket
self._plates = {} # plate -> ticket id
self._seq = itertools.count(1)
def park(self, vehicle: Vehicle, now: datetime) -> Ticket:
with self._lock: # "find a spot" and "take it" are one step
if vehicle.plate in self._plates:
raise ValueError(f"{vehicle.plate} is already parked")
spot = self.allocation.allocate(self.floors, vehicle.type)
if spot is None:
raise LotFullError(f"No free spot for {vehicle.type.name}")
spot.occupant = vehicle
ticket = Ticket(f"T{next(self._seq)}", vehicle, spot, now)
self._active[ticket.id] = ticket
self._plates[vehicle.plate] = ticket.id
return ticket
def quote(self, ticket_id: str, now: datetime) -> int:
with self._lock:
ticket = self._find(ticket_id)
return self.pricing.price_cents(ticket, now)
def exit(self, ticket_id: str, now: datetime, pay: PaymentMethod) -> int:
with self._lock: # claim the ticket so only one exit can use it
ticket = self._active.pop(ticket_id, None)
if ticket is None:
raise KeyError(f"unknown or used ticket {ticket_id}")
due = self.pricing.price_cents(ticket, now)
if not pay.charge(ticket_id, due): # slow call: made outside the lock
with self._lock:
self._active[ticket_id] = ticket
raise RuntimeError("payment declined")
with self._lock:
ticket.status = TicketStatus.PAID
del self._plates[ticket.vehicle.plate]
ticket.spot.occupant = None
self.floors[ticket.spot.floor].give_back(ticket.spot)
return due
def free(self, size: SpotSize) -> int:
with self._lock:
return sum(f.free_count(size) for f in self.floors)
def _find(self, ticket_id):
if ticket_id not in self._active:
raise KeyError(f"unknown or used ticket {ticket_id}")
return self._active[ticket_id]
# ---------- Demo ----------
if __name__ == "__main__":
layout = {SpotSize.SMALL: 2, SpotSize.MEDIUM: 3, SpotSize.LARGE: 1}
lot = ParkingLot([Floor(0, layout), Floor(1, layout)], LowestFloorBestFit(),
HourlyPricing({VehicleType.MOTORBIKE: 100, VehicleType.CAR: 200,
VehicleType.TRUCK: 400}, daily_cap_cents=2000))
nine = datetime(2026, 11, 21, 9, 0)
car = lot.park(Vehicle("KA-01-1234", VehicleType.CAR), nine)
bike = lot.park(Vehicle("KA-02-0007", VehicleType.MOTORBIKE), nine)
print("car ->", car.spot.id, car.spot.size.name)
print("bike ->", bike.spot.id, bike.spot.size.name)
lot.park(Vehicle("TR-1", VehicleType.TRUCK), nine)
lot.park(Vehicle("TR-2", VehicleType.TRUCK), nine)
try:
lot.park(Vehicle("TR-3", VehicleType.TRUCK), nine)
except LotFullError as e:
print("third truck:", e)
later = nine + timedelta(hours=2, minutes=10) # 3 started hours
print("car pays", lot.exit(car.id, later, CardPayment()), "cents")
# Concurrency: 40 cars race for the remaining car-sized spots.
before = lot.free(SpotSize.MEDIUM) + lot.free(SpotSize.LARGE)
def try_park(n):
try:
return lot.park(Vehicle(f"RACE-{n}", VehicleType.CAR), nine).spot.id
except LotFullError:
return None
with ThreadPoolExecutor(max_workers=16) as pool:
got = [s for s in pool.map(try_park, range(40)) if s]
print(f"free before race: {before}, tickets: {len(got)}, all distinct: {len(set(got)) == before}")Running either version prints:
car -> F0-3 (MEDIUM)
bike -> F0-1 (SMALL)
third truck: No free spot for TRUCK
card charged 6.00 for T1
car pays 600 cents
free car-sized spots before race: 6, tickets issued: 6, all distinct: true
The car stayed 2 h 10 min. The first 15 minutes are only free for short stays, so it pays for 3 started hours at 200 cents: 600 cents. A car left for 30 hours pays one daily cap (2,000) plus 6 started hours capped at 2,000 (1,200): 3,200 cents.
5. Concurrency: one spot, two cars
Two gates, one last spot
- Last, edge cases. Two cars arrive at two gates at the same moment and both are offered the last spot. Picking and taking a spot must happen as one locked step, so only one car gets it. Interviewers love this question.
With several gates, park and exit run on different threads at the same time. List the races out loud; interviewers score you for naming them before they ask.
| Race | What goes wrong | Fix in the code above |
|---|---|---|
| Two cars, one spot | Both see the spot free, both are assigned it | Java: pollFirst() on a ConcurrentSkipListSet removes atomically, so only one thread gets the spot; tryOccupy is a compare-and-set as a safety check. Python: one lock around "find and take" |
| The same plate twice | A double tap at the gate holds two spots | putIfAbsent(plate, ticketId): an atomic check-and-insert |
| One ticket, two exits | Paid twice, or the spot is freed twice and handed to two cars | Claim the ticket first with active.remove(id, ticket); only one caller gets true |
| Declined card | The spot is freed while the car is still in it | Free the spot only after payment succeeds; put the ticket back if it fails |
| Price rule swapped mid-exit | A reader sees a half-built object | The field is volatile and strategies are immutable, so a reader sees the old rule or the new one |
The two versions show the two standard fixes on purpose:
- One coarse lock (Python): simple and obviously correct. Every park and exit queues on one lock, but each holds it for microseconds, so a garage with a dozen gates will never notice. Note the payment call is made outside the lock: never hold a lock across a slow network call.
- Fine-grained atomic structures (Java): no global lock. The free set per floor and size is the unit of contention, and
ConcurrentHashMaphandles the ticket and plate maps. More scalable, but every invariant that spans two structures (the plate map and the free set) needs thought.
6. Options and trade-offs
The allocation strategy is a real product decision, and interviewers like to hear that you know the options:
| Strategy | Good at | Weak at | Use when |
|---|---|---|---|
| First fit (first free spot that fits) | Simplest; fast | Trucks find large bays taken by cars | Spot sizes are all the same |
| Best fit (smallest size that fits; used above) | Keeps big spots for big vehicles | Small vehicles may go to a far floor | Mixed sizes, the usual case |
| Nearest the entrance or lift | Short walks | Lower floors fill first, queues on one ramp | Shopping centres, short stays |
| Spread across floors | Even wear and even traffic on ramps | Longer walks | Big garages with several ramps |
And for keeping track of free spots:
| Approach | Find a spot | Weak at |
|---|---|---|
| Scan every spot | O(spots) | Slow at 5,000 spots, and a scan under a lock blocks every gate |
| Free set per floor and size (used above) | O(log n) | A little more memory and code |
| Counter per floor and size only | O(1) | Cannot say which spot; fine if drivers choose their own |
7. Extensions the interviewer will ask for
A good design absorbs each with a new class or a small change in one place:
- EV charging spots: add
SpotFeature.CHARGERto a spot and achargingCentspart to pricing; allocation prefers non-charging spots for non-EVs. - Display boards per floor ("Floor 2: 14 car spaces"): the Observer pattern.
Floorpublishes "free count changed" events; boards subscribe. The lot doesn't know boards exist. - Event-night pricing: a
ScheduledPricingstrategy that delegates toFlatPricingorHourlyPricingby entry time. Nothing else changes. - Lost ticket: look up the active ticket by plate (the plate map already exists) and charge a lost-ticket fee.
- Reservations: a reserved spot is removed from the free set until its time window; a no-show after 30 minutes returns it.
- Multiple entrances: allocation takes the gate as input (
allocate(floors, type, gate)) so "nearest" means nearest this gate.
When not to over-design
- Equal spots, one gate: if every spot is the same size and there is one barrier, a counter and a lock is the whole system. Don't add strategies nobody will swap.
- Drivers choose their own spot: track counts per floor, not spot objects; the "which spot" logic disappears.
- Pricing that never changes: a constant is fine. Add
PricingStrategywhen there is a second rule, or when the interviewer hints there will be.
In the interview
A candidate's code is below. Find at least three bugs, then fix them.
ParkingSpot findSpot(VehicleType t) {
for (ParkingSpot s : spots) if (s.isFree() && t.fits(s.size)) return s;
return null;
}
synchronized void occupy(ParkingSpot s, Vehicle v) { s.occupant = v; }
double exit(Ticket t, PaymentMethod pay) {
t.spot.occupant = null; // free the spot
double price = hours(t) * 2.5;
pay.charge(price);
return price;
}Compare with our answer
The bugs: (1) findSpot then occupy is check-then-act: two threads can find the same free spot; synchronized on occupy alone doesn't help. (2) The spot is freed before payment: if the card is declined, the car is still there but its spot can be given away. (3) Money is a double. (4) Nothing stops the same ticket being used twice. (5) Pricing is hard-coded.
Ticket park(Vehicle v, Instant now) {
synchronized (this) { // find + take as one step
for (ParkingSpot s : spots)
if (s.isFree() && v.type().fits(s.size)) {
s.occupant = v;
Ticket t = new Ticket(nextId(), v, s, now);
active.put(t.id, t);
return t;
}
}
throw new LotFullException(v.type());
}
long exit(String ticketId, Instant now, PaymentMethod pay) {
Ticket t = active.remove(ticketId); // claim: a second exit gets null
if (t == null) throw new IllegalStateException("unknown or used ticket");
long cents = pricing.priceCents(t, now); // strategy, integer cents
if (!pay.charge(ticketId, cents)) { active.put(ticketId, t); throw new IllegalStateException("declined"); }
synchronized (this) { t.spot.occupant = null; } // free only after payment
return cents;
}def park(self, v, now):
with self._lock: # find + take as one step
for s in self.spots:
if s.occupant is None and v.type.fits(s.size):
s.occupant = v
t = Ticket(self._next_id(), v, s, now)
self._active[t.id] = t
return t
raise LotFullError(v.type.name)
def exit(self, ticket_id, now, pay):
with self._lock:
t = self._active.pop(ticket_id, None) # claim: a second exit gets None
if t is None:
raise KeyError("unknown or used ticket")
cents = self.pricing.price_cents(t, now) # strategy, integer cents
if not pay.charge(ticket_id, cents):
with self._lock:
self._active[ticket_id] = t
raise RuntimeError("declined")
with self._lock:
t.spot.occupant = None # free only after payment
return cents(Here active is a ConcurrentHashMap, so remove is atomic without the lock.)
A strong answer mentions: check-then-act on the spot · freeing before payment · double money · double use of one ticket · hard-coded pricing · no slow calls (payment) while holding the lock.
The owner adds 20 EV charging bays on floor 0. Only electric cars may use them unless the garage is otherwise full, and charging costs 30 cents per started 15 minutes on top of parking. What changes in your design, and what stays the same?
Compare with our answer
A strong answer mentions:
- A new spot attribute (
hasCharger, or aSpotFeatureenum set) andVehicle.electric;fitsstays about size. - A new allocation strategy (or a decorator around the existing one) that tries charging bays first for EVs, and for other vehicles only after every normal spot is taken.
- A pricing decorator,
ChargingSurcharge(PricingStrategy inner), that adds the charging fee to whatever the inner rule returns, so hourly and flat pricing both keep working. - The free index needs to separate charging bays (a separate set per floor), or allocation degrades to scanning.
ParkingLot,Ticketand the gates do not change: that is the payoff of the strategies.
- Enums:
VehicleType(withfits(size)),SpotSize,TicketStatus. Vehicle kinds are data, not subclasses. - Composition:
ParkingLot◆Floor◆ParkingSpot;Ticket→ vehicle, spot, entry time. - Strategies:
PricingStrategy(hourly, flat, scheduled),SpotAllocationStrategy(best fit, nearest, spread).PaymentMethodinterface. - Facade: gates call
park,quote,exitonly. - Free index: sorted free set per floor and size; removing from it is claiming the spot.
- Money in integer cents; time passed in for testable pricing; daily cap.
- Races: spot (atomic take), plate (
putIfAbsent), ticket (claim before charging), payment (free spot only after success, no lock held during the call). - Across servers: conditional
UPDATE … WHERE vehicle IS NULLorFOR UPDATE SKIP LOCKED, plus a unique constraint per plate. - Extensions: EV bays (strategy + pricing decorator), boards (Observer), reservations, lost ticket by plate.
1. Two entry gates run on two separate servers that share one MySQL database. Each server wraps "find a free spot and occupy it" in synchronized. On a busy Saturday two cars are assigned the same spot. Why?
A Java lock lives in one process. Two servers need the database to pick the winner: a conditional UPDATE … WHERE vehicle IS NULL, a row lock, or SKIP LOCKED. REPEATABLE READ does not block plain reads, and the JIT never moves code out of a synchronized block in a way other threads can see.
2. Pricing is free for the first 15 minutes, then 200 cents per started hour, capped at 2,000 cents a day. A car enters at 09:00 and leaves at 11:10. What does it pay?
The stay is longer than 15 minutes, so the whole stay is charged: ceiling(130 / 60) = 3 hours × 200 = 600. Whether the grace period is deducted is a business rule worth confirming with the interviewer, but this rule makes it free only for short stays.
3. A motorbike arrives. Floor 0 has no small spots left but has free medium and large spots. With a best-fit allocation strategy, where does it go?
Best fit takes the smallest size that fits, so large bays stay free for trucks. Moving to another floor first would be a different strategy (size before floor); either can be right, which is exactly why allocation is a swappable strategy.
4. A candidate's exit() returns the spot to the free set first and then charges the card. What goes wrong?
Freeing before payment breaks the invariant "a spot is free only when it is empty". Charge first (claiming the ticket so it can't be used twice), and release the spot only after payment succeeds.
5. The owner wants a flat 1,000-cent price for cars entering after 18:00 on Fridays, and the normal hourly price otherwise. Which change touches the least existing code?
A strategy that composes the existing ones keeps the rule in one new class. The branch in exit() mixes pricing into the facade; the subclass changes the building for a price; the flag spreads one rule across two classes.
6. Why does each floor keep a sorted set of free spots per size instead of scanning all spots on every arrival?
A scan is O(spots) and, under a lock, blocks every gate while it runs. pollFirst() on a concurrent sorted set is O(log n) and atomic, so finding and claiming are one step.
7. park() calls plateToTicket.putIfAbsent(plate, id) before allocating a spot. What does this protect against?
putIfAbsent is an atomic check-and-insert: the second request for the same plate sees an existing entry and is refused. In a database this is a unique constraint on active tickets per plate.
Score 60% or more and the lesson is marked complete.