Design room progression with leaderboard
Company: Uber
Role: Machine Learning Engineer
Category: Coding & Algorithms
Difficulty: Medium
Interview Round: Onsite
Quick Answer: This question evaluates the ability to design efficient dynamic data structures and algorithms for maintaining per-player state and a real-time leaderboard, including score aggregation, room transitions, and high-throughput updates.
Constraints
- Player ids and room ids are non-negative integers.
- recordTask only counts when roomId equals the player's current room.
- topK breaks score ties by smaller player id and returns all players when k exceeds the player count.
- Operations referencing unknown players are ignored (getPlayerState returns None).
- 1 <= number of operations <= 10^5
Examples
Input: ([('addPlayer', 1), ('addPlayer', 2), ('recordTask', 1, 0, 50), ('recordTask', 2, 0, 30), ('getPlayerState', 1), ('topK', 2)],)
Expected Output: [{'room': 0, 'score': 50}, [1, 2]]
Explanation: Both players score in room 0. getPlayerState(1) reports room 0, score 50. topK(2) ranks player 1 (50) above player 2 (30).
Input: ([('addPlayer', 5), ('recordTask', 5, 0, 10), ('moveToNextRoom', 5), ('recordTask', 5, 1, 25), ('getPlayerState', 5)],)
Expected Output: [{'room': 1, 'score': 35}]
Explanation: Player 5 scores 10 in room 0, moves to room 1, scores 25 there. Total score 35 accumulates across rooms; current room is 1.
Input: ([('addPlayer', 1), ('addPlayer', 2), ('addPlayer', 3), ('recordTask', 1, 0, 100), ('recordTask', 2, 0, 100), ('recordTask', 3, 0, 40), ('topK', 2)],)
Expected Output: [[1, 2]]
Explanation: Players 1 and 2 tie at 100; the tie is broken by smaller id, so the order is [1, 2] and player 3 (40) is excluded from the top 2.
Input: ([('recordTask', 9, 0, 5), ('getPlayerState', 9), ('topK', 3)],)
Expected Output: [None, []]
Explanation: Player 9 was never added, so recordTask is ignored, getPlayerState returns None, and topK returns an empty list.
Input: ([('addPlayer', 7), ('recordTask', 7, 0, 20), ('recordTask', 7, 0, 30), ('recordTask', 7, 1, 999), ('moveToNextRoom', 7), ('recordTask', 7, 1, 15), ('getPlayerState', 7), ('topK', 1)],)
Expected Output: [{'room': 1, 'score': 65}, [7]]
Explanation: While in room 0, player 7 gains 20+30=50; the recordTask for room 1 (999) is ignored because the player is still in room 0. After moving to room 1, the 15 counts. Total 50+15=65.
Input: ([('addPlayer', 1), ('addPlayer', 1), ('recordTask', 1, 0, 10), ('topK', 5)],)
Expected Output: [[1]]
Explanation: The second addPlayer(1) is a no-op (idempotent). topK with k=5 returns all existing players — just [1].
Hints
- Track three maps keyed by player id: current room, total score, and a version counter.
- For recordTask, guard on roomId == current room before adding points — a player can only score in the room they currently occupy.
- A binary heap can't decrease-key in place. Re-push a fresh (-score, id, version) entry on every score change and skip any popped entry whose version no longer matches the player's current version (lazy deletion).
- During topK, pop valid entries into a buffer (dedup with a 'seen' set) until you have k, then push the valid entries back so the heap is preserved. Ordering by (-score, id) gives highest-score-first with smaller-id tie-breaking.