Problem · Hash Table
Live Top-K Spaces by Active Users
Learn this problem● Hard
xAIFULLTIMEONSITE INTERVIEW
xAIFULLTIMEONSITE INTERVIEWProblem statement
Process records in order. Each record is [operation, space, user, timestamp]. A create event creates a Space and adds its creator; join adds an inactive user; leave removes an active user.
After every record, produce a snapshot containing up to k observed Spaces with the largest current active-user counts. Format each entry as space:count. Order a snapshot by count descending, then by Space name ascending for ties. Once observed, a Space remains eligible with count zero.
Return the snapshots in event order.
Function
liveTopSpaces(records: String[][], k: int) → String[][]Examples
Example 1
records = [["create","abc","u1","1"],["join","abc","u2","2"],["create","def","u3","3"],["leave","abc","u1","4"],["leave","abc","u2","5"]]k = 2return = [["abc:1"],["abc:2"],["abc:2","def:1"],["abc:1","def:1"],["def:1","abc:0"]]After the fourth event both Spaces have one active user, so abc wins the name tie-break. After the fifth, def ranks ahead of the now-empty abc.
Example 2
records = [["create","z","u1","1"],["create","a","u2","2"],["create","m","u3","3"]]k = 1return = [["z:1"],["a:1"],["a:1"]]With equal counts and k = 1, the lexicographically smallest observed Space is selected.
Constraints
1 <= records.length <= 100000.1 <= k <= 100.- Every record has exactly four strings and a valid
create,join, orleavelifecycle transition. - Timestamps are nondecreasing; ranking depends only on event order.
- Space and user names are non-empty ASCII strings without
:. - The total number of returned entries is at most
1000000.