# Design a Parking Lot > Design a parking lot the way an interview goes. Ask the questions, find the classes, then write the code and handle two cars arriving at once. - Track: Code System Design (Classic design problems) - Level: Intermediate - Format: Multi-language code + SQL - Author: Aayush Ostwal - Published: 25 October 2026 - Topics: OOP, Strategy Pattern, Concurrency, PostgreSQL, Python, Java, C++ - Canonical URL: https://compoundengineer.com/library/code-system-design/design-a-parking-lot ## Problem The question Design a parking lot. Vehicles drive in, get a spot and a ticket, and pay when they leave. Write the code. That is the whole prompt, and it hides a dozen decisions. Which vehicles come in? Do all spots have the same size? Which spot does a car get? What happens when the lot is full, or when two cars reach for the last spot at the same moment? A parking lot looks easy, so the interview is not about the parking. It tests whether you can ask the right questions, split the problem into a few clear classes, and keep the data correct when many gates work at once. We start with the questions. ## Gathering what we need The question is one line. Before drawing anything, ask the questions whose answers change the design, and write each answer down. Say why you are asking: it shows the interviewer how you think. You Which spot sizes are there, and which spot does a vehicle get? Interviewer Small, medium and large. A vehicle fits a spot of its size or bigger, and gets the smallest size that fits, then the lowest number, which is the one nearest the gate. If nothing fits, turn the vehicle away with no ticket. three sizes in a fixed order. Best fit, so large spots stay free for trucks. An ordered index of free spots, not a scan, so parking and leaving cost about O(log n). A full lot is a normal outcome, not an error You How does a driver prove they parked, and what if a ticket is reused? Interviewer A ticket with an id. A plate may be inside only once. An unknown or already used ticket is rejected, and a repeated exit must do no harm. a map of open tickets and a set of plates inside. A used ticket leaves the map at once, so it can never free someone else’s spot You How is the fee calculated? Interviewer Per started hour, with a rate by spot size, and rules that stack: rush hour, weekends and so on. We only return the fee on exit. Taking the payment is not part of this. pricing is a list of rules, not an if You How big and how busy is it, and how many servers share the lot? Interviewer 10,000 spots, 10 gates, and a peak of about 20 entries and exits per second. Several servers share one lot, and open tickets must survive a restart. the load is small. The difficulty is correctness under concurrency: never give one spot to two vehicles. A process lock is not enough, so the database has to arbitrate Out of scope (say it aloud): taking the payment, reservations, EV charging, number plate cameras and the screens. Each is a natural follow-up. In the interview Interviewer: “Just assume it’s a normal parking lot.” You: “Understood. I’ll write down the assumptions I’m making so you can correct them: three spot sizes, best fit, a ticket on entry, a fee on exit, and several gates at once.” You have still gathered what you need, and you did it in thirty seconds. ## Core components Before we write any class, look at what happens to one car. The picture shows the steps in plain words. After it, we go through the steps again and name the thing each one needs. A car comes in A car reaches the gate look for a place Find the smallest free spot that fits. Nearest to the gate first did we find one? Is there a spot? answer yes Write a ticket: plate, spot and time then Open the gate and hand over the ticket no Turn the car away. No ticket The car leaves The driver hands in the ticket check it A real ticket, not used before? answer yes Free the spot then Work out the fee from the time spent then Return the fee no Reject it. Nothing changes *Figure 1 — What happens to one car, in plain steps. Each step needs something to remember a fact or make a decision. Those are our classes.* Now read the same story as a list. Each time something has to remember a fact or make a decision , we have found a class. - A car reaches the gate. It brings two facts: a plate number and a size. That is a Vehicle. It only carries those two facts, so it stays a small record. - The lot must find the car a place. A place has a number, a floor and a size, and it is free or taken. That is a Spot. Somebody must also keep the list of free spots, so the nearest one that fits can be found quickly. That is the SpotIndex. - The driver gets a slip of paper that says which plate is in which spot, and since when. That is a Ticket. - On the way out, the stay must become a price. The rules for that (per hour, a rush hour surcharge, a weekend discount) will keep changing, so each rule is its own small class, a PricingRule. A class called Pricing runs them one after another. - The gates need one place to ask for things. That is the ParkingLot. It does very little itself. It hands each job to the class that owns it. We put these classes into three groups, because each group has a different job. Entities hold facts and do not change once created: Vehicle , Spot , Ticket . Behaviours are rules that may change later: the pricing rules. Services do the work and join everything together: SpotIndex , Pricing , ParkingLot . Keeping the groups apart is what keeps every class small. | Class | Group | What it is responsible for | | --- | --- | --- | | Vehicle | Entity | A plate and a size. It only carries information into the lot. | | --- | --- | --- | | Spot | Entity | An id, a floor and a size. None of these change once the spot exists. | | --- | --- | --- | | Ticket | Entity | Remembers which plate is in which spot, and since when. | | --- | --- | --- | | PricingRule, PerHour, PeakSurcharge | Behaviour | One pricing rule each. A rule gets the fee so far and returns the new fee. | | --- | --- | --- | | Pricing | Service | Runs the rules one after another and returns the final fee. | | --- | --- | --- | | SpotIndex | Service | Keeps the list of free spots and hands out the best one. | | --- | --- | --- | | ParkingLot | Service (the front door) | The one class the gates talk to. It takes the lock, asks the others to do the work, and keeps the open tickets. | | --- | --- | --- | The two pictures below show the same classes. Figure 2 shows who asks whom for help. Figure 3 shows what a ticket holds. #### ParkingLotservice, the front door - index SpotIndex - pricing Pricing - open id → Ticket - plates set of plates inside - lock - park(vehicle, now) - unpark(ticket_id, now) uses #### SpotIndexservice - free a min-heap per size - take(vehicle) - give(spot) holds the free #### Spotentity - id - floor - size Size #### Pricingservice - rules list of PricingRule - fee(ticket, exit_time) runs in order #### PricingRuleinterface - apply(ticket, exit_time, fee) implemented by #### PerHour - rates by size #### PeakSurcharge - PEAK_HOURS *Figure 2 — Who calls whom. ParkingLot is a thin front door: search lives in SpotIndex and money in Pricing. Orange cards are the pricing behaviour, an interface and the rules that implement it.* #### ParkingLot - open id → Ticket - park(vehicle, now) issues #### Ticketentity - id - plate - spot Spot - entry_time points to #### Spotentity - id - floor - size Size is not a class Vehicle is plain input: a plate and a size. There are no Car or Truck classes. *Figure 3 — The ticket remembers which plate holds which spot since when. A vehicle only supplies two values, so it stays a small record.* In the interview Interviewer: “Why not Car , Motorcycle and Truck classes?” You: “They would have the same fields and the same methods and differ only in size, so a class tree adds code and no behaviour. One Vehicle with a size does the job, and I would add a subclass only when a type needs its own rule, for example a truck that takes two spots.” ## Services and behaviours Classes are the nouns. Now the verbs : what can be asked of each class. A good test is whether a caller could ask for it in one sentence. ParkingLot.park(vehicle, now) Take the lock, reject a plate already inside, get the smallest free spot that fits, write a ticket and return it. If nothing fits, return none and turn the vehicle away. called by an entry gate ParkingLot.unpark(ticket_id, now) Spend the ticket once, give the spot back to the index, and return the fee. An unknown or used ticket is rejected. called by an exit gate SpotIndex.take(vehicle) Remove and return the nearest free spot of the smallest size that fits. Taking and removing are one step. called by the lot, under its lock SpotIndex.give(spot) Put a spot back among the free ones. called by the lot, under its lock Pricing.fee(ticket, exit_time) Run the rules in order. Each gets the fee so far and returns a new one. called by the lot PricingRule.apply(ticket, exit_time, fee) One rule: per hour, a peak surcharge, a weekend discount. Reads the ticket and returns a number. called by Pricing Inside park , everything between taking the lock and releasing it is the critical section : the one stretch of code that only one gate may run at a time. The concurrency deep dive below shows why. The design in one breath. A ParkingLot facade owns the lock and the open tickets. To park, it asks the SpotIndex for the smallest free spot that fits and writes a Ticket . To leave, the ticket is spent once, the spot goes back to the index, and Pricing runs its rules in order to produce the fee. ## Implementation We build from the bottom up, so every block uses only what is already written. Each block shows the code, then explains the choices behind it: why it is shaped this way and what the alternative would cost. ### Size and Vehicle ``` from __future__ import annotations import heapq import math from abc import ABC, abstractmethod from dataclasses import dataclass from enum import IntEnum from itertools import count from threading import Lock from typing import Optional class Size(IntEnum): SMALL = 1 # the numbers are the fit order MEDIUM = 2 LARGE = 3 @dataclass(frozen=True) class Vehicle: plate: str size: Size ``` ``` import java.util.*; enum Size { SMALL, MEDIUM, LARGE } // declaration order is the fit order record Vehicle(String plate, Size size) {} ``` ``` #include #include #include #include #include #include #include #include #include #include using namespace std; enum class Size { SMALL = 1, MEDIUM = 2, LARGE = 3 }; // the numbers are the fit order struct Vehicle { string plate; Size size; }; ``` - The enum order is the fit rule. SMALL ``` @dataclass(frozen=True) class Spot: id: int floor: int size: Size @dataclass(frozen=True) class Ticket: id: int plate: str spot: Spot entry_time: int # seconds; passed in, never read from a clock ``` ``` record Spot(int id, int floor, Size size) {} record Ticket(int id, String plate, Spot spot, long entryTime) {} // seconds; passed in, never read from a clock ``` ``` struct Spot { int id, floor; Size size; }; struct Ticket { int id; string plate; const Spot* spot; long entryTime; // seconds; passed in, never read from a clock }; ``` - Spot has no occupied flag. A spot is free exactly when it is in the index. One fact, stored once, cannot drift out of step with itself. - Ticket holds the Spot, not just its id. Leaving needs no lookup, and pricing can read the spot’s size. - Time is a number the caller supplies. entry_time is seconds. Nothing reads the clock, so a test can say “two hours later” without waiting. In production, pass the database clock rather than each server’s own. ### SpotIndex: best fit in O(log n) ``` class SpotIndex: """Free spots only, one min-heap per size: best fit in O(log n).""" def __init__(self, spots: list[Spot]) -> None: self._free: dict[Size, list[tuple[int, Spot]]] = {size: [] for size in Size} for spot in spots: self.give(spot) def take(self, vehicle: Vehicle) -> Optional[Spot]: for size in Size: # SMALL, MEDIUM, LARGE: the smallest that fits wins if size >= vehicle.size and self._free[size]: return heapq.heappop(self._free[size])[1] return None def give(self, spot: Spot) -> None: heapq.heappush(self._free[spot.size], (spot.id, spot)) ``` ``` class SpotIndex { // Free spots only, one min-heap per size: best fit in O(log n). private final List> free = new ArrayList<>(); SpotIndex(List spots) { for (int i = 0; i < Size.values().length; i++) free.add(new PriorityQueue<>(Comparator.comparingInt(Spot::id))); spots.forEach(this::give); } Spot take(Vehicle v) { for (int size = v.size().ordinal(); size < free.size(); size++) { // the smallest that fits wins Spot s = free.get(size).poll(); if (s != null) return s; } return null; } void give(Spot s) { free.get(s.size().ordinal()).add(s); } } ``` ``` class SpotIndex { // Free spots only, one min-heap per size: best fit in O(log n). struct ById { bool operator()(const Spot* a, const Spot* b) const { return a->id > b->id; } }; using Heap = priority_queue, ById>; array free; // indexed by Size (1..3) public: explicit SpotIndex(const vector& spots) { for (const Spot& s : spots) give(&s); } const Spot* take(const Vehicle& v) { for (int size = int(v.size); size <= 3; size++) { // the smallest that fits wins if (free[size].empty()) continue; const Spot* s = free[size].top(); free[size].pop(); return s; } return nullptr; } void give(const Spot* s) { free[int(s->size)].push(s); } }; ``` This is the one class where search speed is decided. It keeps only the free spots , in one min-heap per size, ordered by spot number. - take removes the spot as it returns it. There is no “peek, then mark taken” pair of steps with a gap between them. That gap is where a double booking would come from. - It scans sizes upward. The vehicle’s own size first, then larger ones. That loop is best fit, written in three lines. - It is not thread-safe, on purpose. The lock belongs in one place, ParkingLot. Two classes each taking their own lock is how deadlocks start. - Complexity. A scan is O(n) take and O(1) give back. This heap is O(log n) for both and still returns the nearest spot. A plain stack is O(1) for both but returns any spot. (In Python the heap stores (id, spot): ids are unique, so two Spot objects are never compared.) ### Pricing: the Strategy pattern in action The fee is where requirements change most often, so it is isolated behind one small interface. Each rule gets the ticket, the exit time and the fee so far , and returns a new fee. Pricing runs the rules in order. ``` class PricingRule(ABC): @abstractmethod def apply(self, ticket: Ticket, exit_time: int, fee: int) -> int: """Return the new fee, given the fee so far.""" class PerHour(PricingRule): def __init__(self, rates: dict[Size, int]) -> None: self._rates = dict(rates) # price per started hour, by spot size def apply(self, ticket: Ticket, exit_time: int, fee: int) -> int: hours = max(1, math.ceil((exit_time - ticket.entry_time) / 3600)) return hours * self._rates[ticket.spot.size] class PeakSurcharge(PricingRule): """+50% when the vehicle came in during rush hour.""" PEAK_HOURS = (8, 9, 17, 18) def apply(self, ticket: Ticket, exit_time: int, fee: int) -> int: hour = ticket.entry_time // 3600 % 24 return fee * 3 // 2 if hour in self.PEAK_HOURS else fee class Pricing: def __init__(self, rules: list[PricingRule]) -> None: self._rules = list(rules) def fee(self, ticket: Ticket, exit_time: int) -> int: fee = 0 for rule in self._rules: # each rule gets the fee so far fee = rule.apply(ticket, exit_time, fee) return fee ``` ``` interface PricingRule { /** Returns the new fee, given the fee so far. */ int apply(Ticket t, long exitTime, int fee); } class PerHour implements PricingRule { private final int[] rates; // price per started hour, indexed by Size PerHour(int[] rates) { this.rates = rates.clone(); } public int apply(Ticket t, long exitTime, int fee) { long hours = Math.max(1, (exitTime - t.entryTime() + 3599) / 3600); return (int) hours * rates[t.spot().size().ordinal()]; } } class PeakSurcharge implements PricingRule { // +50% when the vehicle came in during rush hour. public int apply(Ticket t, long exitTime, int fee) { long hour = t.entryTime() / 3600 % 24; boolean peak = hour == 8 || hour == 9 || hour == 17 || hour == 18; return peak ? fee * 3 / 2 : fee; } } class Pricing { private final List rules; Pricing(List rules) { this.rules = List.copyOf(rules); } int fee(Ticket t, long exitTime) { int fee = 0; for (PricingRule rule : rules) fee = rule.apply(t, exitTime, fee); // each rule gets the fee so far return fee; } } ``` ``` struct PricingRule { // Returns the new fee, given the fee so far. virtual int apply(const Ticket& t, long exitTime, int fee) const = 0; virtual ~PricingRule() = default; }; struct PerHour : PricingRule { array rates; // price per started hour, indexed by Size explicit PerHour(array rates) : rates(rates) {} int apply(const Ticket& t, long exitTime, int) const override { long hours = max(1L, (exitTime - t.entryTime + 3599) / 3600); return hours * rates[int(t.spot->size)]; } }; struct PeakSurcharge : PricingRule { // +50% when the vehicle came in during rush hour. int apply(const Ticket& t, long, int fee) const override { long hour = t.entryTime / 3600 % 24; bool peak = hour == 8 || hour == 9 || hour == 17 || hour == 18; return peak ? fee * 3 / 2 : fee; } }; class Pricing { vector> rules; public: explicit Pricing(vector> rules) : rules(std::move(rules)) {} int fee(const Ticket& t, long exitTime) const { int fee = 0; for (auto& rule : rules) fee = rule->apply(t, exitTime, fee); // each rule gets the fee so far return fee; } }; ``` Ticket car, in at 08:00, out at 09:00 → PerHour 1 hour × 20 = 20 → PeakSurcharge rush hour: 20 × 1.5 = 30 → Fee 30 *Figure 4 — Two rules in a pipeline: 1 hour at a rate of 20 is 20, and an 08:00 entry adds 50%, so 30. A motorcycle that enters at 17:00 and stays 20 minutes pays 10 × 1.5 = 15.* - This is the Strategy pattern. PricingRule is the strategy interface, PerHour and PeakSurcharge are interchangeable implementations, and Pricing is the context that uses them without knowing which they are. - Order matters, and the caller owns it. The surcharge must come after the base rate, because it scales the fee so far. That is why the list is ordered and each rule sees the previous fee. - The surcharge looks at the entry hour, not the hours actually spent in rush hour. That is a product decision. Name it, and mention that charging by overlap would need the stay split into intervals. - Rules are pure. They read the ticket and return a number. No state, so each one is a one-line unit test. #### Adding a rule changes nothing that exists A weekend discount of 20%. This block is the whole change: ``` class WeekendDiscount(PricingRule): """-20% when the vehicle came in on a Saturday or Sunday.""" def apply(self, ticket: Ticket, exit_time: int, fee: int) -> int: weekday = (ticket.entry_time // 86400 + 4) % 7 # 0 = Sunday return fee * 4 // 5 if weekday in (0, 6) else fee ``` ``` class WeekendDiscount implements PricingRule { // -20% when the vehicle came in on a Saturday or Sunday. public int apply(Ticket t, long exitTime, int fee) { long weekday = (t.entryTime() / 86400 + 4) % 7; // 0 = Sunday return weekday == 0 || weekday == 6 ? fee * 4 / 5 : fee; } } ``` ``` struct WeekendDiscount : PricingRule { // -20% when the vehicle came in on a Saturday or Sunday. int apply(const Ticket& t, long, int fee) const override { long weekday = (t.entryTime / 86400 + 4) % 7; // 0 = Sunday return weekday == 0 || weekday == 6 ? fee * 4 / 5 : fee; } }; ``` Append it to the list passed to Pricing and it is live. ParkingLot , Pricing and the existing rules are untouched. That is the open/closed principle, shown rather than stated. (Day 0 of Unix time was a Thursday, hence the + 4 : it makes 0 = Sunday and 6 = Saturday.) In the interview Interviewer: “Premium customers pay half price. How much code changes?” You: “One new class implementing PricingRule , and one more entry in the list where the lot is created. The lot and the other rules stay as they are.” ### ParkingLot: the facade that owns the lock This is the class the gates see. park follows the entry flow in Figure 1, with the lock wrapped around it. ``` class UnknownTicketError(Exception): pass class AlreadyParkedError(Exception): pass class ParkingLot: def __init__(self, spots: list[Spot], pricing: Pricing) -> None: self._index = SpotIndex(spots) self._pricing = pricing self._open: dict[int, Ticket] = {} self._plates: set[str] = set() self._ids = count(1) self._lock = Lock() def park(self, vehicle: Vehicle, now: int) -> Optional[Ticket]: """Return a ticket, or None when the lot is full.""" with self._lock: # find + take + ticket is one step if vehicle.plate in self._plates: raise AlreadyParkedError(vehicle.plate) spot = self._index.take(vehicle) if spot is None: return None ticket = Ticket(next(self._ids), vehicle.plate, spot, now) self._open[ticket.id] = ticket self._plates.add(ticket.plate) return ticket def unpark(self, ticket_id: int, now: int) -> int: """Return the fee. Raises UnknownTicketError for an unknown or used ticket.""" with self._lock: ticket = self._open.pop(ticket_id, None) if ticket is None: raise UnknownTicketError(ticket_id) self._plates.discard(ticket.plate) self._index.give(ticket.spot) return self._pricing.fee(ticket, now) ``` ``` class UnknownTicketException extends RuntimeException { UnknownTicketException(int id) { super("unknown ticket " + id); } } class AlreadyParkedException extends RuntimeException { AlreadyParkedException(String plate) { super("already parked: " + plate); } } class ParkingLot { private final SpotIndex index; private final Pricing pricing; private final Map open = new HashMap<>(); private final Set plates = new HashSet<>(); private int nextId = 1; ParkingLot(List spots, Pricing pricing) { this.index = new SpotIndex(spots); this.pricing = pricing; } /** Returns a ticket, or null when the lot is full. */ synchronized Ticket park(Vehicle v, long now) { // find + take + ticket is one step if (plates.contains(v.plate())) throw new AlreadyParkedException(v.plate()); Spot spot = index.take(v); if (spot == null) return null; Ticket t = new Ticket(nextId++, v.plate(), spot, now); open.put(t.id(), t); plates.add(t.plate()); return t; } /** Returns the fee. Throws UnknownTicketException for an unknown or used ticket. */ synchronized int unpark(int ticketId, long now) { Ticket t = open.remove(ticketId); if (t == null) throw new UnknownTicketException(ticketId); plates.remove(t.plate()); index.give(t.spot()); return pricing.fee(t, now); } } ``` ``` struct UnknownTicket : runtime_error { explicit UnknownTicket(int id) : runtime_error("unknown ticket " + to_string(id)) {} }; struct AlreadyParked : runtime_error { explicit AlreadyParked(const string& plate) : runtime_error("already parked: " + plate) {} }; class ParkingLot { SpotIndex index; Pricing pricing; unordered_map open; unordered_set plates; int nextId = 1; mutex lock; public: ParkingLot(const vector& spots, Pricing pricing) : index(spots), pricing(std::move(pricing)) {} // Returns a ticket, or nullopt when the lot is full. optional park(const Vehicle& v, long now) { lock_guard guard(lock); // find + take + ticket is one step if (plates.count(v.plate)) throw AlreadyParked(v.plate); const Spot* spot = index.take(v); if (!spot) return nullopt; Ticket t{nextId++, v.plate, spot, now}; open[t.id] = t; plates.insert(t.plate); return t; } // Returns the fee. Throws UnknownTicket for an unknown or used ticket. int unpark(int ticketId, long now) { lock_guard guard(lock); auto it = open.find(ticketId); if (it == open.end()) throw UnknownTicket(ticketId); Ticket t = it->second; open.erase(it); plates.erase(t.plate); index.give(t.spot); return pricing.fee(t, now); } }; ``` - The lock covers the whole read-modify-write. Checking the plate, taking the spot and recording the ticket happen as one step. The concurrency deep dive below shows what goes wrong without that. The section itself is small (a heap pop and a map insert), and the fee calculation in unpark could move outside it if pricing became expensive. - Two kinds of failure, handled in two ways. A full lot is an expected outcome, so park returns none. An unknown ticket or a duplicate plate is a caller error, so it raises a named exception that a caller can catch by type. - A used ticket leaves the map at once. A second exit with the same ticket finds nothing and is rejected, so it cannot free a spot someone else now holds. The plate set keeps a plate from being inside twice the same cheap way; the database version is a unique index (see the data model below). ### Run it One test, three languages. It checks best fit with overflow into a larger spot and then “full”, 50 cars from 16 threads against 10 spots, the fees, the duplicate plate and the unknown ticket. The comments show what each line prints. ``` from concurrent.futures import ThreadPoolExecutor rates = {Size.SMALL: 10, Size.MEDIUM: 20, Size.LARGE: 40} pricing = Pricing([PerHour(rates), PeakSurcharge(), WeekendDiscount()]) # Best fit: a car takes the medium spot, the next car overflows into large, then full. lot = ParkingLot([Spot(1, 1, Size.SMALL), Spot(2, 1, Size.MEDIUM), Spot(3, 2, Size.LARGE)], pricing) first = lot.park(Vehicle("A", Size.MEDIUM), now=0) second = lot.park(Vehicle("B", Size.MEDIUM), now=0) third = lot.park(Vehicle("C", Size.LARGE), now=0) print(first.spot.id, second.spot.id, third) # 2 3 None # 50 cars, 10 spots, 16 threads: exactly 10 tickets, no spot twice. lot = ParkingLot([Spot(i, 1, Size.MEDIUM) for i in range(1, 11)], pricing) cars = [Vehicle(f"CAR-{i}", Size.MEDIUM) for i in range(50)] with ThreadPoolExecutor(max_workers=16) as pool: results = list(pool.map(lambda car: lot.park(car, now=0), cars)) got = [t for t in results if t] print(len(got), len({t.spot.id for t in got})) # 10 10 print(lot.unpark(got[0].id, now=3600)) # 20: one hour, off-peak late = lot.park(Vehicle("LATE", Size.MEDIUM), now=8 * 3600) print(lot.unpark(late.id, now=8 * 3600 + 1800)) # 30: 1 h x 20, +50% rush hour sat = 2 * 86400 # day 2 after the epoch is a Saturday ticket = lot.park(Vehicle("WKND", Size.MEDIUM), now=sat) try: lot.park(Vehicle("WKND", Size.MEDIUM), now=sat) except AlreadyParkedError: print("already parked") # the same plate cannot enter twice print(lot.unpark(ticket.id, now=sat + 3600)) # 16: 1 h x 20, -20% weekend try: lot.unpark(999, now=0) except UnknownTicketError: print("unknown ticket") ``` ``` import java.util.concurrent.*; class Test { public static void main(String[] args) throws Exception { Pricing pricing = new Pricing(List.of(new PerHour(new int[]{10, 20, 40}), new PeakSurcharge(), new WeekendDiscount())); // Best fit: a car takes the medium spot, the next car overflows into large, then full. ParkingLot small = new ParkingLot( List.of(new Spot(1, 1, Size.SMALL), new Spot(2, 1, Size.MEDIUM), new Spot(3, 2, Size.LARGE)), pricing); Ticket first = small.park(new Vehicle("A", Size.MEDIUM), 0); Ticket second = small.park(new Vehicle("B", Size.MEDIUM), 0); Ticket third = small.park(new Vehicle("C", Size.LARGE), 0); System.out.println(first.spot().id() + " " + second.spot().id() + " " + third); // 2 3 null // 50 cars, 10 spots, 16 threads: exactly 10 tickets, no spot twice. List spots = new ArrayList<>(); for (int i = 1; i <= 10; i++) spots.add(new Spot(i, 1, Size.MEDIUM)); ParkingLot lot = new ParkingLot(spots, pricing); List got = Collections.synchronizedList(new ArrayList<>()); ExecutorService pool = Executors.newFixedThreadPool(16); for (int i = 0; i < 50; i++) { Vehicle car = new Vehicle("CAR-" + i, Size.MEDIUM); pool.submit(() -> { Ticket t = lot.park(car, 0); if (t != null) got.add(t); }); } pool.shutdown(); pool.awaitTermination(5, TimeUnit.SECONDS); System.out.println(got.size() + " " + got.stream().map(t -> t.spot().id()).distinct().count()); // 10 10 System.out.println(lot.unpark(got.get(0).id(), 3600)); // 20: one hour, off-peak Ticket late = lot.park(new Vehicle("LATE", Size.MEDIUM), 8 * 3600); System.out.println(lot.unpark(late.id(), 8 * 3600 + 1800)); // 30: 1 h x 20, +50% rush hour long sat = 2 * 86400; // day 2 after the epoch is a Saturday Ticket ticket = lot.park(new Vehicle("WKND", Size.MEDIUM), sat); try { lot.park(new Vehicle("WKND", Size.MEDIUM), sat); } catch (AlreadyParkedException e) { System.out.println("already parked"); // the same plate cannot enter twice } System.out.println(lot.unpark(ticket.id(), sat + 3600)); // 16: 1 h x 20, -20% weekend try { lot.unpark(999, 0); } catch (UnknownTicketException e) { System.out.println("unknown ticket"); } } } ``` ``` #include #include Pricing makePricing() { vector> rules; rules.push_back(make_unique(array{0, 10, 20, 40})); // small, medium, large rules.push_back(make_unique()); rules.push_back(make_unique()); return Pricing(std::move(rules)); } int main() { // Best fit: a car takes the medium spot, the next car overflows into large, then full. vector three{{1, 1, Size::SMALL}, {2, 1, Size::MEDIUM}, {3, 2, Size::LARGE}}; ParkingLot small(three, makePricing()); Vehicle a{"A", Size::MEDIUM}, b{"B", Size::MEDIUM}, c{"C", Size::LARGE}; auto first = small.park(a, 0), second = small.park(b, 0), third = small.park(c, 0); cout << first->spot->id << " " << second->spot->id << " " << (third ? "ticket" : "none") << "\n"; // 2 3 none // 50 cars, 10 spots, 16 threads: exactly 10 tickets, no spot twice. vector spots; for (int i = 1; i <= 10; i++) spots.push_back({i, 1, Size::MEDIUM}); ParkingLot lot(spots, makePricing()); vector cars; for (int i = 0; i < 50; i++) cars.push_back({"CAR-" + to_string(i), Size::MEDIUM}); vector> results(50); vector threads; for (int i = 0; i < 50; i++) threads.emplace_back([&, i] { results[i] = lot.park(cars[i], 0); }); for (thread& t : threads) t.join(); set used; int firstId = -1, n = 0; for (auto& r : results) if (r) { n++; used.insert(r->spot->id); if (firstId < 0) firstId = r->id; } cout << n << " " << used.size() << "\n"; // 10 10 cout << lot.unpark(firstId, 3600) << "\n"; // 20: one hour, off-peak Vehicle lateCar{"LATE", Size::MEDIUM}; auto late = lot.park(lateCar, 8 * 3600); cout << lot.unpark(late->id, 8 * 3600 + 1800) << "\n"; // 30: 1 h x 20, +50% rush hour long sat = 2 * 86400; // day 2 after the epoch is a Saturday Vehicle wknd{"WKND", Size::MEDIUM}; auto ticket = lot.park(wknd, sat); try { lot.park(wknd, sat); } catch (const AlreadyParked&) { cout << "already parked\n"; // the same plate cannot enter twice } cout << lot.unpark(ticket->id, sat + 3600) << "\n"; // 16: 1 h x 20, -20% weekend try { lot.unpark(999, 0); } catch (const UnknownTicket&) { cout << "unknown ticket\n"; } } ``` ## Deep dive ### Concurrency: two gates, one spot “Find a free spot” and “mark it taken” are two steps. If two gates interleave them, both see the same spot as free. The first timeline is that bug. The second is the fix. Without a lock: a bug Gate A Gate B Spot 7 is spot 7 free? yes is spot 7 free? yes (still!) park car A park car B Two cars, one spot: car B replaced car A With a lock: correct Gate A Gate B Lot + lock park(car A) park(car B) B waits for the lock ticket for A: spot 7 ticket for B: spot 8 Two cars, two different spots *Figure 5 — A check-then-act race on shared state. Make the check and the change one atomic step.* The fix is to make the check and the change one indivisible step . In this code that is the lock in ParkingLot : the gate that gets it first takes the spot, and the second gate then sees the next one. ### Thread safety: where the lock goes How much to lock, and where, depends on where the state lives: | Where the state lives | How to make “take a spot” atomic | Limit | | --- | --- | --- | | One process | One lock around park and unpark (this code). | Correct and enough for this load. One lock serialises every gate. | | --- | --- | --- | | One process, heavy load | A lock per size pool, so a motorcycle never waits behind a truck. | Taking a larger spot as overflow must lock two pools. Fix the lock order to avoid a deadlock. | | --- | --- | --- | | Several servers | The database arbitrates: FOR UPDATE SKIP LOCKED, plus unique indexes as a safety net. | A process lock does not reach another machine. This is the data model, below. | | --- | --- | --- | SpotIndex and Pricing take no locks of their own. The lock lives in one place, so there is one order of locking and nothing to deadlock on. ### The data model The in-memory code loses every ticket on a restart, and its lock does not reach a second server. In a real system the database holds the truth and the classes above become the logic in front of it. This is the same design, persisted. PostgreSQL is the source of truth, because tickets are money and need transactions and constraints. Redis suits the free-spot counter on a gate display, where a few seconds of staleness is fine. It is a poor ledger. #### lot - PK id - name #### spot - PK id - FK lot_id - floor - size1..3 - statusFREE | OCCUPIED #### ticket - PK id - FK spot_id - plate - hourly_ratesnapshot - entry_time - exit_time - fee - statusOPEN | CLOSED #### rate_card - PK FK lot_id - PK size - hourly_rate - lot 1 : n spot · spot 1 : n ticket over time · rate_card n : 1 lot - index spot_free (lot_id, size, id) WHERE status = FREE - unique one_open_ticket_per_spot and one_open_ticket_per_plate *Figure 6 — Four tables and two partial indexes. hourly_rate is copied into the ticket at entry, so a price change never touches a car that is already parked.* ``` CREATE TABLE lot ( id BIGSERIAL PRIMARY KEY, name TEXT NOT NULL ); CREATE TABLE spot ( id BIGSERIAL PRIMARY KEY, lot_id BIGINT NOT NULL REFERENCES lot (id), floor SMALLINT NOT NULL, size SMALLINT NOT NULL CHECK (size BETWEEN 1 AND 3), -- 1 small, 2 medium, 3 large status TEXT NOT NULL DEFAULT 'FREE' CHECK (status IN ('FREE', 'OCCUPIED')) ); CREATE TABLE ticket ( id BIGSERIAL PRIMARY KEY, spot_id BIGINT NOT NULL REFERENCES spot (id), plate TEXT NOT NULL, hourly_rate INT NOT NULL, -- rate copied at entry, so a price change cannot hit parked cars entry_time TIMESTAMPTZ NOT NULL DEFAULT now(), exit_time TIMESTAMPTZ, fee INT, status TEXT NOT NULL DEFAULT 'OPEN' CHECK (status IN ('OPEN', 'CLOSED')) ); CREATE TABLE rate_card ( lot_id BIGINT NOT NULL REFERENCES lot (id), size SMALLINT NOT NULL, hourly_rate INT NOT NULL, PRIMARY KEY (lot_id, size) ); -- Best fit is one index probe, because only free spots are in this index. CREATE INDEX spot_free ON spot (lot_id, size, id) WHERE status = 'FREE'; -- The database refuses a double booking even if the application has a bug. CREATE UNIQUE INDEX one_open_ticket_per_spot ON ticket (spot_id) WHERE status = 'OPEN'; CREATE UNIQUE INDEX one_open_ticket_per_plate ON ticket (plate) WHERE status = 'OPEN'; ``` Two indexes carry the design. spot_free is a partial index: only free spots are in it, so best fit is one short index probe and the index stays small however many spots are taken. It is the database version of SpotIndex . one_open_ticket_per_spot makes a double booking impossible, and one_open_ticket_per_plate keeps a plate from being inside twice. #### Park: one atomic statement ``` -- park($1 lot, $2 vehicle size, $3 plate): one statement, so it is atomic WITH pick AS ( SELECT id, size FROM spot WHERE lot_id = $1 AND status = 'FREE' AND size >= $2 ORDER BY size, id -- smallest size first = best fit, then lowest number LIMIT 1 FOR UPDATE SKIP LOCKED -- row held by another gate? skip it, take the next one ), taken AS ( UPDATE spot SET status = 'OCCUPIED' FROM pick WHERE spot.id = pick.id RETURNING spot.id, spot.size ) INSERT INTO ticket (spot_id, plate, hourly_rate) SELECT t.id, $3, r.hourly_rate FROM taken t JOIN rate_card r ON r.lot_id = $1 AND r.size = t.size RETURNING id, spot_id; -- 0 rows = lot is full ``` ORDER BY size, id is best fit. FOR UPDATE SKIP LOCKED is the important part: if another gate has already locked the best row, this gate skips it and takes the next one instead of waiting, so concurrent gates take different spots in parallel. The update and the insert are one statement, so a crash cannot leave a spot marked taken with no ticket. #### Unpark: make a repeat harmless ``` -- unpark($1 ticket id): one transaction BEGIN; -- 1. Read what the fee needs. No row = unknown ticket, or it was already used. SELECT entry_time, hourly_rate, spot_id FROM ticket WHERE id = $1 AND status = 'OPEN'; -- 2. The application works out $2 (the fee) with its pricing rules, then closes the ticket. -- "AND status = 'OPEN'" makes a repeated exit harmless: it updates 0 rows. UPDATE ticket SET status = 'CLOSED', exit_time = now(), fee = $2 WHERE id = $1 AND status = 'OPEN' RETURNING spot_id; -- 3. Free the spot, so the index sees it again. UPDATE spot SET status = 'FREE' WHERE id = $3; COMMIT; ``` The AND status = 'OPEN' guard makes the exit idempotent. A retry or a ticket scanned twice updates zero rows the second time, so the spot is never freed twice. The free count for the gate display is SELECT size, count(*) FROM spot WHERE lot_id = $1 AND status = 'FREE' GROUP BY size , answered from spot_free alone. ## Interviewer follow-ups These are the questions that usually come next. Open one to see an answer you could say out loud. Why not just loop over the spots? For 200 spots I would, because it is the simplest thing that works. At 10,000 spots with several gates, every entry would scan the whole lot while holding the lock. The heap keeps that work at O(log n) and still hands out the nearest spot. The trade-off: the heap is a little more code, and it must be updated whenever a spot is taken or given back. That is why take and give are the only two ways in. Two cars arrive at exactly the same time. What happens, and what if there are several servers? That is a check-then-act race: both see spot 7 free. I make the find-and-take one critical section. In one process that is a lock. Across servers it becomes a single database statement with FOR UPDATE SKIP LOCKED , and I add a unique index so the database refuses a double booking even if my code has a bug. The trade-off: one lock serialises every gate, which is fine at 20 events a second. If it ever was not, I would use a lock per size pool and fix the lock order so overflow into a larger pool cannot deadlock. What can go wrong in production, and what is the fix? | Scenario | What goes wrong | Fix | | --- | --- | --- | | App dies between “spot taken” and “ticket written” | A spot is taken with no ticket, and nobody can free it. | One transaction or one statement. In memory, both steps sit inside the same lock. | | --- | --- | --- | | Exit scanned twice, or retried | A spot someone else now holds gets freed. | Close the ticket with WHERE status = 'OPEN'. Zero rows means reject. | | --- | --- | --- | | Prices change while cars are parked | A parked car is repriced. | Copy the rate into the ticket at entry. | | --- | --- | --- | | App servers disagree on the time | Odd or negative durations. | Use the database now() for entry and exit. | | --- | --- | --- | | Lost ticket | No way to find the spot. | Look up the open ticket by plate, and charge the maximum daily fee. | | --- | --- | --- | ## Wrap up The order matters more than the code. We asked questions until the lot was clear, turned the nouns into a handful of small classes, said what each one does, and only then wrote code, so every block was short because its shape was already decided. Then we looked at the two things that decide whether the design survives real use: two gates racing, and state that must outlive a process. ### Design principles applied | Principle | Where it shows up | | --- | --- | | Single responsibility | SpotIndex searches, Pricing prices, ParkingLot coordinates and locks. Each can change for one reason only. | | --- | --- | | Open/closed | WeekendDiscount was added without editing Pricing, ParkingLot or any existing rule. | | --- | --- | | Liskov substitution | Any PricingRule can replace another: same input, same kind of output, no surprises. | | --- | --- | | Dependency inversion | Pricing depends on the PricingRule interface, not on PerHour. The lot depends on Pricing, not on any rule. | | --- | --- | | Composition over inheritance | One Vehicle with a size, and a fee built from a list of rules. There is no class tree to maintain. | | --- | --- | | Explicit failure | Expected outcomes (lot full) return normally. Caller errors (bad ticket, duplicate plate) raise a named exception. | | --- | --- | | Testability | Time is a parameter and the rules are pure, so the whole suite runs without sleeping or mocking. | | --- | --- | ### Patterns used, and not used Strategy for pricing (one interface, interchangeable and stackable implementations) and Facade for ParkingLot (one entry point in front of the index, the tickets and pricing). Observer only if a gate display is asked for, and a cached counter is often simpler. Factory and Singleton are deliberately absent: there is one Vehicle class for a factory to choose, and a singleton hides a dependency and makes tests harder. Naming a pattern you do not need costs more than leaving it out. Interview tip: the closing two minutes Go back through your notes and tick them off: spot choice, tickets and rejection in park and unpark , no double booking with the lock and the unique indexes, fast search with SpotIndex , and new pricing without edits through the rules. Then name what you would do next: per-pool locks, a cached free count for the display, and reservations as a new spot state. Ending on “here is what I did not build, and why” is what makes a design sound finished. --- From Compound Engineer (https://compoundengineer.com), visual lessons for engineers. The page above is the full interactive version.