Parking Spot Finder

The problem

"Design an app that finds parking near where you're going." The driver types a destination, sees the garages within 1 km with how many spots each has free right now, and can reserve a spot for the time they'll arrive.

This practice problem reuses Design Nearby Places with the holds of Design Ticketmaster. What's new is live data: free spots change every minute, reported by the gates, and a reservation is a hold that starts hours later. Park street meters and turn-by-turn directions.

The numbers

From the interviewer: 20,000 garages, and at rush hour each one's gates let a car in or out about every 5 seconds. Drivers make about 2,000 searches a second at that time.

• Count changes: one every 5 seconds is a fifth of a change a second, so 20,000 ÷ 5 = 4,000 changes a second.
• Changes per search: 4,000 ÷ 2,000 = 2. Nearby Places had 20,000 searches for each edit: here the data changes faster than people read it.
• Size: at about 100 bytes a garage, all 20,000 take about 2 MB: freshness matters, not size.

Live counts: a cache per cell

As in Nearby Places, a search reads the destination's cell and the 8 around it. Each garage found also needs its free count:

• A search index rebuilt every 5 minutes, as in Nearby Places, is too old: in 5 minutes a busy garage lets about 60 cars in or out, so one shown with 10 free can be full when you arrive.
• The database, on every search, is too busy: 2,000 searches × 9 cells = 18,000 reads a second, plus the 4,000 updates, is 22,000, more than 4× the 5,000 simple lookups one database server answers.
• A cache with each cell's garages and their free counts, updated by every gate event, takes the same 22,000 a second well under the 100,000 one cache server answers. Keep a replica.

The garage service writes each change to the database and to the garage's cell entry, so counts are seconds old. As in Hotel Booking, the search shows and the reservation decides.

Reservations: a reserved count per hour

GET /garages/nearby?lat=40.75&lng=-73.99
  → 200 [{"garage": "g7", "free": 18, "price": …}, …]

POST /reservations {"garage": "g7", "arrive": "18:00",
                    "leave": "21:00", "idempotency_key": "k3"}
  → 201 {"id": "r5", "held_until": "18:15"}

At 14:00, Ana reserves garage g7 for 18:00 to 21:00. Lowering the live free count, the cars inside now, would hide a spot for 4 hours. Holding spot B-14 like a Ticketmaster seat fails too: most garages don't assign spots.

The fit is Hotel Booking's nights, by the hour. Say g7 offers 50 of its spots for reservations each hour. Each hour has a row counting its reservations, and her stay, 18:00 up to 21:00, takes 3 of them: one transaction, one conditional update per hour, reserved < 50, checking and adding in one step like Ticketmaster's hold. If any hour is full, none is taken.

hour    before   after
18:00   31       32
19:00   28       29
20:00   15       16

The gate keeps her spot. Say g7 has 500 spots and at 17:50 holds 470 cars, so 30 are empty; of the 32 reservations for 18:00, 20 cars are in and 12 are still coming. Drivers without a reservation see 30 − 12 = 18 free.

No-shows: give the spot back once

Her spot is held until 18:15, 15 minutes past her arrival time, and at 18:15 the gate hasn't seen her car. Unlike a Ticketmaster hold, nothing frees itself: a seat row carried its own expiry, but here a number counts reservations, and her 1 stays in it until something takes it off.

So a job runs every minute (or a delayed message set at booking). It marks r5 expired only if it's still waiting and gives back its 3 hours in the same transaction. Without that condition, a job run twice after a crash, or racing Ana's car at 18:15, gives her hours back twice or while she's parked: this is Hotel Booking's cancel-once update.

Gate events: ids and a nightly recount

Each gate sends an event for every car in or out, and the garage service adds or subtracts 1 in one atomic step.

• Resends: a gate whose reply was lost sends an entry again; a gate offline for 10 minutes sends the events it saved. An id on each event, the gate and a number counting up, lets the service apply each once, as with Idempotency Keys.
• Order: an exit from gate 2 arriving before an earlier entry from gate 1 is harmless: adds and subtracts give the same total in any order. So are two cars at two gates at once, since each change is one atomic add.
• Drift: a car that slips in behind another sends no event, and a sensor that reads a trailer as a second car sends one too many. No id catches that, and a count off by 3 cars a day would be 90 off within a month. So once a night, at the quietest hour, count the cars really inside and set the count to match, as Payment System checks its records against the bank.

Same pattern as Nearby Places and Ticketmaster

Finding garages is Nearby Places: positions in cells, the destination's cell and its neighbors. The reservation is Ticketmaster's hold: one conditional update that checks and takes in one step, with an end time. What changed: the counts are live, and the hold starts at an arrival time.

Summary

• Scope: free counts near a destination, and reservations for later.
• Numbers: about 4,000 count changes a second, 2 for every search.
• Live counts: a cache per cell, updated by every gate event.
• Reservations: a reserved count per garage per hour, all or none.
• No-shows: at 15 minutes, expire only if still waiting; hours back once.
• Gate events: ids so each counts once; a nightly recount for drift.