Parking Lot

Vehicle Parking System

Design a multi-floor parking lot that assigns each vehicle a spot it fits, issues a ticket, and charges for the stay, while many gates park and release cars at once.

Overview

A parking lot has floors, each floor has spots of a few sizes, and vehicles of a few types arrive at the gates. The system must find a spot the vehicle fits, hand back a ticket, and when the vehicle leaves, free the spot and compute the fee. Everyone knows the domain, so the interviewer can spend the whole hour on your design choices.

The problem tests three things. First, how you model a rule table (which vehicle fits which spot) so that a new vehicle type is a data change, not a new branch in the code. Second, how you keep allocation fast and safe when several gates park vehicles at the same moment: two gates must never be given the same spot. Third, whether you can separate the parts that change often (pricing) from the parts that do not (the layout), which is where the Strategy pattern earns its place.

A strong answer names the entities in the first two minutes, states the fit rule as a table, explains where the lock lives and why, and writes a small program that a test can drive with a fake clock.

Scoping the problem

Before writing code, ask these questions; each answer changes the design a little.

Which vehicle types and spot sizes exist? — Fixes the fit table — Bike, car, truck; small, compact, large
May a smaller vehicle use a bigger spot? — Decides whether the fit rule is a set of sizes or one size — Yes: a car may take a large spot
Prefer the smallest fit, or the nearest floor? — Best fit keeps large spots for trucks; nearest floor is friendlier to drivers — Best fit, then lowest floor
How is the fee computed? — Hourly, flat daily, per type; this is the part that changes most — Per started hour, by vehicle type
How many entry and exit gates run at once? — Decides whether locks are needed and how fine they are — Several; allocation must be safe
What does a full lot do? — Refuse at the gate, or queue — Refuse with a clear error
Do tickets or payments persist across restarts? — Adds a store; not part of the core — Follow-up, not the core

The fit rule as data

The rule 'bikes take small spots, cars take compact or large, trucks take large' is a table, and a table should be a dictionary, not an if-else chain. Sizes are listed smallest first, so trying them in order gives best fit for free.

Bike — small
Car — compact, then large
Truck — large

Adding a van that takes compact or large spots is one new dictionary entry, and no method changes. That is the Open/Closed idea in one line, and interviewers listen for it.

Core entities

The composition arrows matter. A spot belongs to exactly one floor, and a floor to exactly one lot, so those are filled diamonds. The lot only refers to its pricing strategy, which can be swapped at runtime, so that is a plain arrow.

Entry and exit

Entry tries each allowed size across the floors and stops at the first free spot. Exit looks the ticket up, frees the spot, and asks the pricing strategy for the fee.

The trace below is the demo in the implementation. Floor 0 has one spot of each size; floor 1 has one compact spot.

1 — park(bike) — 0-S0 — The only size a bike may use
2 — park(car) — 0-C0 — Compact is tried before large
3 — park(car) — 1-C0 — All compact spots on every floor are tried before any large spot
4 — park(truck) — 0-L0 — Still free because step 3 did not take it
5 — park(car) — refused — No compact or large spot left
6 — leave(car from step 2) after 90 min — fee 6 — 90 minutes rounds up to 2 started hours at 3 each

Where the lock lives

Two gates can call park in the same millisecond. Without a lock, both could read 'spot 0-C0 is free' and both could be given it: a check-then-act race. The fix is to make the check and the take one atomic step. The code keeps one lock per floor around its free lists, and a second lock in the lot around the ticket table. Gates working on different floors never wait for each other.

No lock, check spot.vehicle is None then assign — No: two gates can win the same spot — none — The classic bug
One lock per spot, try each spot in turn — Yes — low — Scans every spot on a busy floor: O(spots) per park
One lock per floor around free lists per size (the code below) — Yes — low — O(1) to take or return a spot; floors are independent
One lock for the whole lot — Yes — high — Simplest; fine for one gate

The free list per size is what makes allocation O(1). A deque per size holds the free spots; take pops from the left and release appends. The lot never scans occupied spots.

Pricing as a strategy

The fee formula changes more often than anything else in this system: hourly, flat daily, a free first half hour, a per-type rate. Putting it behind a PricingStrategy interface means the lot never contains a formula, and a new plan is a new class. The demo swaps HourlyPricing for FlatDailyPricing at runtime and the lot does not notice.

HourlyPricing — started hours × rate for the vehicle type, at least 1 hour — ceil(5400 ÷ 3600) = 2 hours, fee 6 — 30 hours = 30 × rate
FlatDailyPricing — started days × price, at least 1 day — 1 day, fee 20 — ceil(30 ÷ 24) = 2 days, fee 40

Time is passed in as a number (now) rather than read from the clock inside the class. That is why the demo can assert exact fees.

What you will be able to do

Name the entities and draw their ownership arrows in the first minutes of the interview.
State the fit rule as a table and turn it into a dictionary that makes new vehicle types a data change.
Explain the check-then-act race at the gate and place the lock at the floor, with the trade-offs of coarser and finer locks.
Keep fees out of the lot with a Strategy object, and swap it at runtime.
Drive the whole design from a test with a fake clock, including the full-lot and double-exit failure cases.

Functional requirements

Several floors, each with spots of three sizes: small, compact, large
Three vehicle types: bike, car, truck; each may use a fixed set of spot sizes
park(vehicle, now) assigns the smallest fitting free spot on the lowest floor and returns a ticket, or refuses when none fits
leave(ticket_id, now) frees the spot and returns the fee; a ticket can leave once
Fees come from a pluggable pricing strategy (per started hour by vehicle type, or flat per day)
availability() reports free spots per floor and size

Non-functional requirements

Taking or returning a spot is O(1): free lists per size, no scan of occupied spots
Safe for many gates at once: a spot is never given to two vehicles
Locks are per floor, so floors do not contend with each other
Adding a vehicle type or a pricing plan changes data or adds a class; no method is edited
Deterministic: time is injected, so fees are exact in tests

Interview questions

How would you add electric vehicle charging spots?
Two gates park a car at the same moment. Walk me through what could go wrong and how your code prevents it.
Why best fit across all floors instead of the first free spot on the nearest floor?
How would you make tickets survive a restart?
What would you show on the display board at the entrance, and how do you keep it correct?