Design Parking System — Solution in Python, Java & C++
Design Parking System solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. An easy problem.
Design Parking System is an easy coding problem on simulation and counting, asked in Amazon and Microsoft interviews.
- Difficulty: Easy
- Topics: Simulation, Counting
- Asked at: Amazon, Microsoft
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
A parking lot has three sizes of space — big, medium and small — with a fixed number of each. A car may only park in a space of its own size, and cars never leave. Write the class ParkingSystem:
ParkingSystem(int big, int medium, int small)creates a lot with that many spaces of each size.boolean addCar(int carType)tries to park a car of typecarType(1= big,2= medium,3= small). If a space of that size is free the car takes it and the call returnstrue; otherwise it returnsfalse.
The judge calls the methods in the order listed in the first input line, with the arguments in the second; the expected output holds each call's result, null for the constructor and for every void method.
Example 1
Input: ["ParkingSystem","addCar","addCar","addCar","addCar"]
[[1,1,0],[1],[2],[3],[1]]
Output: [null,true,true,false,false]
Explanation: One big and one medium space: the first big car and the medium car park. There are no small spaces, and the second big car finds the only big space taken.
Example 2
Input: ["ParkingSystem","addCar","addCar","addCar","addCar","addCar"]
[[0,2,1],[2],[1],[2],[2],[3]]
Output: [null,true,false,true,false,true]
Explanation: Two medium spaces fill up after two medium cars, so the third is turned away. There are no big spaces at all; the small car takes the one small space.
Constraints
0 <= big, medium, small <= 1000carType is 1, 2 or 3At most 1000 calls are made to addCar
Hints for Design Parking System
Hint 1
A car never moves into a space of another size, so the three sizes are three independent counters.
Hint 2
Store the free spaces per type in an array indexed by
carType.Hint 3
addCarchecks the counter for its type: zero meansfalse; otherwise decrement it and returntrue.
How to solve Design Parking System
Keep one counter of free spaces per car type. Parking a car is a check and a decrement of its own counter.
Approach
- Store
free = [_, big, medium, small]sofree[carType]is the number of free spaces for that type. addCar(carType): iffree[carType] == 0returnfalse; otherwise decrement it and returntrue.
Why it works
Spaces of different sizes never interact and cars never leave, so the only state that matters is how many spaces of each size are still free.
Complexity
- Time —
O(1) per call - Space —
O(1)
Pitfalls
carTypeis 1-based; index an array of size 4 or subtract one.- A lot may have zero spaces of a size from the start.
Reference solution
Python
class ParkingSystem:
def __init__(self, big: int, medium: int, small: int):
self.free = [0, big, medium, small]
def addCar(self, carType: int) -> bool:
if self.free[carType] == 0:
return False
self.free[carType] -= 1
return TrueJava
class ParkingSystem {
private int[] free;
public ParkingSystem(int big, int medium, int small) {
free = new int[]{0, big, medium, small};
}
public boolean addCar(int carType) {
if (free[carType] == 0) return false;
free[carType]--;
return true;
}
}C++
class ParkingSystem {
int freeSpaces[4];
public:
ParkingSystem(int big, int medium, int small) {
freeSpaces[0] = 0;
freeSpaces[1] = big;
freeSpaces[2] = medium;
freeSpaces[3] = small;
}
bool addCar(int carType) {
if (freeSpaces[carType] == 0) return false;
freeSpaces[carType]--;
return true;
}
};JavaScript
var ParkingSystem = function(big, medium, small) {
this.free = [0, big, medium, small];
};
ParkingSystem.prototype.addCar = function(carType) {
if (this.free[carType] === 0) return false;
this.free[carType]--;
return true;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.