SDE Path

Parking Lot

Medium

Parking Lot

The most iconic OOD interview question, made judge-able: size-tiered spot allocation, vehicle tracking, and availability queries.

Requirements

  • Spot labels are the size letter plus 0-based index within that tier: S0…S(numSmall-1), M0…, L0….
  • Allocation policy: try tiers smallest-to-largest among those the vehicle fits, and within a tier the lowest free index. (A motorcycle takes S2 before M0; a car never takes an S spot.)
  • Freed spots become allocatable again immediately, and the lowest-index rule still applies.
  • Track vehicles by id so leave is O(1)-ish, not a lot scan.

API to implement

Implement the class ParkingLot. The I/O driver is already written in the starter code — it parses the command script below and calls your methods. You only implement the class.

| Command | Returns | Behavior | |---|---|---| | park <vehicleType> <vehicleId> | string | Park a MOTORCYCLE (fits S/M/L), CAR (M/L) or BUS (L only). Allocate the smallest sufficient tier with a free spot, lowest index first. Return the spot label (S0, M3, L1, …) or FULL. vehicleId is not currently parked. | | leave <vehicleId> | boolean | Vehicle leaves; its spot frees up. Return false if the id isn't parked, else true. | | free <size> | int | Number of free spots of size S, M, or L. |

Input format

The first line contains Q, the number of operations. The second line contains the constructor arguments: numSmall, numMedium, numLarge — spot counts per size tier. Each of the next Q lines is one command as listed above. String arguments contain no spaces.

Output format

For each command with a non-void return, print its result on its own line, in order. The driver does this for you — your methods just return values.

This is a design problem: the hidden tests exercise edge cases and interaction sequences, not performance tricks. Model the state cleanly and the tests will pass.

Sample cases

Example 1
Input
9
1 1 1
park MOTORCYCLE m1
park MOTORCYCLE m2
park CAR c1
park CAR c2
free S
free M
leave m1
park MOTORCYCLE m3
leave ghost
Expected output
S0
M0
L0
FULL
0
0
true
S0
false
Example 2
Input
9
0 1 2
park BUS b1
park BUS b2
park BUS b3
park MOTORCYCLE m1
free L
leave b1
park CAR c1
free L
free M
Expected output
L0
L1
FULL
M0
0
true
L0
0
0