Design Parking System

Let cars into a parking lot with three sizes of space, keeping one count of free spaces per size.

A parking lot has a fixed number of big, medium and small spaces. Write a class ParkingSystem with two parts. The constructor ParkingSystem(big, medium, small) sets how many spaces of each size there are. The method addCar(carType) tries to park one car, where carType 1, 2 and 3 mean big, medium and small. A car may only park in a space of its own size. addCar returns true if the car parks, and false if no space of its size is free.

Example
ParkingSystem(1, 1, 0), then addCar(1), addCar(2), addCar(3), addCar(1)
returns true, true, false, false
There are no small spaces, and the single big space is taken by the first car.
Solution

The Idea

Picture the gate at the entrance of a parking lot. Cars arrive one at a time, and the gate either lets a car in or turns it away. The lot has spaces of three sizes, and a car can only use a space of its own size, so a small car cannot take a free big space. Our class plays the gate: addCar is one car arriving.

Look at the example. The lot has 1 big space, 1 medium space and no small spaces. The first car is big, and it takes the big space. The second is medium, and it takes the medium space. The third is small, but the lot has no small spaces at all. The fourth is big again, and the one big space is already taken.

What does the gate need to remember to give these answers? It might seem to need a record of every space in the lot, each marked free or taken. But look at what each answer depended on: only how many spaces of the car's size were still free. Cars never leave, and no call ever asks which space a car took.

So three numbers are enough: one count of free spaces for each size. Look at the picture below. Each row is one call, and the orange box is the count that call checks.

Three counts of free spaces, big, medium and small, start at 1, 1 and 0. addCar(1) takes the big space, addCar(2) takes the medium space, addCar(3) finds 0 small spaces, and the second addCar(1) finds 0 big spaces.

The counts start at 1, 1 and 0. addCar(1) finds 1 free big space, takes it, and the big count drops to 0. addCar(2) does the same with the medium count. addCar(3) finds the small count at 0 and returns false. The last addCar(1) returns false too, because the big count is now 0 as well.

Solution Approach

Turning that idea into code means settling three things: what to store, how a car type finds its count, and what addCar does with that count.

What to store

Why not keep a list of every space, each marked free or taken? It works, but to park a car the gate would have to search the list for a free space of the right size. In a lot of 100,000 spaces, one call could look at all 100,000 entries. A count answers the same question in one step, however large the lot is.

Finding the count for a car type

How does addCar get from carType to the right count? One way is three separate fields and a switch on the type. A shorter way is an array of counts, where the car type is the index, so free[carType] is the count directly.

Java arrays start at index 0, but car types start at 1. Making the array four long and leaving index 0 unused lines them up: free[1] is the big count, free[2] the medium count and free[3] the small count.

Parking a car

What should addCar do with the count? If it is 0, no space of that size is free, so it returns false and leaves the count alone. Otherwise it takes one space by decreasing the count, and returns true. Checking before decreasing means a count never drops below 0.

If cars could also leave, an optional removeCar(carType) method would simply increase the count again. The problem has no such method, so here the counts only go down.

Java Solution

The class has three parts:

  • free: the counts of free spaces, indexed by car type. free[0] is unused.
  • The constructor: fills free with the starting counts.
  • addCar: checks the count for the car's type, and takes a space if one is free.

The main method runs the example, sends a big car and then three small cars to a lot with only two small spaces, and fills a lot of 100,000 big spaces until it refuses a car.

Java
public class ParkingSystem {

    private final int[] free;   // free[1] big, free[2] medium, free[3] small; free[0] unused

    public ParkingSystem(int big, int medium, int small) {
        free = new int[] {0, big, medium, small};
    }

    public boolean addCar(int carType) {
        if (free[carType] == 0) {   // no free space of this size
            return false;
        }
        free[carType]--;            // take one
        return true;
    }

    public static void main(String[] args) {
        ParkingSystem lot = new ParkingSystem(1, 1, 0);
        System.out.println("Example: " + lot.addCar(1) + ", " + lot.addCar(2) + ", "
            + lot.addCar(3) + ", " + lot.addCar(1));

        ParkingSystem small = new ParkingSystem(0, 0, 2);
        System.out.println("A big car, small spaces free: " + small.addCar(1));
        System.out.println("Three small cars: " + small.addCar(3) + ", "
            + small.addCar(3) + ", " + small.addCar(3));

        ParkingSystem large = new ParkingSystem(100000, 0, 0);
        int parked = 0;
        while (large.addCar(1)) {
            parked++;
        }
        System.out.println("100000 big spaces: " + parked + " big cars parked, then "
            + large.addCar(1));
    }
}

Running it prints:

Output
Example: true, true, false, false
A big car, small spaces free: false
Three small cars: true, true, false
100000 big spaces: 100000 big cars parked, then false

The first line matches the example. The second line shows that sizes never mix: the big car is turned away even though two small spaces are free. On the third line, two small cars take the two small spaces and the third is refused. The last line shows the count working the same in a large lot: exactly 100,000 big cars park, and the next one is refused.

The unused free[0] is there for a reason. With a three-slot array {big, medium, small} read as free[carType], big cars would read the medium count, and addCar(3) would throw ArrayIndexOutOfBoundsException: Index 3 out of bounds for length 3.

The original implementation, ParkingSystem.java, is on GitHub.

Complexity

Each call does a fixed amount of work and the object keeps a fixed number of values, however many spaces the lot has.

  • Time: O(1) per call. The constructor builds a four-element array, and addCar does one array read, one comparison and at most one decrease.
  • Space: O(1). The object holds one array of four ints, whether the lot has two spaces or 100,000.

For a design problem that needs lookups by key rather than by a small number, see Design Underground System.