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 ParkingSystemParkingSystem(big, medium, small)addCar(carType)addCar
Example
returns true, true, false, false
There are no small spaces, and the single big space is taken by the first car.
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
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.
The counts start at 1, 1 and 0. addCar(1)addCar(2)addCar(3)addCar(1)
Solution Approach
Turning that idea into code means settling three things: what to store, how a car type finds its count, and what addCar
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 addCarswitchfree[carType]
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]free[2]free[3]
Parking a car
What should addCar
If cars could also leave, an optional removeCar(carType)
Java Solution
The class has three parts:
: the counts of free spaces, indexed by car type.free is unused.free[0]- The constructor: fills
with the starting counts.free : checks the count for the car's type, and takes a space if one is free.addCar
The main
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:
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]{big, medium, small}free[carType]addCar(3)ArrayIndexOutOfBoundsException: Index 3 out of bounds for length 3
The original implementation,
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
does one array read, one comparison and at most one decrease.addCar - 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