1603. Design Parking System
Model: qwen2.5-coder:14b
Topics: Design
FAANG asked: 1
Acceptance rate: 86.2%
Problem Breakdown
The problem requires designing a parking system that can handle three types of parking spaces: big, medium, and small. Each type has a fixed number of slots. The ParkingSystem class needs to be implemented with two methods:
__init__(self, big, medium, small): Initializes the parking system with the given number of slots for each car type.addCar(self, carType): Checks if there is an available slot for a car of the specified type and parks it if possible.
Inputs:
- Constructor takes three integers representing the number of big, medium, and small parking slots.
- The
addCarmethod takes one integer representing the type of car (1 for big, 2 for medium, 3 for small).
Outputs:
- The constructor returns nothing (
None). - The
addCarmethod returns a boolean indicating whether the car was successfully parked.
Implicit Constraints or Tricky Edge Cases:
- If no slots are available for a given car type, return
false. - Handle cases where multiple cars of the same type try to park consecutively.
- Ensure that the input values for slots are non-negative integers within the range [0, 1000].
Intuition
A brute-force approach would involve checking each slot individually every time a car tries to park. However, this is inefficient as it would result in a high time complexity of O(n) for each addCar call.
The key insight is to use an array or list to keep track of the number of available slots for each car type. This allows us to check and update the slot count in constant time, O(1), making the solution efficient.
Approach
- Data Structure Choice: Use a list
slotswhere the index represents the car type (0 for big, 1 for medium, 2 for small) and the value at each index represents the number of available slots for that car type. - Initialization: In the constructor, initialize the
slotslist with the given number of slots for each car type. - Adding a Car:
- For the
addCarmethod, decrement the slot count for the corresponding car type if there is an available slot. - Return
trueif the car was parked successfully (i.e., the slot count was greater than zero before decrementing). - Return
falseif no slots were available.
- For the
Complexity Analysis
- Time Complexity: O(1) for both the constructor and the
addCarmethod. The operations involve constant-time list access and modification. - Space Complexity: O(1) since the space used does not depend on the input size but only on a fixed-size array of three elements.
Solution
class ParkingSystem:
def __init__(self, big: int, medium: int, small: int):
# Initialize the slots list with the number of available slots for each car type
self.slots = [big, medium, small]
def addCar(self, carType: int) -> bool:
# Decrement the slot count for the given car type if there is an available slot
if self.slots[carType - 1] > 0:
self.slots[carType - 1] -= 1
return True
return False
Edge Cases Handled
- No Slots Available: If no slots are available for a given car type, the method correctly returns
false. - Multiple Cars of Same Type: The slot count is decremented only if there is an available slot, ensuring that multiple cars of the same type can park consecutively until all slots are filled.
- Non-negative Input Values: The constructor assumes valid input values within the specified range [0, 1000].
The solution provided is correct and efficient. It handles all edge cases as described in the problem statement. The time and space complexity claims are accurate based on the constraints given.