Parking Lot
medium · classes + state, allocation
Brief-reported interview attribution (unverified): Amazon, Microsoft, Uber, Google
How to approach an LLD roundRequirements
- Functional: park a bike/car/truck in the first free spot that fits, across floors; issue a ticket; unpark by ticket and charge an hourly fee by vehicle type; count free spots per floor and vehicle type.
- Non-functional: allocation scans floors in order and stops at the first fitting free spot; in the worst case it scans all spots; fee rules are replaceable through the pricing strategy; a new vehicle subclass must also be registered in the vehicle-type registry; the lot is shared state, so concurrent park/unpark must never double-book a spot.
- Out of scope (45–60 min): payments, reservations, valet, multi-lot routing, persistence.
Statement
Design a parking lot with several floors. Each floor has spots of three
sizes: compact, regular, large. Vehicles are bike, car, truck. A bike
fits any spot, a car fits regular or large, a truck fits large only. Parking
takes the first fitting free spot in floor order, then spot order. A ticket records
vehicle type, floor, spot, and entry time. Fees are per hour: bike $1, car $2,
truck $4. Timestamps are integers (hours) passed by the caller.
class ParkingLot:
def __init__(self, floors):
# floors: list of dicts, e.g. [{"compact": 2, "regular": 2, "large": 1}]
def park(self, vehicle_type, timestamp):
# -> ticket id (int, starting at 1), or None if no fitting spot / bad type
def unpark(self, ticket_id, timestamp):
# -> fee (int) = (timestamp - entry) * rate, or None if the ticket is unknown/used
def free_spots(self, floor, vehicle_type):
# -> number of free spots on that floor that fit the vehicle (0 for a bad floor/type)Rules. A vehicle that does not fit anywhere returns None from park. unpark
with an unknown or already-used ticket returns None and changes nothing. A car
must not take a compact spot while a regular one is free.
Money units: fees are whole dollars, not cents; a three-hour car stay returns 6.
Tests use explicit inputs and injected clocks/callbacks. No network, real threads or application-server execution is involved.
Class design (SOLID)
Vehicle (type + allowed spot sizes) with Bike/Car/Truck subclasses — LSP (any vehicle can be parked where a Vehicle is expected) and OCP (a new vehicle type is a new subclass plus an entry in the vehicle registry). Spot (size + occupancy), Floor (owns spots, finds the first free fitting one), Ticket (vehicle, floor, spot, entry time) — each SRP. PricingStrategy (ABC interface) + HourlyPricingStrategy (hours x per-vehicle rate; OCP — a flat or surge strategy swaps in). ParkingLot orchestrates and takes the pricing strategy as a constructor argument (DIP). Pattern: Strategy (pricing).
Public demo
# Public demo: run after implementing the class API above.
p = ParkingLot([{'compact': 1, 'regular': 1, 'large': 1}, {'compact': 0, 'regular': 1, 'large': 0}])
print(p.park('bike', 0))Reference solution and hidden tests
Locked. Open the interactive editor and attempt the problem; the reference, hidden test descriptions, pattern explanation and complexity are available only after an explicit reveal.
Concurrency
Two drivers parking at once must not receive the same spot. The find-a-free-spot + mark-it-taken step must be atomic: guard park/unpark with one lock per lot (or per floor for more parallelism). The runnable reference is single-threaded — the site's Python runtime cannot run threads — so the lock is described here, not in the code.
Trade-offs & extensions
First-fit allocation is simple and fast but can fragment the lot. Extending: maintain a min-heap of free spot indices per (floor, size) for O(log free spots) pop/push operations, plus the work to choose a fitting floor and size, add a Reservation class and an AllocationStrategy (first-fit vs best-fit) the same way PricingStrategy works, and store tickets in a database instead of memory.
Starter code
from abc import ABC, abstractmethod
class Vehicle:
def __init__(self, vehicle_type):
"""floors: list of dicts, e.g. [{"compact": 2, "regular": 2, "large": 1}]"""
pass
def allowed_sizes(self):
"""Implement the return value and rules in the API contract."""
pass
class Bike(Vehicle):
pass
class Car(Vehicle):
pass
class Truck(Vehicle):
pass
class Spot:
def __init__(self, size):
"""floors: list of dicts, e.g. [{"compact": 2, "regular": 2, "large": 1}]"""
pass
def is_free(self):
"""Implement the return value and rules in the API contract."""
pass
def fits(self, vehicle):
"""Implement the return value and rules in the API contract."""
pass
class Floor:
def __init__(self, spec):
"""floors: list of dicts, e.g. [{"compact": 2, "regular": 2, "large": 1}]"""
pass
def first_free_spot(self, vehicle):
"""Implement the return value and rules in the API contract."""
pass
def free_count(self, vehicle):
"""Implement the return value and rules in the API contract."""
pass
class Ticket:
def __init__(self, ticket_id, vehicle, floor, spot_index, entry):
"""floors: list of dicts, e.g. [{"compact": 2, "regular": 2, "large": 1}]"""
pass
class PricingStrategy(ABC):
@abstractmethod
def fee(self, vehicle_type, hours):
"""Implement the return value and rules in the API contract."""
pass
class HourlyPricingStrategy(PricingStrategy):
def fee(self, vehicle_type, hours):
"""Implement the return value and rules in the API contract."""
pass
class ParkingLot:
def __init__(self, floors, pricing=None):
"""floors: list of dicts, e.g. [{"compact": 2, "regular": 2, "large": 1}]"""
pass
def park(self, vehicle_type, timestamp):
"""-> ticket id (int, starting at 1), or None if no fitting spot / bad type"""
pass
def unpark(self, ticket_id, timestamp):
"""-> fee (int) = (timestamp - entry) * rate, or None if the ticket is unknown/used"""
pass
def free_spots(self, floor, vehicle_type):
"""-> number of free spots on that floor that fit the vehicle (0 for a bad floor/type)"""
pass
Each test has a five-second execution limit. Your practice drafts and solved progress stay in this browser.
Return to the Python interpreter