Design A Leaderboard
Medium · Design · Design · Hash Table · Sorting
Problem
Keep a running scoreboard for a game. Every player starts off the board.
- addScore(playerId, score) — add score points to that player's total, putting the player on the board with score if they are not there yet
- top(K) — return the sum of the K highest totals currently on the board
- reset(playerId) — take the player off the board entirely; if they score again later, they start from zero
Only the sum is asked for, not who the top players are, so players who tie at the cut-off are interchangeable. reset is only called for a player who is on the board, and top(K) never asks for more players than the board holds.
Your tests replay a call sequence: the first entry names the class, each later entry is a method with its arguments, and calls returning nothing report None.
Examples
Input: addScore(1,73), addScore(2,56), addScore(3,39), addScore(4,51), addScore(5,4), top(1), reset(1), reset(2), addScore(2,51), top(3) Output: 73, then 141
Player 1 leads with 73. After players 1 and 2 are taken off, player 2 comes back with a fresh 51, so the board holds 51, 39, 51 and 4, and the best three add to 51 + 51 + 39 = 141.
Input: addScore(7,10), addScore(7,15), addScore(8,20), top(1) Output: 25
Player 7 has scored twice, so their total is 25 and they lead player 8.
Constraints
- 1 <= playerId, K <= 10^4
- 1 <= score <= 100
- K never exceeds the number of players on the board
- reset is only called for a player on the board
- At most 1000 calls
Approaches
- Hash map, sort every total on each top — time O(1) update, O(n log n) top, space O(n)
Follow-up
What if the board holds millions of players and the game also asks for a single player's rank? Totals are bounded, so a Fenwick tree indexed by total (counting players and summing points) answers both the top-K sum and "how many are ahead of me?" in O(log maxScore).
Related problems
Start free on Cariara · Coding problems · System design studio
