Design Parking System
EasyPrompt
Design a parking system for a parking lot. The parking lot has three kinds of parking spaces: big, medium, and small, with a fixed number of slots for each size.
Implement the ParkingSystem class:
ParkingSystem(int big, int medium, int small)Initializes object of theParkingSystemclass. The number of slots for each parking space are given as part of the constructor.bool addCar(int carType)Checks whether there is a parking space ofcarTypefor the car that wants to get into the parking lot.carTypecan be of three kinds: big, medium, or small, which are represented by1,2, and3respectively. A car can only park in a parking space of itscarType. If there is no space available, returnfalse, else park the car in that size space and returntrue.
Example 1:
Input
["ParkingSystem", "addCar", "addCar", "addCar", "addCar"]
[[1, 1, 0], [1], [2], [3], [1]]
Output
[null, true, true, false, false]
Explanation
ParkingSystem parkingSystem = new ParkingSystem(1, 1, 0);
parkingSystem.addCar(1); // return true because there is 1 available slot for a big car
parkingSystem.addCar(2); // return true because there is 1 available slot for a medium car
parkingSystem.addCar(3); // return false because there is no available slot for a small car
parkingSystem.addCar(1); // return false because there is no available slot for a big car. It is already occupied.
Constraints:
0 <= big, medium, small <= 1000carTypeis1,2, or3- At most
1000calls will be made toaddCar
Approaches
2 approaches with complexity analysis and trade-offs.
This approach uses separate instance variables to store the available slots for each car type (big, medium, and small). The addCar method then uses a series of if-else statements to check the carType and update the corresponding slot count.
Algorithm
- Initialize three integer member variables in the constructor:
bigSlots,mediumSlots, andsmallSlots. - In the
addCarmethod, use a series ofif-else ifstatements to determine thecarType. - For
carType == 1, check ifbigSlotsis greater than 0. If it is, decrementbigSlotsand returntrue. - For
carType == 2, check ifmediumSlotsis greater than 0. If it is, decrementmediumSlotsand returntrue. - For
carType == 3, check ifsmallSlotsis greater than 0. If it is, decrementsmallSlotsand returntrue. - If the respective slot count is 0 for the given
carType, returnfalse.
Walkthrough
In this straightforward approach, we declare three integer member variables in the ParkingSystem class: one for each car type (big, medium, small). The constructor's role is to initialize these three variables with the provided initial counts.
The addCar(int carType) method contains the main logic. It uses a conditional block (an if-else if-else structure) to handle the different car types:
- It first checks if
carTypeis 1 (for a big car). - If it is, it checks if there are any available big slots (
bigSlots > 0). - If a slot is available, it decrements the count of big slots and returns
true. - If no slot is available, it returns
false. - The same logic is repeated for medium (
carType == 2) and small (carType == 3) cars, using their respective counter variables.
While this method is very explicit and easy to understand for a fixed set of three car types, it becomes less elegant and harder to maintain if the number of types were to increase.
class ParkingSystem { private int bigSlots; private int mediumSlots; private int smallSlots; public ParkingSystem(int big, int medium, int small) { this.bigSlots = big; this.mediumSlots = medium; this.smallSlots = small; } public boolean addCar(int carType) { if (carType == 1) { if (this.bigSlots > 0) { this.bigSlots--; return true; } } else if (carType == 2) { if (this.mediumSlots > 0) { this.mediumSlots--; return true; } } else if (carType == 3) { if (this.smallSlots > 0) { this.smallSlots--; return true; } } return false; }}Complexity
Time
O(1). Both the constructor and the `addCar` method perform a constant number of operations (assignments and comparisons), resulting in constant time complexity.
Space
O(1). The space required is constant as it only uses three integer variables to store the slot counts, regardless of the number of cars or calls to `addCar`.
Trade-offs
Pros
Extremely simple to implement and understand for the given problem constraints.
No overhead from using more complex data structures.
Cons
The code is verbose and contains repetitive logic.
It is not easily scalable. Adding a new car type would require adding another branch to the
if-elsestructure, modifying the core logic of theaddCarmethod.
This approach is a more streamlined and scalable solution. It uses an array to store the counts of available slots. The carType is used as a direct index to access the count for the corresponding parking space, which eliminates the need for conditional statements and makes the code more concise.
Algorithm
- Initialize an integer array,
slots, of size 4 in the constructor to allow for 1-based indexing. - Store the initial counts at indices corresponding to the car types:
slots[1] = big,slots[2] = medium,slots[3] = small. The 0-th index is unused. - In the
addCarmethod, use thecarTypeparameter directly as an index for theslotsarray. - Check if
slots[carType]is greater than 0. - If it is, decrement
slots[carType]and returntrue. - Otherwise, return
false.
Walkthrough
A more efficient and elegant way to solve this problem is by using a data structure that maps the car type to its available slot count. An array is a perfect fit for this since the car types are integers (1, 2, 3) that can be used as indices.
We declare an integer array, slots, as a member variable. To simplify indexing, we can make the array of size 4, so that we can use 1-based indexing that directly corresponds to the carType values. slots[0] will be unused.
The constructor initializes this array with the given counts: slots[1] is set to big, slots[2] to medium, and slots[3] to small.
The addCar(int carType) method then becomes remarkably simple. It checks if the count at slots[carType] is positive. If it is, it decrements the count and returns true. Otherwise, it returns false. This design is not only cleaner but also more maintainable and scalable.
class ParkingSystem { private int[] slots; public ParkingSystem(int big, int medium, int small) { // Use a 1-based index for car types 1, 2, 3. // slots[0] is unused. this.slots = new int[]{0, big, medium, small}; } public boolean addCar(int carType) { // carType is guaranteed to be 1, 2, or 3. if (this.slots[carType] > 0) { this.slots[carType]--; return true; } return false; }}Complexity
Time
O(1). The constructor and `addCar` method both have constant time complexity. Array initialization and access by index are O(1) operations.
Space
O(1). The space used is for an array of a fixed size (4), which is constant and does not depend on the number of calls to `addCar`.
Trade-offs
Pros
Concise and clean code that avoids repetitive
if-elseblocks.Highly scalable. If new car types were added, the logic would remain the same; only the array initialization would change.
Directly maps the input
carTypeto its corresponding data, which is an elegant design.
Cons
Uses a slightly larger, though still constant, amount of memory for the array compared to individual variables.
The 0-th index of the array is unused, which is a minor inefficiency in space usage.
Solutions
Solution
public class ParkingSystem { private List < int > cnt ; public ParkingSystem ( int big , int medium , int small ) { cnt = new List < int >() { 0 , big , medium , small }; } public bool AddCar ( int carType ) { if ( cnt [ carType ] == 0 ) { return false ; } -- cnt [ carType ]; return true ; } } /** * Your ParkingSystem object will be instantiated and called as such: * ParkingSystem obj = new ParkingSystem(big, medium, small); * bool param_1 = obj.AddCar(carType); */class ParkingSystem { private int [] cnt ; public ParkingSystem ( int big , int medium , int small ) { cnt = new int [] { 0 , big , medium , small }; } public boolean addCar ( int carType ) { if ( cnt [ carType ] == 0 ) { return false ; } -- cnt [ carType ]; return true ; } } /** * Your ParkingSystem object will be instantiated and called as such: * ParkingSystem obj = new ParkingSystem(big, medium, small); * boolean param_1 = obj.addCar(carType); */class ParkingSystem { public: vector < int > cnt ; ParkingSystem ( int big , int medium , int small ) { cnt = { 0 , big , medium , small }; } bool addCar ( int carType ) { if ( cnt [ carType ] == 0 ) return false ; -- cnt [ carType ]; return true ; } }; /** * Your ParkingSystem object will be instantiated and called as such: * ParkingSystem* obj = new ParkingSystem(big, medium, small); * bool param_1 = obj->addCar(carType); */class ParkingSystem : def __init__ ( self , big : int , medium : int , small : int ): self . cnt = [ 0 , big , medium , small ] def addCar ( self , carType : int ) -> bool : if self . cnt [ carType ] == 0 : return False self . cnt [ carType ] -= 1 return True # Your ParkingSystem object will be instantiated and called as such: # obj = ParkingSystem(big, medium, small) # param_1 = obj.addCar(carType)Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.