4
\$\begingroup\$

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

\$\endgroup\$
  • 1
    \$\begingroup\$ Other than the constraints and assumptions that you listed, was the only instruction "Design a parking lot"? That seems rather vague; I would expect to be told something about the kind of operations that need to be done. \$\endgroup\$ – Blackwood Dec 25 '18 at 2:39
  • \$\begingroup\$ @blackwood yes you're right. I pretty much had to think of the operations that would be expected of a parking lot. I'll edit those into the descriptions as well. \$\endgroup\$ – thebenman Dec 25 '18 at 2:41

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.