InternDoor

A car park that finds the nearest slot

Mediumdesign · heap · hash mapDesign a class

Reported in interviews at (where)

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.

Example 1
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.

Example 2
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 <= 50000
  • every slot size, and every car size, is 1, 2 or 3
  • 1 <= car <= 100000
  • park is only called for a car that is not parked
  • at 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.

Ready for the real one?

Engineering internships and entry-level jobs in India, newest first.