Design a Parking Lot

Description

"Design a parking lot" is the most common object-oriented design prompt, and a good warm-up for the whole family: a few entities, a couple of rules, two lookups that must stay in sync, and follow-ups (vehicle sizes, pricing, several gates) that test whether the design can absorb change. This skill walks through the clarifying questions, the model, the core data structures and the allocation policy.

"Design a parking lot" is the most common object-oriented design prompt, and the first attempt usually puts everything into one class that scans:

class ParkingLot {
    boolean[] occupied = new boolean[500];
    String[] plateAt = new String[500];

    int park(String plate) {
        for (int i = 0; i < occupied.length; i++)
            if (!occupied[i]) { occupied[i] = true; plateAt[i] = plate; return i; }
        return -1;
    }

    void leave(String plate) {
        for (int i = 0; i < plateAt.length; i++)
            if (plate.equals(plateAt[i])) { occupied[i] = false; plateAt[i] = null; }
    }
}

class ParkingLot:
    def __init__(self):
        self.occupied = [False] * 500
        self.plate_at: list[str | None] = [None] * 500

    def park(self, plate: str) -> int:
        for i in range(len(self.occupied)):
            if not self.occupied[i]:
                self.occupied[i] = True
                self.plate_at[i] = plate
                return i
        return -1

    def leave(self, plate: str) -> None:
        for i in range(len(self.plate_at)):
            if self.plate_at[i] == plate:
                self.occupied[i] = False
                self.plate_at[i] = None

It passes a demo, and every follow-up breaks it. Vehicle sizes (a bus can't use a motorcycle bay), a second entrance, a price per hour, a board showing free spots per size - each one lands as another array and another if inside the same two loops. leave by plate frees every spot holding that plate, nothing stops the same car being parked twice, and nobody outside the class can tell which parking session a spot belongs to.

We'll go from simple to more technical:

1. The four steps - clarify, model, API, core - applied to a garage.
2. The core: free spots per size and a ticket-to-spot map.
3. Allocation as a swappable policy, and smallest fit first.
4. What a real garage adds, and the bugs that come from two structures disagreeing.

The approach

An object-oriented design round rewards the same four steps every time - clarify, model, define the API, build the core - with extension points where the interviewer is likely to push next.

1. Clarify. Which vehicle types and spot sizes? May a small vehicle use a bigger spot? One level or many, one gate or several? What happens when nothing fits - return a value or throw? Is pricing in scope? Is it concurrent?
2. Model. Entities with identity and a lifecycle (ParkingSpot, a ticket), value objects (Vehicle: a type and a plate), enums for closed sets (Vehicle.Type, ParkingSpot.Size), and one facade that owns the rules (ParkingLot).
3. API. Three operations: String parkVehicle(Vehicle) returns a ticket, or null when nothing fits; boolean unparkVehicle(String ticketId); int availableSpots(ParkingSpot.Size).
4. Core. Two lookups that run in opposite directions, each with its own structure: a free spot of this size for park, and ticket → spot for unpark.

ParkingLot ──owns──> ParkingSpot (size, occupied)      Vehicle (type, plate)
    │                       ^
    │ asks                  │ ticket id -> spot
    v                       │
FitPolicy            Map<String, ParkingSpot>

The pieces in code

public class ParkingLot {
    private final Map<ParkingSpot.Size, Deque<ParkingSpot>> free = new EnumMap<>(ParkingSpot.Size.class);
    private final Map<String, ParkingSpot> spotByTicket = new HashMap<>();

    public ParkingLot(List<ParkingSpot> spots) {
        for (ParkingSpot.Size s : ParkingSpot.Size.values()) free.put(s, new ArrayDeque<>());
        for (ParkingSpot spot : spots) free.get(spot.getSize()).addLast(spot);
    }

    public String parkVehicle(Vehicle vehicle) {
        ParkingSpot spot = free.get(sizeFor(vehicle.getType())).pollFirst();   // O(1); null when that size is full
        if (spot == null) return null;
        spot.setOccupied(true);
        String ticket = UUID.randomUUID().toString();
        spotByTicket.put(ticket, spot);
        return ticket;
    }

    public boolean unparkVehicle(String ticketId) {
        ParkingSpot spot = spotByTicket.remove(ticketId);   // remove, not get: a ticket works once
        if (spot == null) return false;
        spot.setOccupied(false);
        free.get(spot.getSize()).addLast(spot);
        return true;
    }

    public int availableSpots(ParkingSpot.Size size) {
        return free.get(size).size();                       // the free list is the count
    }
}

import uuid
from collections import deque


class ParkingLot:
    def __init__(self, spots: list[ParkingSpot]):
        self._free: dict[ParkingSpot.Size, deque[ParkingSpot]] = {s: deque() for s in ParkingSpot.Size}
        self._spot_by_ticket: dict[str, ParkingSpot] = {}
        for spot in spots:
            self._free[spot.size].append(spot)

    def park_vehicle(self, vehicle: Vehicle) -> str | None:
        free = self._free[size_for(vehicle.type)]
        if not free:
            return None                                     # that size is full
        spot = free.popleft()                               # O(1)
        spot.occupied = True
        ticket = str(uuid.uuid4())
        self._spot_by_ticket[ticket] = spot
        return ticket

    def unpark_vehicle(self, ticket_id: str) -> bool:
        spot = self._spot_by_ticket.pop(ticket_id, None)    # pop, not get: a ticket works once
        if spot is None:
            return False
        spot.occupied = False
        self._free[spot.size].append(spot)
        return True

    def available_spots(self, size: ParkingSpot.Size) -> int:
        return len(self._free[size])                        # the free list is the count

(sizeFor is a switch mapping MOTORCYCLE, CAR and BUS to SMALL, MEDIUM and LARGE.) Three details carry most of the grading:

• remove, not get, in unparkVehicle (in Python, pop, not get) makes a ticket single-use. With get, a second call returns true and appends the spot to the free list again - now it's listed twice, and two later cars are handed the same spot.
• availableSpots reads the free list's size instead of a separate counter, so the number can't drift from the truth.
• pollFirst() returns null on an empty deque (removeFirst() would throw), which is exactly "nothing of that size is free". (Python's deque.popleft() raises IndexError on an empty deque instead - hence the if not free check first.)

A ticket, not a plate, is the key: it names one parking session. The lot mints it, can refuse it once used, and can later carry the entry time a price needs. A plate names a car, and the same car comes back tomorrow.

Allocation is a policy

"Which spot?" changes more often than anything else in this design: exact size only, a motorcycle allowed in a car bay, the bay nearest the gate you came in through. Keep that decision behind one small interface and let ParkingLot keep its structures private:

public interface FitPolicy {
    List<ParkingSpot.Size> sizesToTry(Vehicle.Type type);   // in preference order

    FitPolicy EXACT = type -> List.of(switch (type) {
        case MOTORCYCLE -> SMALL;
        case CAR -> MEDIUM;
        case BUS -> LARGE;
    });

    FitPolicy SMALLEST_FIRST = type -> switch (type) {
        case MOTORCYCLE -> List.of(SMALL, MEDIUM, LARGE);
        case CAR -> List.of(MEDIUM, LARGE);
        case BUS -> List.of(LARGE);
    };
}

from collections.abc import Callable

# A fit policy: the spot sizes to try for a vehicle type, in preference order.
type FitPolicy = Callable[[Vehicle.Type], list[ParkingSpot.Size]]


def exact(t: Vehicle.Type) -> list[ParkingSpot.Size]:
    return [{MOTORCYCLE: SMALL, CAR: MEDIUM, BUS: LARGE}[t]]


def smallest_first(t: Vehicle.Type) -> list[ParkingSpot.Size]:
    return {MOTORCYCLE: [SMALL, MEDIUM, LARGE], CAR: [MEDIUM, LARGE], BUS: [LARGE]}[t]

parkVehicle then walks fitPolicy.sizesToTry(vehicle.getType()) and takes the first spot it can poll. (In Python a one-method policy is simply a function, as above.) Smallest fit first matters as soon as vehicles may use bigger bays: giving a motorcycle the lowest-numbered free spot - which might be a bus bay - can turn the next bus away while small bays stand empty.

Not every policy fits this shape. "Nearest to your gate" orders spots within a size, so it changes the structure too: each gate needs free spots ordered by its own distance, such as a PriorityQueue per gate. That is one reason the free lists stay private - the policy says what to prefer, and the lot decides how to store spots so that preference is cheap.

What a real garage adds

A real garage adds what the interview version leaves out: tickets are stored durably (a restart must not forget who is parked), the entry time on the ticket feeds a pricing component at the exit, per-bay sensors report occupancy that can disagree with the software (a car parks across two bays; a sensor fails), and display boards subscribe to free-count changes rather than polling. Each of those is a new class that talks to the lot through a narrow interface - the lot itself stays about space.

Which tool for which job?

Common mistakes

Check yourself

Try to answer before opening each one - recalling beats re-reading.

1. What test would catch an unparkVehicle that reads the ticket map with get instead of remove?

2. Motorcycles may now use any free spot. Why try SMALL before LARGE instead of taking the lowest-numbered free spot of any size?

3. Two exits scan the same ticket at the same instant, and tickets live in a ConcurrentHashMap. What makes the spot come free only once?

Key takeaways

• Clarify, model, define the API, then build the core - the clarifying answers decide the entities and structures.
• A parking lot needs two lookups in opposite directions: a free spot by size for park, and ticket → spot for unpark. Keep them private and update them together.
• A ticket names a parking session: mint it, and remove it on use so it works exactly once.
• Allocation rules change most often: put them behind one small interface, and prefer the smallest size that fits.
• Under concurrency, finding and taking a spot must be one atomic step - a lock, or structures whose poll/remove hand an item to exactly one caller.