Design a parking lot
Vehicles, spots and levels for a multi-level parking garage.
On this page
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#
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#
-
Turn the constraints into a table. This is the most useful thing you can write down:
Vehicle Fits in Spots needed Motorcycle any spot 1 Car compact or large 1 Bus large only 5 in a row -
List the nouns. ParkingLot, Level (a floor), ParkingSpot, Vehicle (Motorcycle, Car, Bus).
-
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.
-
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. -
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.
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:
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')andMotorcycle('M1')fail with'Car' object has no attribute 'spot_size'. The lineself.spot_sizereads an attribute instead of assigning one, so it is a typo forself.spot_size = spot_size.Car.can_fit_in_spotreadsspot.size, but aParkingSpothasspot_sizeandvehicle_size, notsize. It would raiseAttributeErrorthe first time it is called.Vehicle.clear_spotscallsspot.remove_vehicle(self), butParkingSpot.remove_vehicletakes no argument, so unparking raises aTypeError.- 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. ParkingLottakesnum_levelsbut starts with an empty list of levels, andLevelstarts withavailable_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.