Design A Leaderboard

Design A Leaderboard

1. What is this problem about?

The Design A Leaderboard interview question asks you to build a system that tracks player scores. You need to support adding scores to existing players, resetting a player's score to zero (effectively removing them), and querying the sum of the top $K$ scores on the board. This Design A Leaderboard coding problem focuses on balancing the cost of individual updates against the cost of calculating global statistics.

2. Why is this asked in interviews?

Companies like Bloomberg and Amazon ask this to test your understanding of Sorting interview patterns and data organization. It evaluates whether you can identify that you don't always need a perfectly sorted list if you only need the "Top K" sum occasionally. It also tests your ability to handle sparse data (many players, few updates).

3. Algorithmic pattern used

There are two main approaches:

• Map + Sorting: Store scores in a Map<PlayerID, Score>. For top(K), collect all scores, sort them ($O(N \log N)$), and sum the first $K$.
• Map + Ordered Map: Use a TreeMap<Score, Frequency> to store how many players have a specific score. This allows top(K) to be calculated by iterating through the scores in descending order ($O(K)$ or $O( ext{Unique Scores})$).
• Heap: For a very large $N$ and small $K$, using a Min-Heap of size $K$ during the query can find the top sum in $O(N \log K)$.

4. Example explanation

1. addScore(1, 50), addScore(2, 100), addScore(3, 20): Map: {1:50, 2:100, 3:20}.
2. top(2):
   • Collect scores: [100, 50, 20].
   • Top 2 are 100 and 50. Sum = 150.
3. reset(2): Map: {1:50, 3:20}.
4. top(1): Returns 50.

5. Common mistakes candidates make

• Sorting on every update: Maintaining a sorted list after every addScore is $O(N)$ per update, which is inefficient if updates are frequent.
• Memory Management: Not removing players from the map when their score is reset, leading to memory bloat over time.
• Incorrect Top-K Logic: Using a max-heap to store all $N$ players when you only need the sum of the top $K$.

6. Interview preparation tip

Always ask the interviewer about the read/write ratio. If top(K) is called much less frequently than addScore, a simple Map + occasional sort is often the most practical and easiest solution to implement.