Support room moves and query top-k fastest
Company: Pinterest
Role: Machine Learning Engineer
Category: Coding & Algorithms
Difficulty: hard
Interview Round: Onsite
## Problem
There are `R` rooms labeled `0..R-1` (in increasing order), and `P` people labeled `0..P-1`.
- Initially, **all people are in room 0**.
- Operation `move(personId)` moves that person **from room i to room i+1**, if `i < R-1`. (If already in the last room, they stay there.)
- Within each room, maintain the **arrival order** of people (FIFO by the time they entered that room).
Design a data structure that supports:
1. `countInRoom(roomId) -> int`
- Return how many people are currently in `roomId`.
- Must be **O(1)** time.
2. `topKFastest(k) -> list[int]`
- Return the **k fastest people**, where “faster” means:
1) People in **higher-numbered rooms** are faster (closer to the end).
2) For people in the **same room**, the one who **entered that room earlier** is faster.
- Return fewer than k people if `k > P`.
### Example
`R = 5`, `P = 5`.
Operations:
- `move(1)`, `move(2)`, `move(1)`
State:
- Person 1 is in room 2
- Person 2 is in room 1
- Others are in room 0
So:
- `countInRoom(1) == 1`, `countInRoom(2) == 1`
- `topKFastest(2)` returns `[1, 2]` (order can be `[1,2]` given the definition above).
## Complexity expectations
Explain the time complexity of each operation and aim for efficient updates (especially avoiding scanning all people for `countInRoom` or `topKFastest`).
Quick Answer: This question evaluates understanding of dynamic data structure design and ordering semantics, specifically maintaining per-room FIFO arrival order, constant-time room counts, and efficient top-k retrieval based on hierarchical priorities.
Initially people 0..P-1 are in room 0 in label order. move(person) advances that person one room unless already in the last room. count(room) returns occupancy. top(k) returns people in higher-numbered rooms first; ties within a room use earlier arrival order. Implement solution(R, P, operations) and return outputs from count/top operations.
Constraints
- R and P are non-negative
- move at the last room leaves the person there
Examples
Input: (5, 5, [['move', 1], ['move', 2], ['move', 1], ['count', 1], ['count', 2], ['top', 2]])
Expected Output: [1, 1, [1, 2]]
Input: (2, 3, [['top', 5], ['move', 0], ['move', 0], ['top', 3], ['count', 1]])
Expected Output: [[0, 1, 2], [0, 1, 2], 1]
Input: (0, 2, [['top', 1], ['count', 0]])
Expected Output: [[], 0]
Hints
- Maintain a current room per person and an arrival-ordered container per room.