Parking Lot
Allocate a compatible space, issue a ticket, calculate a fee and release the space without double allocation.
Allocate a compatible space, issue a ticket, calculate a fee and release the space without double allocation. This worked design targets SDE-1; the scale figures below are exercise assumptions, not claims about a named company's implementation.
Clarify the prompt
| Ask the interviewer | Decision to record |
|---|---|
| Are spaces assigned or is admission capacity-only? | Assigned spaces require ownership of a specific spot. |
| Which vehicle types, accessible spaces and charging policies are supported? | Eligibility is a rule, not just vehicle size. |
| Can gates operate offline? | Offline allocation needs disjoint inventories or admission must pause. |
Requirements and scope
The core deliverable is: Allocate a compatible space, issue a ticket, calculate a fee and release the space without double allocation. The first design implements the APIs below and the state constraints in the data model. Agree the latency, freshness, retention and failure policy before adding infrastructure. Every successful acknowledgment must have an explicit meaning: accepted intent, committed state or completed external work. These are separate milestones.
Capacity and bottleneck reasoning
Assume 2,000 spaces, four gates and a peak of 20 arrivals/s. At 250 bytes per ticket and 10,000 tickets/day, raw ticket growth is 2.5 MB/day. A transactional database is sufficient; gate hardware latency dominates.
Keep average and peak demand separate. Add replication, indexes, retries and safety headroom to raw arithmetic before selecting capacity. Load-test the busiest ownership key and recovery traffic as well as uniform happy-path throughput.
APIs and data model
- POST /tickets {vehicleType, requestKey} -> 201 ticket or 409 full
- POST /tickets/{id}/pay {requestKey} -> payment status
- POST /tickets/{id}/exit -> closed ticket; GET /availability?type=car
spot(spot_id PK, floor, kind, status, version)
ticket(ticket_id PK, vehicle, spot_id, entry_at, exit_at, tariff_version, status)
UNIQUE active ticket per spot; payment(operation_key UNIQUE, ticket_id, amount_minor, status)Authorize resource ownership at the API boundary; do not trust IDs or state supplied by a client. Bind retry identity to the caller and payload for mutating operations. Reject an incompatible replay instead of returning an unrelated stored result.
Component relationships
Read the diagram
Follow the labeled relationship panels; they are separate directed paths, not one global timeline.
Step-by-step design
1. Establish the authority
Keep allocation rules behind a policy function: filter by eligibility, then choose a space. In a transaction lock a candidate row, mark it occupied and insert the ticket. A uniqueness constraint is the final defense against two gates selecting the same spot.
2. Make retries and concurrent work safe
Persist the price policy version on entry. Compute fees using integer minor currency units and explicit rounding. Payment authorization and physical exit are separate durable transitions; a gate timeout does not prove the car never left.
3. Scale and recover the critical path
Release a spot only when the exit policy is satisfied. Sensor discrepancies create reconciliation work. Publish display counts asynchronously; an available-space display never grants a reservation.
Worked request and concurrency example
Gates A and B both observe spot S7 as available. A locks S7 and commits ticket T1. B either waits and rechecks or chooses another unlocked candidate; it cannot commit T2 for S7. If A loses its HTTP response, retrying its request key returns T1. A stale display may still show one vacancy, but a later request receives full. This separates useful approximate information from authoritative allocation.
Failure and recovery walkthrough
Crash after payment capture but before the gate response: query the provider using the same payment identity, reconcile its status, then retry opening the gate under an audited policy. Never charge again merely because a timeout occurred.
Read the diagram
This numbered trace follows one scenario; explain the durable evidence at each transition.
Deep dive: compatibility, occupancy and a real exit
Start with one lot and one transactional database. This original exercise assigns a physical space, issues a ticket, records payment and confirms departure. It excludes advance reservations, valet movements and dynamic pricing until the baseline works. Gates/controllers are clients of the service; a free-space display or a vehicle sensor does not independently own allocation.
Separate fit from eligibility
| Space | Vehicle sizes allowed by this exercise | Additional eligibility |
|---|---|---|
| Small | Motorcycle | Must be open for allocation |
| Standard | Motorcycle, car | Choose a smaller fitting space first where policy allows |
| Large | Motorcycle, car, van | Preserve scarce large spaces through least-sufficient-fit policy |
| Accessible/charger attributes | Apply independently of the size column | Require the appropriate permit or charger requirement under the declared policy |
Do not encode every combination as a new subclass or use size alone to decide accessibility. A policy filters eligible spaces and orders candidates; the database chooses the actual winner. Product rules about non-EV use of chargers or temporary accessibility restrictions must be explicit. LLD can model policy interfaces and entities later; HLD must first show the authoritative allocation and gate workflow.
space(lot_id, space_id, size, accessible, charger, state, version)
ticket(id, lot_id, vehicle_id, space_id, entry_at, tariff_version,
state, closed_at, exit_operation_id)
entry_request(lot_id, gate_principal, request_key, payload_hash, ticket_id)
UNIQUE active ticket per (lot_id, space_id)
UNIQUE active ticket per (lot_id, vehicle_id) under this lot policyAn active ticket includes payment-pending and exit-uncertain states, not just unpaid parking. PostgreSQL can express an active-ticket uniqueness guard with a partial unique index using a stable predicate such as closed_at IS NULL. Do not put now() in the index predicate to make eligibility expire automatically. Closing a ticket is a controlled state transition, not an inference from elapsed time. See PostgreSQL CREATE INDEX for the actual partial-index restrictions.
Allocate and acknowledge one ticket
In a short transaction, resolve the scoped entry key, select an eligible candidate, lock/recheck it, mark occupancy and insert the ticket and request result. Unique constraints are the final defense. If no candidate survives, return full/conflict under a bounded retry policy. Do not hold a transaction open while waiting for a gate device.
Gates A and B both see S7 as free. A commits ticket T1; B must re-evaluate or receive no space, not also acknowledge T2 for S7. If A loses its response, the same key and fingerprint return T1. A different vehicle under that key is a conflict. Approximate display counts can lag and reconcile asynchronously; the allocation predicate cannot.
Payment does not prove physical departure
| State | Meaning | What may happen next |
|---|---|---|
| parked | Active space ownership | Create/resolve one payment operation |
| payment_pending/unknown | Provider result unresolved | Query/retry the same payment identity |
| exit_authorized | Payment/exit policy satisfied | Submit a bounded gate-open operation |
| exit_uncertain | Gate or passage evidence incomplete | Reconcile controller/sensor/staff evidence |
| closed | Departure accepted under policy | Release the matching space once |
Pin the tariff version on entry and store the fee quote with its calculation time and policy. For an illustrative tariff of 100 minor units per started 30-minute block, 61 minutes costs 300. Equality, grace periods, maximum stay and clock rules are product choices. Recomputing an old payment under a newly changed tariff can create an incompatible retry.
Read the diagram
Payment P is captured for ticket T1 → Gate-open response is lost → T1 stays active; its space stays occupied → Passage or controller evidence resolves exit → Close T1 and release its matching space once
If payment succeeds but the gate response is lost, reconcile the same payment and gate identities. Recharging does not repair the gate, and immediately releasing the space can double-allocate a still-occupied bay. Define which passage event or authorized staff action closes the ticket. Duplicate passage events close only the matching active ticket; an old event cannot release a space now held by another ticket. Emergency egress is a physical safety policy with an audit trail, not a reason to make occupancy accounting guess silently.
Keep hardware and scale boundaries honest
A single lot rarely needs a distributed database for correctness. If a serialized allocation decision takes 10 ms under the example workload, one contended allocation boundary has an ideal ceiling around 100/s before overhead. Partition independent lots or shorten the critical section before adding more API callers. Measure conflict, gate latency, active uncertain exits and display discrepancies separately.
Offline admission requires disjoint preallocated inventory or another safe authority. A cached free count shared by disconnected gates cannot prevent double allocation. During a database outage the product may stop admission while an independently defined emergency-exit procedure remains available. State that availability trade-off directly.
Parking assessment: prove one owner and one release
Question: A car fits a large space, but a standard space is available. Must the service always choose the large one because it is physically valid?
Show answer and explanation
Answer: No. Eligibility and ranking policy are separate. Under least-sufficient-fit, choose a valid standard candidate to preserve large capacity, while the atomic allocation still resolves races.
Question: Capture succeeded but no passage evidence exists after a gate timeout. May the space be advertised as free authoritatively?
Show answer and explanation
Answer: No under this contract. Keep the active ticket/occupancy, reconcile gate/passage evidence and resolve the exit without charging again.
Question: A duplicate old exit event arrives after S7 has a new ticket. May it free S7 again?
Show answer and explanation
Answer: No. Close/release checks the matching active ticket and exit identity; a repeated or obsolete event produces no second occupancy change.
Score one point each for explicit compatibility policy, atomic allocation/unique guards, tariff/payment identity, physical-exit uncertainty and idempotent matching release. Explain the service boundary before optional classes or inheritance diagrams.
Decisions and alternatives
| Decision | Trade-off |
|---|---|
| Alternative 1 | Row-level locking gives a simple ownership boundary but hot entrances can contend. A capacity counter is cheaper only if the product does not assign spots. |
| Alternative 2 | A single database is easier to operate than per-gate partitions. Disjoint gate inventories permit offline service but waste capacity when arrivals are uneven. |
Operational contract
Monitor allocation conflicts, gate command failures, payment uncertainty age and sensor-versus-ticket mismatch. Alert on any spot with more than one active ticket. Reconcile by spot and ticket identity rather than rewriting aggregate counts.
Choose alert thresholds from the agreed user-facing objective. Assign an owner for stuck work and a replay/repair procedure that preserves the original business identity. Bound queue depth, concurrency and recovery throughput so an outage does not produce an uncontrolled catch-up burst.
Foundation, senior and staff depth
- Foundation: Separate vehicle compatibility from allocation policy and enforce one active ticket per space.
- Senior: Resolve payment and gate uncertainty without guessing physical departure.
- Staff: Defend offline admission authority and reconcile obsolete hardware events.
Practice before revealing the answer
Spend 45 minutes: 5 clarifying scope, 7 on capacity/APIs/state, 12 on the first architecture, 15 on the concurrency and failure examples, and 6 on trade-offs and operations. Draw your own design before comparing it with this chapter.
Question: Can a gate allocate from a cached free-space count during a database outage?
Show answer and explanation
Answer: Only if the contract explicitly assigns it a disjoint offline inventory or another safe authority. A shared cached count permits overselling; otherwise stop new admissions while allowing an audited emergency exit policy.
Verification and rollout
Race entry requests and replay scoped keys with changed payloads. Lose gate acknowledgements after payment, then replay old passage events against a newly occupied space. Verify matching-ticket release and tariff boundaries.
Primary technical reference
Official documentation for the mechanism used in this exercise. This lesson is an original interview design, not a description of undisclosed company internals.
Related study
Before this design, review these mechanisms and identify which owns the critical state transition:
Use the Interview Playbook to adapt the depth and timing, then return to the question breakdown overview.