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.
```
Quick Answer: Implement reusable locker-bank operations that allocate the lowest available number, reject invalid stores or pickups, release lockers immediately, and preserve the last successful store.
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 the bank is full. Pickup releases and returns that customer's locker, or -1 if none is assigned. Last returns the locker number from the most recent successful store, or -1 if no store has succeeded. Return one result for every 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.
- Every operation contributes exactly one returned integer.
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; locker 1 is released and immediately reused as the smallest free locker.
Input: (3, [])
Expected Output: []
Explanation: An empty operation sequence returns no results.
Hints
- Use a min-oriented structure for currently free locker numbers.
- Track each assigned customer's locker separately from the most recent successful store.