Design A Leaderboard
Asked at Bloomberg, Pinterest
Problem
Design A Leaderboard asks you to support three operations: add points to a player's score, return the sum of the top K scores, and reset a player's score to zero. It is a small design problem where the discussion about data structure trade-offs matters more than the code.
Asked At
| Company | Difficulty | |
|---|---|---|
| Bloomberg | Medium | View all Bloomberg questions → |
| Medium | View all Pinterest questions → |
How to Think About It
Store scores in a hash map from player id to score. addScore and reset are then O(1).
For top(K), the simplest correct approach is to take the K largest values with a heap: O(n log K).
If top is called far more often than updates, maintain a sorted structure (a balanced BST / sorted multiset of scores). Updates become O(log n) (remove old score, insert new) and top(K) is O(K).
reset can simply delete the player; a later addScore recreates them from zero.
Talk through which operation is hot. That trade-off conversation is what the interviewer is really grading.
Optimal Approach
State: scores map.
addScore(id, s): scores[id] = scores.get(id, 0) + s.top(K): return the sum of the K largest values (heap selection).reset(id): delete id from scores.
Time: O(1) for add and reset, O(n log K) for top. Space: O(n).
What Trips People Up in Real Interviews
Fully sorting all scores on every top call without discussing alternatives.
Forgetting that addScore accumulates — it does not overwrite.
Keeping a sorted list and doing linear inserts, which makes every update O(n).
Not asking which operations dominate. The right structure depends on the read/write mix.
Solution Code
import heapq
class Leaderboard:
def __init__(self):
self.scores = {}
def addScore(self, playerId, score):
self.scores[playerId] = self.scores.get(playerId, 0) + score
def top(self, K):
return sum(heapq.nlargest(K, self.scores.values()))
def reset(self, playerId):
self.scores.pop(playerId, None)Frequently Asked Questions
What is the Design A Leaderboard problem?
Design A Leaderboard asks you to support three operations: add points to a player's score, return the sum of the top `K` scores, and reset a player's score to zero. It is a small design problem where the discussion about data structure trade-offs matters more than the code.
How do you solve Design A Leaderboard?
The optimal approach is described in detail above, including step-by-step walkthroughs, complexity analysis, and solution code in Python. Scroll up to the "Optimal Approach" section.
What companies ask Design A Leaderboard?
Design A Leaderboard is asked at Bloomberg, Pinterest. It is a medium difficulty problem.
What are common mistakes on Design A Leaderboard?
- Fully sorting all scores on every `top` call without discussing alternatives.
- Forgetting that `addScore` accumulates — it does not overwrite.
- Keeping a sorted list and doing linear inserts, which makes every update `O(n)`.
- Not asking which operations dominate. The right structure depends on the read/write mix.