03 · OOP for DSA & Design Rounds
#1603 Design Parking System
frequently reported atAmazon
the problem
In plain words
A parking lot has a fixed number of big, medium and small slots, given to the constructor ParkingSystem(big, medium, small). addCar(carType) (1 = big, 2 = medium, 3 = small) parks the car in a free slot of exactly its size and returns true, or returns false if none is free.
in ParkingSystem(1, 1, 0); addCar(1), addCar(2), addCar(3), addCar(1)
out true, true, false, false
There is no small slot at all, and the only big slot is taken by the first car.
- 0 ≤ big, medium, small ≤ 1000
- carType is 1, 2 or 3
- At most 1000 calls to addCar
your turn
Try it before you peek
Read the examples, say the brute force out loud, then write code: here or on LeetCode ↗. Stuck for 20 minutes? Open one hint at a time.
Solve it in the browser
Design: implement every operation. Compiled by the real javac (Java 17) and judged right here — nothing is sent anywhere.
Solutions are hidden so you can try first. Even 20 minutes of real effort makes the answer stick far better than reading it.
Marking the problem solved, or opening every hint, also shows it.
the aha
Key insight
patternClass design: state + operations
where this runsjava.util.concurrent.Semaphore works the same way: it keeps only a count of available permits, not permit objects.
Which slot a car takes never matters, only how many are left. Store three counts, ideally in an int[] indexed by carType so addCar needs no branching on the type.
solutions
From brute force to optimal
Model every slot as a boolean and scan for a free one.
taken[type] = new boolean[count]for each size.- addCar: scan
taken[carType]for a false, set it and return true; otherwise return false.
A nearly full lot means scanning every slot of that size.
One flag per slot.
// On LeetCode, name this class ParkingSystem.class ParkingSystemSlots { private final boolean[][] taken; // taken[type][slot]: one flag per physical slot public ParkingSystemSlots(int big, int medium, int small) { taken = new boolean[][] {new boolean[0], new boolean[big], new boolean[medium], new boolean[small]}; } public boolean addCar(int carType) { boolean[] slots = taken[carType]; for (int i = 0; i < slots.length; i++) { // scan for a free slot: O(capacity) if (!slots[i]) { slots[i] = true; return true; } } return false; }}Only the number of free slots matters.
- Fields
big,medium,small. - addCar: pick the counter with if/else; if it is 0 return false, else decrement and return true.
A fixed number of comparisons.
Three ints.
// On LeetCode, name this class ParkingSystem.class ParkingSystemCounters { private int big; // only the COUNT of free slots matters private int medium; private int small; public ParkingSystemCounters(int big, int medium, int small) { this.big = big; // this.big is the field, big is the parameter this.medium = medium; this.small = small; } public boolean addCar(int carType) { if (carType == 1) { if (big == 0) return false; big--; } else if (carType == 2) { if (medium == 0) return false; medium--; } else { if (small == 0) return false; small--; } return true; }}free[carType] replaces the if/else chain.
free = {0, big, medium, small}(index 0 unused).- addCar: if
free[carType] == 0return false; otherwisefree[carType]--and return true.
One array read and one write.
Four ints.
class ParkingSystem { private final int[] free; // free[1] big, free[2] medium, free[3] small public ParkingSystem(int big, int medium, int small) { free = new int[] {0, big, medium, small}; // index 0 unused, so carType IS the index } public boolean addCar(int carType) { if (free[carType] == 0) return false; free[carType]--; return true; }}in the room
How to say it in the interview
talk track
- Point out that slot identity never matters, so counts are enough.
- Use instance fields, not static ones: the judge may create several parking lots.
- If asked to extend it: an enum
CarType, or aMap<CarType, Integer>when the types are not simply 1..3.
traps
- Making the counters
static: two ParkingSystem objects would share their slots. - Off-by-one on carType:
free[carType - 1]with a 3-element array, or forgetting that index 0 is unused in a 4-element one.
what they ask next
Follow-ups
What if a car may also take a bigger slot when its own size is full?
Try free[carType], then each bigger size in turn (for a small car: small, medium, big). Still O(1) with three sizes.
What if several entry gates call addCar at the same time?
Make addCar synchronized, or keep one AtomicInteger per size and decrement it in a compare-and-set loop, so two cars can never take the last slot.
before you submit
Edge cases to test
- A size with 0 slots from the start.
- A size that fills up while more cars of that size arrive.
- Two ParkingSystem objects in the same test: their counts must not mix.
practise next
Similar problems
- #622Design Circular QueueMediumin Queues
- #155Min StackMediumin Stacks
- #705Design HashSetEasyin Java OOP