Why this matters: in the implementation act, interviewers mostly go quiet and watch one thing — whether your code matches your words. Every seam you claimed in the design should be visible in the structure; every invariant you stated should have an enforcement point. This walkthrough builds the core in Java-ish pseudocode, in the order you'd write it live.
The vocabulary types
Sizes first, because the fit rule sits on them. An ordered enum makes "fits" a comparison instead of a case analysis:
enum SpotSize { SMALL, MEDIUM, LARGE } // ordinal order matters
class Vehicle {
final String plate;
final SpotSize requiredSize; // motorcycle -> SMALL, car -> MEDIUM, truck -> LARGE
}
class Spot {
final String id;
final int floor;
final int distanceFromGate; // feeds the "nearest" policy
final SpotSize size;
Ticket activeTicket = null; // null == free
boolean fits(Vehicle v) { return size.ordinal() >= v.requiredSize.ordinal(); }
boolean isFree() { return activeTicket == null; }
}Note where fits lives: one method, one comparison. In your interview, say that out loud as you write it — "this is the only place the compatibility rule exists."
The ticket
class Ticket {
final String id;
final String plate;
final Spot spot;
final Instant entryTime;
Instant exitTime = null; // set at close
boolean isActive() { return exitTime == null; }
}The ticket records everything exit needs: which spot to free, and the timestamps the charge is computed from. Nothing else in the system stores the vehicle→spot association — that's the "exactly one active ticket per occupied spot" invariant made structural.
Availability: per-size free lists
The naive lot scans every spot on every arrival — O(N) per park, and an interviewer will make you say so. The design answer is an index: keep the free spots grouped by size, ordered by distance from the gate.
class ParkingLot {
// free spots only, keyed by size, ordered nearest-first
Map<SpotSize, TreeSet<Spot>> freeBySize; // comparator: distanceFromGate
Map<String, Ticket> activeTickets; // ticketId -> Ticket
SpotAssignmentStrategy strategy;
PricingTable pricing;
}Two things to narrate here. First, the free lists are the availability answer — isFull(size) is "is every compatible set empty," floor displays derive from the same structure, no separate counters to drift. Second, the TreeSet ordering bakes "nearest" into the data structure so the strategy's scan is cheap.
The assignment strategy
interface SpotAssignmentStrategy {
Optional<Spot> findSpot(Vehicle v, Map<SpotSize, TreeSet<Spot>> freeBySize);
}
class NearestSmallestFit implements SpotAssignmentStrategy {
Optional<Spot> findSpot(Vehicle v, Map<SpotSize, TreeSet<Spot>> freeBySize) {
// smallest size that fits, then nearest within it; step up only if empty
for (SpotSize s : SpotSize.values()) {
if (s.ordinal() < v.requiredSize.ordinal()) continue; // uses THE fit rule's ordering
TreeSet<Spot> candidates = freeBySize.get(s);
if (!candidates.isEmpty()) return Optional.of(candidates.first());
}
return Optional.empty();
}
}Walking the sizes smallest-fit-first implements the policy from our requirements; candidates.first() is "nearest" courtesy of the comparator. The whole policy is ~10 lines, and swapping it later touches nothing else — which is the entire reason it's an interface.
park(): entry, end to end
Ticket park(Vehicle v) {
Optional<Spot> chosen = strategy.findSpot(v, freeBySize);
if (chosen.isEmpty()) throw new LotFullException(v.requiredSize); // the refusal path
Spot spot = chosen.get();
freeBySize.get(spot.size).remove(spot); // no longer available
Ticket t = new Ticket(newId(), v.plate, spot, now());
spot.activeTicket = t; // spot occupied
activeTickets.put(t.id, t);
return t;
}Narrate the invariant enforcement: the spot leaves the free list and gains its ticket in the same flow — there is no state where a spot is both "free" and ticketed. And the full-lot case is a first-class outcome, not a null that surprises the caller.
unpark(): exit, end to end
Charge unpark(String ticketId) {
Ticket t = activeTickets.remove(ticketId);
if (t == null || !t.isActive()) throw new InvalidTicketException(ticketId);
t.exitTime = now();
Charge charge = pricing.price(t.spot.size, Duration.between(t.entryTime, t.exitTime));
t.spot.activeTicket = null; // spot free again
freeBySize.get(t.spot.size).add(t.spot); // back in availability
return charge;
}Exit operates purely on the ticket — look it up, price it, free its spot. The pricing call is one line because pricing is a table:
class PricingTable {
Map<SpotSize, Money> hourlyRate;
Charge price(SpotSize size, Duration parked) {
long hours = ceilHours(parked); // partial hours round up — one place
return new Charge(hourlyRate.get(size).times(hours));
}
}What you'd say about complexity
With per-size free lists: park is O(number of sizes) set lookups plus an O(log F) tree operation — effectively O(1) for three sizes; unpark is O(log F) for the re-insert, hash lookups otherwise; space is O(spots + active tickets). Say the honest version too: without the index, park degrades to an O(N) scan — the index is what you traded that for.
Key takeaway
The implementation is the design made checkable: an ordered size enum makes fit one comparison, per-size nearest-ordered free lists make assignment O(1)-ish and availability single-sourced, park() moves a spot from free to ticketed atomically with a real refusal path, and unpark() runs entirely off the ticket. If your code's structure lets an interviewer point at each design claim, the act is won.