Design a Parking Lot

A parking lot system works by keeping two pieces of mutable state in sync under concurrency: a per-spot free flag and an aggregate available-count per spot type, both mutated as vehicles enter and leave through multiple physical gates at once. Everything else — tickets, panels, the tiered fee — hangs off that core invariant: a vehicle is admitted only if a compatible spot is genuinely free, and exactly one entry gate may claim it. The interesting engineering is not the class catalog; it is (1) the tiered fee calculation, which is a textbook Strategy candidate, and (2) the race window when two gates issue tickets simultaneously.

The mechanism: admission and the count invariant

Each ParkingFloor owns its spots in per-type maps. The ParkingLot singleton holds, for each spot type, a current occupied count and a hard max…Count. Admission flows through one method, getNewParkingTicket(vehicle):

1. Check fit: isFull(type) asks whether any spot category this vehicle is allowed to use has room. A car may use compact or large; an electric car may use electric, compact, or large; a truck/van needs large only. This fallback is the part most candidates forget.
2. Persist then count: save the ticket to the DB first, then incrementSpotCount. Ordering matters — if you bump the in-memory count and the DB write fails, the lot permanently believes it is one car fuller than reality.
3. Assign a physical spot later, when the car actually parks, which flips that spot's free flag and refreshes the floor's display board.

The decoupling in step 3 is the source of the page's most important bug: the count changes at ticket issue, but the spot flag changes at park time. Treat them as one logical transaction or they drift.

Which spot do you hand out? Step 3 says "assign a spot" but not which — and that is itself a swappable policy. First-fit (any free spot of the type) is O(1) with a per-type free-list (a stack/queue of free spot ids). Nearest-to-entrance orders spots by walking distance, so you keep a min-heap per type keyed on distance — O(log n) to pop the closest and O(log n) to return it on exit. A mall wants nearest; an airport long-stay lot may want to balance floors for even wear/traffic. Make spot selection a strategy so the allocation rule can differ per site without touching admission.

The fee model is the real algorithm

The requirement — $4 for hour 1, $3.5 for hours 2–3, $2.5 for every hour after — is a piecewise tier function over rounded-up hours. The naive version multiplies one flat rate by hours and is simply wrong for any stay longer than an hour. Here it is correctly, with the rate table externalized so a senior engineer can swap pricing without recompiling:

// A fee strategy: given entry/exit, return the charge.
// Externalizing this is what turns the spec's one pricing rule into
// "any pricing rule" (weekend, EV surcharge, flat-rate event days).
public interface ParkingFeeStrategy {
    BigDecimal compute(Instant entry, Instant exit);
}

public final class TieredHourlyFee implements ParkingFeeStrategy {
    // tiers: first N hours at a rate, then the next, then the tail.
    // {firstHourCount, rate} pairs; last entry's count is treated as infinity.
    @Override
    public BigDecimal compute(Instant entry, Instant exit) {
        long minutes = Duration.between(entry, exit).toMinutes();
        // ceil to whole hours: 61 minutes = 2 hours. A partial hour is billed full.
        long hours = Math.max(1, (minutes + 59) / 60);

        BigDecimal total = BigDecimal.ZERO;
        for (long h = 1; h <= hours; h++) {
            BigDecimal rate;
            if (h == 1)            rate = new BigDecimal("4.0");   // first hour
            else if (h <= 3)       rate = new BigDecimal("3.5");   // hours 2-3
            else                   rate = new BigDecimal("2.5");   // 4th hour onward
            total = total.add(rate);
        }
        return total;
    }
}

Why the naive version is wrong: hours * 4.0 over-charges (every hour at the top rate) and a flat hours * someAverage mis-charges short and long stays in opposite directions. Tiered pricing is inherently a fold over hour buckets, not a multiplication. Also note: use BigDecimal, never double — 0.1 + 0.2 != 0.3 in IEEE-754, and money that is off by a cent is a billing-dispute generator.

Worked example: two cars, one open spot, two gates

A lot has maxCompactCount = 1, currently compactSpotCount = 0, and no large spots. Gate A and Gate B each scan a car at the same instant. Trace what the count does:

This is exactly why getNewParkingTicket is declared synchronized on the singleton: it serializes the check-then-act so only one gate can pass isFull when one slot remains. Without the lock, the read-modify-write on the shared counter is a classic TOCTOU (time-of-check to time-of-use) race. With it, Gate B re-reads compactSpotCount = 1, isFull returns true, and B correctly gets a ParkingFullException.

Pitfalls

• TOCTOU on the counter. The whole reason getNewParkingTicket is synchronized. Skip the lock and two gates over-admit (traced above). Note the cost: one global lock serializes every gate in the building — fine for a 500-spot lot, a throughput wall for a city-scale system, where you'd shard the lock per spot type or per floor, or use an atomic CAS / DB row lock instead.
• Count and spot flag drift. incrementSpotCount runs at ticket issue, but the spot's free flag flips at assignVehicleToSpot. A car that takes a ticket and never parks (or a crash between the two) leaves the count high and the spot flagged free forever. Reconcile by deriving counts from the spots themselves, or treating issue+assign as one unit.
• Float money. double for fees silently loses cents. Use BigDecimal and round explicitly.
• Partial-hour rounding undefined. The spec says "per hour" but not how to bill 61 minutes. Decide and document (this design ceils). Off-by-one here is a real customer complaint, not a theoretical edge.
• Stub isFull(type) forgetting fallback categories. A car rejected because compact is full while large spots sit empty is a correctness bug, not just rudeness. The allowed-category union in isFull is load-bearing.
• Display board staleness. The board caches "a" free spot; once that one fills it must scan for the next. Update it on every assign/free or it advertises a taken spot.

Selection & trade-offs: pricing as Strategy vs the alternatives

The fee rule is the one place this design must absorb change — pricing teams revise it constantly (weekend rates, EV surcharge, validation discounts, flat event-day pricing). How you model it is a senior-level decision.

Decision signal: reach for Strategy the moment pricing must vary independently of the vehicle/ticket or be chosen at runtime (config, A/B test, per-lot). Choose Strategy when the rule is a swappable, runtime-selected policy; prefer Template Method when every rule is genuinely the same algorithm with one varying table and you'll never select per-request; prefer plain if/else when there is exactly one rule that will never change and adding a class is pure ceremony. For this lot — pricing changes often and may differ per location — Strategy wins; the extra class pays for itself the first time pricing changes without a redeploy of admission logic.

The Singleton on ParkingLot is a separate, more contentious choice: it gives every gate one shared source of truth for the counter (which the lock then protects), but it also hard-wires global state that fights unit testing. In production you'd usually inject one ParkingLot instance via DI rather than a static getInstance() — same single-instance guarantee, testable, no hidden global.

Takeaways

• The core of this problem is a concurrent capacity counter: check-then-act under a lock, with persistence ordered before the in-memory increment.
• The tiered fee is a fold over hour buckets in BigDecimal, not a flat multiply — and it's the natural home for the Strategy pattern because pricing changes constantly.
• Watch the two independent pieces of state — aggregate count and per-spot free flag — they must be reconciled or they drift.
• Singleton gives a shared counter but couples global state; prefer dependency injection for the same guarantee with testability.

Based on the Grokking the Object Oriented Design Interview "Parking Lot" problem (DesignGurus / educative.io) for the requirements and class roster. Mechanism trace, concurrency (TOCTOU) analysis, BigDecimal tiered-fee implementation, and the Strategy-vs-Template-Method-vs-if/else and Singleton-vs-DI trade-off treatment re-authored and deepened for this guide; pattern guidance per Gang of Four, Design Patterns. Code corrected to compile (BigDecimal money, ceil rounding, allowed-category fallback in isFull).