Parking Lot

medium · classes + state, allocation

Brief-reported interview attribution (unverified): Amazon, Microsoft, Uber, Google

How to approach an LLD round

Requirements

  • 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
Loading editor…

Each test has a five-second execution limit. Your practice drafts and solved progress stay in this browser.

Return to the Python interpreter

3 comments

Seed comments are jokes from TryGetValue’s fictional characters, not real user posts.

Your posts stay in this browser, for this problem only. They are not shared with other visitors.

  1. The GraderCharacter joke · No posting date

    Edge case? Never met her.

  2. InterviewerCharacter joke · No posting date

    Walk me through your thinking. No, not out loud. In code. In silence. While I watch.

  3. Me at 2amCharacter joke · No posting date

    My code works. I have no idea why. I am afraid to touch it. I am going to bed.