A car park that finds the nearest slot
Build ParkingLot for a car park whose slots are numbered from 1. Every slot has a size: 1 for small, 2 for medium, 3 for large. A car of size s fits any slot of size s or bigger.
ParkingLot(sizes) opens the car park with every slot free: slot i + 1 has size sizes[i].
park(car, size) parks car, which has size size, in the lowest-numbered free slot it fits, and returns that slot's number. If no free slot fits, the car is not parked and park returns -1.
leave(car) frees the slot car is parked in and returns that slot's number, or returns -1 if car is not parked.
freeSlots(size) returns how many free slots have exactly that size.
park is only called for a car that is not parked. Aim for O(log n) time per call.
- Input
["ParkingLot","park","park","park","park","freeSlots","leave","park","leave","freeSlots"]
[[[1,2,3,1]],[10,2],[11,2],[12,3],[13,1],[1],[11],[12,3],[99],[3]]- Output
[null,2,3,-1,1,1,3,3,-1,0]
Car 11 needs size 2 or more; slot 2 is taken, so it gets the large slot 3. Car 12 finds no large slot free until car 11 leaves.
- Input
["ParkingLot","park","park","leave","leave","freeSlots"]
[[[3]],[1,1],[2,1],[1],[1],[3]]- Output
[null,1,-1,1,-1,1]
A small car may take the only slot, a large one. Once it has left, leaving again gives -1.
Limits
1 <= number of slots <= 50000every slot size, and every car size, is 1, 2 or 31 <= car <= 100000park is only called for a car that is not parkedat most 20000 calls after the constructor
Hints
Hint 1
For each size, keep the free slots of that size where the lowest number is quick to find: a min-heap per size.
Hint 2
A car of size s may go in the heaps for sizes s, s + 1 and 3: take the smallest top among them. Remember each parked car's slot so leave can put it back.
Where this was reported
Our own problem on the task these candidates describe; the wording, examples and tests are InternDoor’s.
Run your code to check it on the examples. Submit runs every hidden test.