Leetcode – Design Parking System Solution

Spread the love

Designing a system that reflects real-world functionality is a classic category of problems in software engineering interviews. These problems focus not just on algorithmic complexities but also on design patterns, modularity, and object-oriented principles. One such problem in this domain is the “Design Parking System” problem found on Leetcode.

This problem may appear straightforward, but it touches upon essential concepts like encapsulation, class design, and method creation. In this extensive article, we’ll dissect the problem thoroughly, explore the Pythonic way of solving it, discuss its time and space complexity, and look at possible enhancements and improvements.

Problem Statement

The original problem statement on Leetcode is as follows:

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 is given as part of the constructor.
  • bool addCar(int carType) Checks whether there is a parking space of carType for the car. A carType of 1, 2, and 3 represents a big, medium, and small car, respectively. It returns true if the car can be parked and false if the car cannot be parked.

Example:

parkingSystem = ParkingSystem(1, 1, 0);
parkingSystem.addCar(1); # return true, big slot is available
parkingSystem.addCar(2); # return true, medium slot is available
parkingSystem.addCar(3); # return false, small slot is not available
parkingSystem.addCar(1); # return false, big slot is already taken

Understanding the Problem

The main idea behind the problem is to design a system that can manage a parking lot with different sizes of slots: big, medium, and small. Each car that arrives specifies its type (big, medium, or small), and the system needs to check whether a corresponding slot is available.

Algorithmic Approach

Since this is a design problem, our main focus will be on crafting classes and methods that encapsulate the required functionality. The steps to solve the problem are as follows:

  1. Initialization: Create a ParkingSystem class with a constructor that initializes the number of slots for each type of parking space.
  2. Checking and Allocation: Implement a method addCar to check if a parking space is available for a particular type of car and allocate it if available.

Python Code Implementation

Here is how you can implement the parking system using Python:

class ParkingSystem:

    def __init__(self, big: int, medium: int, small: int):
        self.slots = {1: big, 2: medium, 3: small}

    def addCar(self, carType: int) -> bool:
        if self.slots[carType] > 0:
            self.slots[carType] -= 1
            return True
        else:
            return False

Code Explanation

  1. Constructor (__init__): This initializes an instance of the ParkingSystem class. We use a dictionary self.slots to store the number of slots available for each type of car. The keys 1, 2, and 3 represent big, medium, and small cars, respectively.
  2. Method addCar: This method checks if a slot is available for a given carType. If yes, it decrements the available slots for that carType by 1 and returns True. Otherwise, it returns False.

Time and Space Complexity

  1. Time Complexity:
    • The constructor (__init__) runs in O(1) time as it only involves initializing a dictionary.
    • The addCar method also runs in O(1) time as dictionary lookup and modification are constant-time operations.
  2. Space Complexity: The space complexity for the parking system is O(1) because the size of the dictionary remains constant regardless of the number of operations performed.

Possible Enhancements and Variants

  1. Slot Release: You can add a releaseCar method that increments the available slot count for a particular car type.
  2. Parking Levels: To make it more realistic, you can add multiple levels to the parking lot.
  3. Pricing Strategy: Different types of parking slots can have different costs, and you could add methods to manage pricing.
  4. Validation: Additional validation could be added to ensure the car type is one of the defined types.

Conclusion

The “Design Parking System” problem serves as a solid introduction to system design fundamentals within the context of a relatively simple domain. This problem is excellent for brushing up on class design and encapsulation in Python. It is relatively straightforward but offers a good base for those interested in more complex system design questions. By working through it, you not only gain practical experience with Python’s object-oriented features but also engage in an exercise of translating real-world constraints into code.

Leave a Reply