I solved this system design interview question.
The problem description
Design a parking lot
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
Operations I assumed and implemented for the ParkingLot.
ParkVehicle
is when a person wants to park their vehicle in the spots they wish too. The spot chosen is assumed to be free always.UnParkVechicle
is when a person want's to unpark their vehicle without having to explicitly mention the spot in which they parked.GetOptimalParkingSpot
is when a person wishes to know which is the parking spot that is nearest to them for their vehicle. This implementation compares the spots by the floor, row and position they are on.GetParkingSpotStatus
returns whether the requested parking spot range is occupied or vacant.IParkingSpaceMapper.GetSmallestParkingSpaceRequired
returns the least required parking spots for a particular vehicle.
Implementation Details.
- To make the solution more adaptable to future business rules I decided to represent the parking space required for each vehicle type as a continuous set of parking spots.
- To keep track of the continuous set of parking spots and their types I used a sorted set to find a particular range of parking spots and also to merge with continuous ranges to it's left and right during freeing a particular range of parking spots.
The main interfaces
public interface IParkingLot
{
int FreeSpots { get; }
bool ParkVehicle(Vehicle vehicle, ParkingSpot parkingSpot);
bool UnParkvehicle(Vehicle vehicle);
ParkingSpot GetOptimalParkingSpot(Vehicle vehicle);
ParkingSpotStatus GetParkingSpotStatus(ParkingSpot spot);
}
public interface IParkingSpaceMapper
{
ParkingSpaceRequirment GetSmallestParkingSpaceRequired(Vehicle vehicle);
}
Concrete Implementation of Interfaces (Business Logic)
public class ParkingLotCore : IParkingLot
{
private ImmutableSortedSet<ParkingSpot> freeParkingSpots;
private ConcurrentDictionary<string, ParkingSpot> parkedVehicles;
private readonly IEnumerable<List<List<ParkingSpot>>> parkingLotLayout;
private readonly IParkingSpaceMapper parkingSpaceMapper;
private int _freeSpots = 0;
public int FreeSpots => _freeSpots;
private int _totalSpots = 0;
public int TotalSpots => _totalSpots;
public ParkingLotCore(IEnumerable<List<List<ParkingSpot>>> parkingLotLayout, IParkingSpaceMapper parkingSpaceMapper)
{
var comparer = Comparer<ParkingSpot>.Create((x, y) =>
x.Floor == y.Floor ?
x.Row == y.Row ?
x.StartPosition.CompareTo(y.StartPosition)
: x.Row.CompareTo(y.Row)
: x.Floor.CompareTo(y.Floor)
);
freeParkingSpots = ImmutableSortedSet.Create<ParkingSpot>(comparer);
parkedVehicles = new ConcurrentDictionary<string, ParkingSpot>();
this.parkingLotLayout = parkingLotLayout;
this.parkingSpaceMapper = parkingSpaceMapper;
InitializeParkingLot();
}
private void InitializeParkingLot()
{
foreach (var floor in parkingLotLayout)
{
foreach (var row in floor)
{
foreach (var spot in row)
{
freeParkingSpots = freeParkingSpots.Add(spot);
Interlocked.Add(ref _totalSpots, spot.SpotCount);
Interlocked.Add(ref _freeSpots, spot.SpotCount);
}
}
}
}
public ParkingSpot GetOptimalParkingSpot(Vehicle vehicle)
{
ParkingSpaceRequirment requiredSpace = parkingSpaceMapper.GetSmallestParkingSpaceRequired(vehicle);
var vacantSpot = freeParkingSpots.FirstOrDefault(m => m.ParkingSpotTypes >= requiredSpace.ParkingSpot
&& m.SpotCount >= requiredSpace.ParkingSpotsCount
);
if (vacantSpot != null)
{
vacantSpot.SpotCount = Math.Min(vacantSpot.SpotCount, requiredSpace.ParkingSpotsCount);
}
return vacantSpot;
}
public bool ParkVehicle(Vehicle vehicle, ParkingSpot parkingSpot)
{
if (parkedVehicles.ContainsKey(vehicle.VehicleNumber))
{
throw new InvalidOperationException($"Vehicle with number {vehicle.VehicleNumber} is already parked");
}
ParkingSpot vacantSpot = freeParkingSpots.FirstOrDefault(spot => spot.Floor == parkingSpot.Floor
&& spot.Row == parkingSpot.Row
&& spot.ParkingSpotTypes == parkingSpot.ParkingSpotTypes
&& spot.StartPosition <= parkingSpot.StartPosition
&& spot.SpotCount >= parkingSpot.SpotCount
);
if (vacantSpot == null)
throw new KeyNotFoundException("The spot could not be found");
freeParkingSpots = freeParkingSpots.Remove(vacantSpot);
parkedVehicles.TryAdd(vehicle.VehicleNumber, parkingSpot);
if (parkingSpot.StartPosition > vacantSpot.StartPosition)
{
var newSpot = new ParkingSpot() { Floor = vacantSpot.Floor, ParkingSpotTypes = vacantSpot.ParkingSpotTypes, Row = vacantSpot.Row, StartPosition = vacantSpot.StartPosition};
newSpot.SpotCount = parkingSpot.StartPosition - vacantSpot.StartPosition;
freeParkingSpots = freeParkingSpots.Add(newSpot);
}
if (vacantSpot.SpotCount > parkingSpot.SpotCount)
{
var newSpot = new ParkingSpot() { Floor = vacantSpot.Floor, ParkingSpotTypes = vacantSpot.ParkingSpotTypes, Row = vacantSpot.Row};
newSpot.StartPosition = parkingSpot.StartPosition + parkingSpot.SpotCount;
newSpot.SpotCount = vacantSpot.SpotCount - newSpot.StartPosition + 1;
freeParkingSpots = freeParkingSpots.Add(newSpot);
}
Interlocked.Add(ref _freeSpots, parkingSpot.SpotCount * -1);
return true;
}
public bool UnParkvehicle(Vehicle vehicle)
{
parkedVehicles.TryRemove(vehicle.VehicleNumber, out ParkingSpot currentSpot);
if (currentSpot == null)
throw new ArgumentException($"vehicle {vehicle.VehicleNumber} is not parked");
var leftSpot = freeParkingSpots.FirstOrDefault(spot => spot.Floor == currentSpot.Floor
&& spot.Row == currentSpot.Row
&& spot.ParkingSpotTypes == currentSpot.ParkingSpotTypes
&& spot.StartPosition + spot.SpotCount == currentSpot.StartPosition
);
ParkingSpot newSpotToUpdate = new ParkingSpot() { Floor = currentSpot.Floor, ParkingSpotTypes = currentSpot.ParkingSpotTypes, Row = currentSpot.Row, StartPosition = currentSpot.StartPosition, SpotCount = currentSpot.SpotCount };
if (leftSpot != null)
{
newSpotToUpdate.StartPosition = leftSpot.StartPosition;
newSpotToUpdate.SpotCount = currentSpot.SpotCount + leftSpot.SpotCount;
freeParkingSpots = freeParkingSpots.Remove(leftSpot);
}
var rightSpot = freeParkingSpots.FirstOrDefault(spot => spot.Floor == currentSpot.Floor
&& spot.Row == currentSpot.Row
&& spot.ParkingSpotTypes == currentSpot.ParkingSpotTypes
&& spot.StartPosition == currentSpot.StartPosition + currentSpot.SpotCount
);
if (rightSpot != null)
{
newSpotToUpdate.SpotCount = newSpotToUpdate.SpotCount + rightSpot.SpotCount;
freeParkingSpots = freeParkingSpots.Remove(rightSpot);
}
freeParkingSpots = freeParkingSpots.Add(newSpotToUpdate);
return true;
}
public ParkingSpotStatus GetParkingSpotStatus(ParkingSpot parkingSpot)
{
var rightSpot = freeParkingSpots.FirstOrDefault(spot => spot.Floor == parkingSpot.Floor
&& spot.Row == parkingSpot.Row
&& spot.ParkingSpotTypes == parkingSpot.ParkingSpotTypes
&& spot.StartPosition <= parkingSpot.StartPosition
&& spot.StartPosition + spot.SpotCount >= parkingSpot.SpotCount + parkingSpot.StartPosition
);
if (rightSpot != null)
{
return ParkingSpotStatus.Vacant;
}
return ParkingSpotStatus.Occupied;
}
}
public class ParkingSpaceMapper : IParkingSpaceMapper
{
public ParkingSpaceRequirment GetSmallestParkingSpaceRequired(Vehicle vehicle)
{
switch (vehicle.vehicleType)
{
case VehicleTypes.MotorCycle:
return new ParkingSpaceRequirment() { ParkingSpot = ParkingSpotTypes.Motorcycle, ParkingSpotsCount = 1 };
case VehicleTypes.Car:
return new ParkingSpaceRequirment() { ParkingSpot = ParkingSpotTypes.Compact, ParkingSpotsCount = 1 };
case VehicleTypes.Bus:
return new ParkingSpaceRequirment() { ParkingSpot = ParkingSpotTypes.Large, ParkingSpotsCount = 5 };
default:
throw new ArgumentException($"vehicleType {vehicle.vehicleType} is invalid.");
}
}
}
The enum's used
public enum ParkingSpotStatus
{
Occupied = 0,
Vacant = 1
}
public enum ParkingSpotTypes
{
Motorcycle = 0,
Compact = 1,
Large = 2
}
public enum VehicleTypes
{
MotorCycle = 0,
Car = 1,
Bus = 2
}
The data transfer objects used
public class ParkingLotStatus
{
public int TotalParkingSpots { get; set; }
public int OccupiedSpots { get; set; }
public int FreeSpots { get; set; }
}
public class ParkingSpaceRequirment
{
public ParkingSpotTypes ParkingSpot { get; set; }
public int ParkingSpotsCount { get; set; }
}
public class ParkingSpot
{
public int Floor { get; set; }
public int Row { get; set; }
public int StartPosition { get; set; }
public int SpotCount { get; set; }
public ParkingSpotTypes ParkingSpotTypes { get; set; }
}
public class Vehicle
{
public string VehicleNumber { get; set; }
public VehicleTypes vehicleType { get; set; }
}
The code along with the unit tests are available at GitHub to make it easier to read. https://github.com/benneyman/oop-parkingLot