Design Parking System

Easy

Asked by:

23 views

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 the ParkingSystem class. 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 of carType for the car that wants to get into the parking lot. carType can be of three kinds: big, medium, or small, which are represented by 1, 2, and 3 respectively. A car can only park in a parking space of its carType. If there is no space available, return false, else park the car in that size space and return true.

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 <= 1000
carType is 1, 2, or 3
At most 1000 calls will be made to addCar

Try coding it in LeetCode

Design Parking System

Easy

Asked by:

23 views

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 the ParkingSystem class. 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 of carType for the car that wants to get into the parking lot. carType can be of three kinds: big, medium, or small, which are represented by 1, 2, and 3 respectively. A car can only park in a parking space of its carType. If there is no space available, return false, else park the car in that size space and return true.

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 <= 1000
carType is 1, 2, or 3
At most 1000 calls will be made to addCar

Try coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What are the capacity limits for each car type (big, medium, small)? Can they be zero?
Will the carType parameter in the addCar function always be a valid value (1, 2, or 3)?
If a car cannot be parked due to the parking lot being full, should the addCar function return false, or should it throw an exception?
Is the parking system intended to be used by multiple threads concurrently, and if so, are there any specific synchronization requirements?
What is the expected number of calls to the addCar function throughout the lifetime of the ParkingSystem object?

Brute Force Solution

Approach

The parking system has a limited number of spots for each car size. The brute force approach simulates every possible parking attempt to see if there's space for a given car.

Here's how the algorithm would work step-by-step:

When a car tries to park, first check if there's any available spot for its size.
If there is, mark that spot as occupied.
If there isn't, report that the car cannot park.
Each time a car parks, we must update the number of remaining spots for that car size.
After trying all possible parking attempts, we know if a given car can park.

Code Implementation

class ParkingSystem:

    def __init__(self, big_spots: int, medium_spots: int, small_spots: int):
        self.available_big_spots = big_spots
        self.available_medium_spots = medium_spots
        self.available_small_spots = small_spots

    def addCar(self, car_type: int) -> bool:
        # Check for big cars
        if car_type == 1:
            if self.available_big_spots > 0:
                self.available_big_spots -= 1

                return True
            else:
                return False

        # Check for medium cars
        elif car_type == 2:
            if self.available_medium_spots > 0:
                self.available_medium_spots -= 1

                return True
            else:
                return False

        # Check for small cars
        elif car_type == 3:
            # Only proceed if there's space
            if self.available_small_spots > 0:
                self.available_small_spots -= 1

                return True
            else:
                return False

        return False

Big(O) Analysis

Time Complexity

O(1) – The problem states we have a parking system with a limited number of spots for each car size. The 'addCar' operation involves checking the availability of a spot for the car size and decrementing the corresponding count if available. These are constant-time operations as they do not depend on the number of cars attempting to park, nor does it iterate through a data structure of variable size. Therefore the time complexity is O(1).

Space Complexity

O(1) – The parking system only requires storing a fixed number of integers representing the remaining spots for each car size (small, medium, and large). The number of such spots is predetermined in the constructor, and updated in-place when a car parks. Therefore, the auxiliary space used is constant regardless of the number of parking attempts (N), leading to O(1) space complexity.

Optimal Solution

Approach

The design parking system problem can be solved efficiently by keeping track of the number of parking spots available for each car type. We simply decrement the count for the corresponding car type when a car parks and check to make sure there's space before doing so.

Here's how the algorithm would work step-by-step:

At the start, note down how many parking spaces are available for each of the three car sizes: small, medium, and large.
When a car tries to park, check if there is a parking space available for that car's size.
If there is a space, decrease the number of available spaces for that car size by one, and confirm that the car can park.
If there are no spaces available for that car size, simply report that the car cannot park.

Code Implementation

class ParkingSystem:

    def __init__(self, big_spots: int, medium_spots: int, small_spots: int):
        self.available_big_spots = big_spots
        self.available_medium_spots = medium_spots
        self.available_small_spots = small_spots

    def addCar(self, car_type: int) -> bool:
        # Check the car type and corresponding spot availability
        if car_type == 1:
            if self.available_big_spots > 0:
                self.available_big_spots -= 1
                return True
            else:
                return False
        elif car_type == 2:
            if self.available_medium_spots > 0:
                self.available_medium_spots -= 1
                return True
            else:
                return False
        else:
            # Handle small car parking
            if self.available_small_spots > 0:
                # Decrement the count and return true
                self.available_small_spots -= 1
                return True
            else:
                # Indicate parking is unavailable
                return False

Big(O) Analysis

Time Complexity

O(1) – The constructor takes constant time as it initializes a fixed number of counters (one for each car type). The addCar method performs a constant number of checks and decrements regardless of any input size. Therefore, both operations have a time complexity of O(1).

Space Complexity

O(1) – The space complexity of the parking system design is O(1) because we use a fixed number of variables to store the capacity of each car type (small, medium, and large). Specifically, we store the initial counts for each car size. The amount of memory used does not depend on the number of parking requests or any other input size N. Therefore, the auxiliary space used is constant.

Edge Cases

Case	How to Handle
Initial number of slots for a car type is negative	Throw an IllegalArgumentException as the number of slots must be non-negative.
Car type is outside the valid range (1, 2, 3)	Throw an IllegalArgumentException as the car type must be within the defined range.
addCar called with null or invalid car type	Throw an IllegalArgumentException if the car type is null or outside the valid range.
Multiple calls to addCar deplete a type's slots to negative	The addCar method should return false if no slots are available and the count becomes negative.
Integer overflow when adding cars of the same type repeatedly	The internal counters should be carefully checked for integer overflow and prevent addition if it occurs.
Maximum number of addCar calls exceeding memory limits	The initial number of slots should be chosen such that memory usage from many addCar calls stays within reasonable limits.
All slots are initialized to zero	The addCar method should always return false as there are no initial spots.
Very large initial slot sizes provided	Consider potential memory usage and performance impact of extremely large initial sizes, possibly limiting the maximum allowed size to prevent resource exhaustion.