There are R rooms labeled 0..R-1 (in increasing order), and P people labeled 0..P-1.
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.)
Design a data structure that supports:
countInRoom(roomId) -> int
roomId
.
topKFastest(k) -> list[int]
k > P
.
R = 5, P = 5.
Operations:
move(1)
,
move(2)
,
move(1)
State:
So:
countInRoom(1) == 1
,
countInRoom(2) == 1
topKFastest(2)
returns
[1, 2]
(order can be
[1,2]
given the definition above).
Explain the time complexity of each operation and aim for efficient updates (especially avoiding scanning all people for countInRoom or topKFastest).