Design a parking lot

Vehicles, spots and levels for a multi-level parking garage.

On this page
  1. Constraints and assumptions
  2. Solution
  3. The one idea
  4. How to get there in an interview
  5. A working version
  6. What is wrong with the sketch above
  7. Questions to expect next

Constraints and assumptions#

  • What types of vehicles should we support?
    • Motorcycle, Car, Bus
  • Does each vehicle type take up a different amount of parking spots?
    • Yes
    • Motorcycle spot -> Motorcycle
    • Compact spot -> Motorcycle, Car
    • Large spot -> Motorcycle, Car
    • Bus can park if we have 5 consecutive "large" spots
  • Does the parking lot have multiple levels?
    • Yes

Solution#

python
from abc import ABCMeta, abstractmethod


class VehicleSize(Enum):

    MOTORCYCLE = 0
    COMPACT = 1
    LARGE = 2


class Vehicle(metaclass=ABCMeta):

    def __init__(self, vehicle_size, license_plate, spot_size):
        self.vehicle_size = vehicle_size
        self.license_plate = license_plate
        self.spot_size = spot_size
        self.spots_taken = []

    def clear_spots(self):
        for spot in self.spots_taken:
            spot.remove_vehicle(self)
        self.spots_taken = []

    def take_spot(self, spot):
        self.spots_taken.append(spot)

    @abstractmethod
    def can_fit_in_spot(self, spot):
        pass


class Motorcycle(Vehicle):

    def __init__(self, license_plate):
        super(Motorcycle, self).__init__(VehicleSize.MOTORCYCLE, license_plate, spot_size=1)

    def can_fit_in_spot(self, spot):
        return True


class Car(Vehicle):

    def __init__(self, license_plate):
        super(Car, self).__init__(VehicleSize.COMPACT, license_plate, spot_size=1)

    def can_fit_in_spot(self, spot):
        return True if (spot.size == LARGE or spot.size == COMPACT) else False


class Bus(Vehicle):

    def __init__(self, license_plate):
        super(Bus, self).__init__(VehicleSize.LARGE, license_plate, spot_size=5)

    def can_fit_in_spot(self, spot):
        return True if spot.size == LARGE else False


class ParkingLot(object):

    def __init__(self, num_levels):
        self.num_levels = num_levels
        self.levels = []

    def park_vehicle(self, vehicle):
        for level in levels:
            if level.park_vehicle(vehicle):
                return True
        return False


class Level(object):

    SPOTS_PER_ROW = 10

    def __init__(self, floor, total_spots):
        self.floor = floor
        self.num_spots = total_spots
        self.available_spots = 0
        self.parking_spots = []

    def spot_freed(self):
        self.available_spots += 1

    def park_vehicle(self, vehicle):
        spot = self._find_available_spot(vehicle)
        if spot is None:
            return None
        else:
            spot.park_vehicle(vehicle)
            return spot

    def _find_available_spot(self, vehicle):
        """Find an available spot where vehicle can fit, or return None"""
        # ...

    def _park_starting_at_spot(self, spot, vehicle):
        """Occupy starting at spot.spot_number to vehicle.spot_size."""
        # ...


class ParkingSpot(object):

    def __init__(self, level, row, spot_number, spot_size, vehicle_size):
        self.level = level
        self.row = row
        self.spot_number = spot_number
        self.spot_size = spot_size
        self.vehicle_size = vehicle_size
        self.vehicle = None

    def is_available(self):
        return True if self.vehicle is None else False

    def can_fit_vehicle(self, vehicle):
        if self.vehicle is not None:
            return False
        return vehicle.can_fit_in_spot(self)

    def park_vehicle(self, vehicle):  # ...
    def remove_vehicle(self):  # ...

Added on this site

The one idea#

The classes are easy to list. The design question is which object knows what, and the one genuinely algorithmic part: a bus needs five consecutive large spots, so finding space is a search for a run, not a single free slot.

How to get there in an interview#

  1. Turn the constraints into a table. This is the most useful thing you can write down:

    VehicleFits inSpots needed
    Motorcycleany spot1
    Carcompact or large1
    Buslarge only5 in a row
  2. List the nouns. ParkingLot, Level (a floor), ParkingSpot, Vehicle (Motorcycle, Car, Bus).

  3. Put the rules on the object that owns the knowledge. A vehicle knows which spot sizes it can use and how many it needs. A level knows how to find room. The lot only decides which level to try. Nobody should be reaching across objects to ask for sizes and then deciding for them.

  4. Describe the main operations. park(vehicle) finds spots and marks them taken. unpark(vehicle) frees every spot that vehicle held. A vehicle that took several spots must remember all of them.

  5. Name the hard part before writing code. Walk a level's spots in order, keep a running run of free, suitable spots, reset the run when you hit one that does not fit, and stop when the run is long enough.

A working version#

This version assumes the spots on a level are in one row. To respect separate rows, add a row number to each spot and reset the run when it changes.

python
class Vehicle:
    FITS = ()          # spot sizes this vehicle can use
    SPOTS_NEEDED = 1

    def __init__(self, plate):
        self.plate = plate
        self.spots = []


class Motorcycle(Vehicle):
    FITS = ('motorcycle', 'compact', 'large')


class Car(Vehicle):
    FITS = ('compact', 'large')


class Bus(Vehicle):
    FITS = ('large',)
    SPOTS_NEEDED = 5


class Spot:
    def __init__(self, number, size):
        self.number = number
        self.size = size
        self.vehicle = None


class Level:
    def __init__(self, spots):
        self.spots = spots

    def park(self, vehicle):
        """Park in the first run of free, suitable, consecutive spots that is long enough."""
        run = []
        for spot in self.spots:
            if spot.vehicle is None and spot.size in vehicle.FITS:
                run.append(spot)
                if len(run) == vehicle.SPOTS_NEEDED:
                    for taken in run:
                        taken.vehicle = vehicle
                    vehicle.spots = run
                    return run
            else:
                run = []                      # the run is broken: start again
        return None

    def free_spots(self):
        return sum(1 for spot in self.spots if spot.vehicle is None)


class ParkingLot:
    def __init__(self, levels):
        self.levels = levels

    def park(self, vehicle):
        for level in self.levels:
            spots = level.park(vehicle)
            if spots:
                return spots
        return None

    def unpark(self, vehicle):
        for spot in vehicle.spots:
            spot.vehicle = None
        vehicle.spots = []

Try it:

python
level = Level([Spot(1, 'motorcycle'), Spot(2, 'compact'), Spot(3, 'compact')] + [Spot(n, 'large') for n in range(4, 10)])
lot = ParkingLot([level])

bus, bus2, car = Bus('B1'), Bus('B2'), Car('C1')
assert [s.number for s in lot.park(bus)] == [4, 5, 6, 7, 8]    # five large spots in a row
assert lot.park(bus2) is None                                   # only one large spot is left
assert [s.number for s in lot.park(car)] == [2]                 # a car takes a compact spot
assert level.free_spots() == 3                                  # nine spots, six now taken

lot.unpark(bus)
assert lot.park(bus2) is not None                               # the freed run can be reused
assert Motorcycle('M1').FITS == ('motorcycle', 'compact', 'large')

What is wrong with the sketch above#

The solution on this page is an outline, and the vehicle classes cannot even be created. Each of these was checked by running the code:

  • Car('ABC') and Motorcycle('M1') fail with 'Car' object has no attribute 'spot_size'. The line self.spot_size reads an attribute instead of assigning one, so it is a typo for self.spot_size = spot_size.
  • Car.can_fit_in_spot reads spot.size, but a ParkingSpot has spot_size and vehicle_size, not size. It would raise AttributeError the first time it is called.
  • Vehicle.clear_spots calls spot.remove_vehicle(self), but ParkingSpot.remove_vehicle takes no argument, so unparking raises a TypeError.
  • The methods that do the real work (_find_available_spot, _park_starting_at_spot, ParkingSpot.park_vehicle) are empty. In particular the consecutive-spots search for the bus is missing, and that is the hard part.
  • ParkingLot takes num_levels but starts with an empty list of levels, and Level starts with available_spots = 0, so the counts disagree with the spots.

Questions to expect next#

  • Fees. Record the entry time on the ticket and compute the fee on exit. Keep pricing in its own class, so changing the rates does not touch parking logic.
  • Finding the nearest spot. Keep a free list per spot size, or per level, instead of scanning. Then parking is O(1) for single spots.
  • Concurrency. Two cars must not take the same spot. Assign under a lock per level, or make the "set vehicle if empty" step atomic in the database.
  • Electric vehicle spots, handicapped spots. Add an attribute to the spot and a requirement on the vehicle, instead of new classes for each case.
  • Many lots across a city. Now it is a real system: a database of spot availability, a service to query it, and caching for the busy ones. The capacity estimator is a good place to start sizing it.
Esc
↑ ↓ to move↵ to open