Implement a Reusable Locker Allocation System
Company: Google
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
## Problem
A locker bank has lockers numbered from 1 through `n`. Process operations in
order. `store(customer)` assigns the smallest available locker and returns its
number, or `-1` if that customer already has a locker or none is available.
`pickup(customer)` releases and returns that customer's locker, or `-1` if no
locker is assigned. `last()` returns the locker number from the most recent
successful `store`, or `-1` if there has not been one. Return one result per
operation.
### Constraints & Assumptions
- `1 <= n <= 200,000`.
- There are at most 200,000 operations.
- Customer IDs are non-empty strings.
- A released locker becomes immediately available for reuse.
### Clarifications
- Failed store and pickup operations do not change `last()`.
- The allocation rule is always the smallest currently free locker number.
- A customer can store again after a successful pickup.
### Examples
```text
n = 3
operations = [store("a"), store("b"), pickup("a"), store("c"), last()]
output = [1, 2, 1, 1, 1]
```
### Hints
```hint Track free lockers
Use an ordered structure that can remove and reinsert the minimum locker efficiently.
```
```hint Track ownership
A map from customer ID to locker supports validation and pickup.
```
Overview: Build a locker allocator that assigns the smallest free locker, tracks customer ownership, supports pickup and reuse, and remembers the latest successful assignment.
Process a fresh locker bank with lockers numbered 1 through n. Operations are ["store", customer], ["pickup", customer], or ["last"]. Store assigns and returns the smallest available locker, or -1 if the customer already owns one or none is free. Pickup releases and returns that customer's locker, or -1 if none is assigned. Last reports the locker from the most recent successful store, or -1 before any success. Return one integer per operation.
Constraints
- 1 <= n <= 200000.
- operations contains at most 200000 encoded store, pickup, or last lists.
- Customer IDs are non-empty strings.
- A released locker becomes immediately available for reuse.
- Failed store and pickup operations do not change last.
- A customer can store again after a successful pickup.
Examples
Input: (3, [['store', 'a'], ['store', 'b'], ['pickup', 'a'], ['store', 'c'], ['last']])
Expected Output: [1, 2, 1, 1, 1]
Explanation: This is the source example; the released smallest locker is reused.
Input: (5, [])
Expected Output: []
Explanation: An empty batch produces no per-operation results.
Hints
- Keep available locker numbers in a min-oriented structure.
- Use a customer-to-locker map to validate stores and pickups.