MediumHeapAI interview only
Design A Leaderboard
Asked atamazonbloomberggoogle
01 · Problem
Build a Leaderboard class that tracks player scores:
Leaderboard()creates an empty leaderboard.void addScore(int playerId, int score)addsscoreto the player's total. A player not yet on the board joins with that score.int top(int K)returns the sum of theKhighest totals currently on the board.void reset(int playerId)removes the player from the board (equivalent to setting their score to 0 and dropping them). The player is guaranteed to be on the board when this is called, and may be added again later.
When top is called, K is guaranteed to be between 1 and the number of players currently on the board.
02 · Examples
Example 01
Input
["Leaderboard","addScore","addScore","addScore","addScore","addScore","top","reset","reset","addScore","top"], [[],[1,73],[2,56],[3,39],[4,51],[5,4],[1],[1],[2],[2,51],[3]]
Output
[null,null,null,null,null,null,73,null,null,null,141]
Totals become {1:73, 2:56, 3:39, 4:51, 5:4}; top(1) = 73. Players 1 and 2 are reset, then player 2 rejoins with 51. Totals are {2:51, 3:39, 4:51, 5:4}, so top(3) = 51 + 51 + 39 = 141.
Example 02
Input
["Leaderboard","addScore","addScore","addScore","top","top"], [[],[7,10],[8,20],[7,15],[1],[2]]
Output
[null,null,null,null,25,45]
Player 7 accumulates 10 + 15 = 25 and player 8 has 20. top(1) = 25 and top(2) = 25 + 20 = 45.
Example 03
Input
["Leaderboard","addScore","addScore","reset","addScore","top"], [[],[1,5],[2,9],[2],[3,4],[2]]
Output
[null,null,null,null,null,9]
After resetting player 2 the board holds {1:5, 3:4}, so top(2) = 9.
03 · Constraints
- 011 <= playerId, K <= 104
- 021 <= score <= 100
- 03At most 1000 calls are made to each method
- 04reset is only called for a player currently on the board
- 051 <= K <= number of players on the board when top is called
04 · Optimal complexity
- Time
- O(1) addScore/reset, O(p log K) top
- Space
- O(p)
05 · Two ways to work on it
Practice it alone or rehearse it as an interview.
Practice Mode gives you an editor and test runs, nothing else. AI Interview Mode puts a voice interviewer on the other side, adds a clock, and ends with a scored summary of the round.