Design a parking lot with several levels. Each level is a row of numbered spots, and every spot is "small", "medium" or "large". A vehicle of a given size fits in a spot of that size or any larger size (small < medium < large).
Implement ParkingLot(levels), where levels[i][j] is the size of spot j on level i (both numbered from 0). A spot is identified by the tuple (level, spot). The starter defines SIZES, smallest to largest.
park(vehicle_id, size, now=0) parks the vehicle and returns its spot. It may use any free spot whose size is size or larger. Among those, choose the lowest level, then the lowest spot number on that level. Return None if no free spot fits or if vehicle_id is already parked.leave(vehicle_id, now=0) frees the vehicle's spot so it can be used again and returns True. It returns False if the vehicle is not parked.available(size) returns how many spots of exactly size are free.Ignore now until Part 3.
(0, 0) (0, 1) (0, 2) (1, 0) None 0 0 0
lot = ParkingLot([["small", "medium", "large"], ["large"]])
print(lot.park("s1", "small"))
print(lot.park("m1", "medium"))
print(lot.park("l1", "large"))
print(lot.park("l2", "large"))
print(lot.park("l3", "large"))
print(lot.available("small"), lot.available("medium"), lot.available("large"))Design a multi-level parking lot class: park vehicles in spots that fit their size, then choose the smallest fitting spot quickly and look up where a vehicle is, then report the busiest period.
Also known as: Parking lot system, Object-oriented design: parking lot
Stateful class design shows up in 19.7% of the 1,447 coding interview reports we studied, at 16 companies. Implement a class with a handful of methods that share state, often in levels: get the basic operations working, then add a feature that forces you to restructure.
Reported at: OpenAI, Anthropic, Rippling, Databricks, Snowflake, Citadel, Zip, Robinhood, Roblox, Amazon, Perplexity, Waymo, xAI, Harvey AI, Palantir, Mercor.
This is an original practice problem written by AceOffer to train the pattern. It is not a question any company asked.
Follow-ups candidates reported on questions with this pattern, in our words. Parts marked “from reports” below are built on them.
Design a parking lot with several levels. Each level is a row of numbered spots, and every spot is "small", "medium" or "large". A vehicle of a given size fits in a spot of that size or any larger size (small < medium < large).
Implement ParkingLot(levels), where levels[i][j] is the size of spot j on level i (both numbered from 0). A spot is identified by the tuple (level, spot). The starter defines SIZES, smallest to largest.
park(vehicle_id, size, now=0) parks the vehicle and returns its spot. It may use any free spot whose size is size or larger. Among those, choose the lowest level, then the lowest spot number on that level. Return None if no free spot fits or if vehicle_id is already parked.leave(vehicle_id, now=0) frees the vehicle's spot so it can be used again and returns True. It returns False if the vehicle is not parked.available(size) returns how many spots of exactly size are free.Ignore now until Part 3.
Large spots are scarce, so a small car should not take one when a small spot is free anywhere in the lot. Change the rule park uses:
This replaces the Part 1 rule. (The Part 1 tests only use cases where both rules pick the same spot.)
Also add where(vehicle_id), which returns the (level, spot) of a parked vehicle, or None if it is not parked (never parked, or already left).
Parking happens far more often than lots change size, so choosing a spot should not mean scanning every spot.
The operator wants to know how full the lot gets. now is a time in whole minutes that never decreases, passed to every park and leave call.
Add peak(), which returns a tuple (n, start, end):
n is the largest number of vehicles that were parked at the same time so far (0 if nothing has parked yet),start is the now of the park call that first brought the count up to n,end is the now of the first leave after that moment, which is when the count first dropped below n again. It is None while the lot is still at n.If the count later climbs back to the same n, keep the earlier period. Failed park or leave calls change nothing. Before any vehicle parks, peak() returns (0, None, None).
Open this page on a laptop or desktop to write and run your code against the tests in the browser.
Spoilers: try each part before reading its walkthrough.
Start with the state, not the classes. You need to know which spots are free and where each vehicle is. A dict parked from vehicle id to its spot handles duplicates and lets leave find the spot instantly. For free spots, a first version can scan levels and spots in order and take the first free one whose size is at least the vehicle's size, comparing with SIZES.index. Scanning in level order, then spot order, gives the lowest-level, lowest-number rule directly. That is O(S) per park for S spots, which is fine to get working; Part 2 replaces it. Identifying a spot by the tuple (level, spot) keeps output simple and gives a natural ordering for later.
Group free spots by size and keep each group in a min-heap of (level, spot) tuples. Python compares tuples element by element, so the heap top is always the nearest free spot of that size. To park, walk SIZES from the vehicle's own size upward and pop from the first non-empty heap; that is the best-fit rule in at most three checks plus one O(log S) pop. To leave, push the spot back onto the heap for its size. available(size) is just the heap length, and where reads the parked dict. A sorted list with bisect would also work, but its inserts are O(S); heaps keep both operations logarithmic.
Occupancy only changes on a successful park or leave, so the peak can be tracked online with three values: the current count, the best record (n, start, end), and a flag saying whether the lot is still sitting at that record. On park, increment the count; if it is strictly greater than the record, start a new record at now with no end and raise the flag. On leave, if the flag is up, this leave is the moment the count drops below the record, so store now as the end and lower the flag, then decrement. Using strictly greater keeps the earliest period on ties. Each call does O(1) extra work and no event history is stored.
Keep a dict from vehicle id to its spot. That answers 'already parked?' and lets leave find the spot to free in O(1).
Keep one min-heap of free (level, spot) tuples per spot size. Tuples compare level first, then spot, so the top of each heap is the nearest free spot of that size.
Keep a running count of parked vehicles. Update the record only when the count goes strictly above the old peak, and close the period on the next successful leave.
Building the heaps is O(S) for S spots. park tries at most three sizes and pops one heap entry, O(log S). leave pushes the spot back, O(log S). available, where and peak are O(1). Memory is O(S + V) for V parked vehicles.
The company guides collect the questions candidates report, with every part, the follow-ups interviewers added, and how often each one comes up.
Browse the interview guides