Maintain an Escape-Room Leaderboard
Company: Pinterest
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: hard
Interview Round: Technical Screen
Design and implement an `EscapeRoomGame` for a fixed set of players and rooms `0` through `R`.
- `advance(player_id)` moves that player forward by one room in `O(1)`. A player already in room `R` remains there.
- `get_room(player_id)` returns the current room in `O(1)`.
- `leaderboard(k)` returns up to `k` player IDs ordered by room descending. Players in the same room are ordered by the time they entered that room, earliest first. Its required time is `O(N + k)`, where `N` is the player count.
All players begin in room `0`; their initial tie order is the order in the constructor's player list.
For console evaluation, player IDs are integers and every operation is a homogeneous two-integer row `[opcode, argument]`:
- `[0, player_id]` means `advance(player_id)`.
- `[1, player_id]` means `get_room(player_id)`.
- `[2, k]` means `leaderboard(k)`.
Implement `escape_room_results(players, R, operations)` and return a list of integer lists. Append `[0, room]` for each room query and `[1, player_id_1, ..., player_id_m]` for each leaderboard query. The leading tag keeps every result in one portable nested-integer representation. Advance operations produce no result.
### Constraints
- `1 <= N <= 100000`, and `players` contains unique integer IDs in the inclusive range `0` through `10^9`, in their initial tie order.
- `1 <= R <= 10000`
- At most `200000` operations are supplied.
- Every referenced player exists, every player ID in an operation is in the inclusive range `0` through `10^9`, and `1 <= k <= N`.
```hint Test tie stability after movement
When two players share a room, moving one away and later back changes when that player entered the shared room.
```
```hint Respect all three complexity targets
A design that reorders every player for each leaderboard call may produce correct small examples but miss the required bound.
```
Quick Answer: Design and implement an `EscapeRoomGame` for a fixed set of players and rooms `0` through `R`. Work through the function contract, boundary cases, correctness argument, and time and space complexity expected in a production-quality solution.
Maintain fixed players in rooms zero through `R`. Advance moves one room in O(1), stopping at R; room lookup is O(1). A leaderboard returns up to k IDs by room descending, then by earliest entry time into that room, in O(N+k). All players start in room zero in constructor order. Return tagged room and leaderboard records for the homogeneous console operations.
Constraints
- 1 <= N <= 100000; player IDs are unique integers from 0 through 10^9 in initial tie order.
- 1 <= R <= 10000 and at most 200000 homogeneous two-integer operations are supplied.
- Every referenced player exists; opcode 2 uses 1 <= k <= N.
- Return [0,room] for room queries and [1,player_ids...] for leaderboards; advances return nothing.
Examples
Input: ([10], 1, [])
Expected Output: []
Explanation: No operations produce no result records.
Input: ([10], 1, [[1, 10]])
Expected Output: [[0, 0]]
Explanation: Every player begins in room zero.
Hints
- Test the initial leaderboard, k smaller than N, and k equal to N.
- Advance players into the same room at different times and repeat an advance after one reaches room R.
- Interleave advances, room queries, and leaderboards while using both player-ID boundaries.