Design a Leaderboard — Score Tracking with Top K

Problem Statement#

Design a leaderboard with three operations: addScore(playerId, score) adds score to a player's cumulative total; top(K) returns the sum of the top K scores; reset(playerId) resets a player's score to zero.

Constraints:

• 1 <= playerId, K <= 10000
• 1 <= score <= 100
• At most 1000 calls each to addScore, top, and reset
• top(K) guarantees at least K players have non-zero scores

Input:  addScore(1,73), addScore(2,56), addScore(3,39), addScore(4,51), top(1)
Output: 73

Input:  ... addScore(1,73), addScore(2,56), top(2), reset(1), top(2)
Output: 129, 107

Why This Problem Matters#

Real-time leaderboards are a critical component of gaming platforms, competitive programming sites like Codeforces, and live event dashboards. Redis uses sorted sets (ZADD / ZREVRANGE) as a production solution to exactly this problem at scale. In FAANG interviews, this design question tests your knowledge of heap-based top-K queries and your ability to choose between simple O(N log K) approaches and more sophisticated O(log N) sorted container solutions.

Amazon uses leaderboards for seller rankings, student performance dashboards, and internal OKR tracking. Understanding the trade-offs between heapq.nlargest (simple but O(N log K)) and SortedList (O(log N) per operation) signals that you think about production performance, not just interview solutions.

The Core Insight#

The simplest correct approach stores scores in a hashmap and uses heapq.nlargest(K, scores.values()) for top(K). This is O(N log K) per top call but O(1) for addScore and reset. For the problem's constraints (at most 1000 calls, at most 10000 players), this is perfectly acceptable.

The optimal approach for high-frequency top(K) queries uses a sorted container. Python's sortedcontainers.SortedList supports O(log N) insert, remove, and range queries. After each addScore or reset, update the sorted list. top(K) becomes O(K) by reading the last K elements.

The key implementation detail for SortedList: when updating a score, you must first remove the old score before adding the new one—otherwise duplicates accumulate.

Visual Dry Run#

Solution (Optimal)#

import heapq
from collections import defaultdict
 
class Leaderboard:
    def __init__(self):
        self.scores = defaultdict(int)
 
    def addScore(self, playerId: int, score: int) -> None:
        self.scores[playerId] += score
 
    def top(self, K: int) -> int:
        return sum(heapq.nlargest(K, self.scores.values()))
 
    def reset(self, playerId: int) -> None:
        self.scores[playerId] = 0

class Leaderboard {
    constructor() {
        this.scores = new Map();
    }
 
    addScore(id, score) {
        this.scores.set(id, (this.scores.get(id) || 0) + score);
    }
 
    top(K) {
        return [...this.scores.values()]
            .sort((a, b) => b - a)
            .slice(0, K)
            .reduce((a, b) => a + b, 0);
    }
 
    reset(id) {
        this.scores.set(id, 0);
    }
}

Time: O(N log K) for top using nlargest, O(1) for addScore and reset
Space: O(N) — one score entry per unique player ID

Common Mistakes#

• Calling reset sets score to 0 but must not delete the key—the player still exists on the leaderboard
• When using SortedList, forgetting to remove the old score before adding the new one creates phantom duplicates
• Using sorted() instead of heapq.nlargest() is O(N log N) vs O(N log K)—matters when K is much smaller than N
• Not defaulting missing player scores to 0 in addScore, causing KeyError on first access
• top(K) must sum the values, not return them as a list—a common off-by-one error in the return statement

Interview Tips#

• Start with the simple hashmap + heapq.nlargest solution, then mention the SortedList optimisation as a follow-up
• Discuss the production solution: Redis sorted sets with ZADD O(log N) and ZREVRANGE O(K) are the industry standard
• When presenting SortedList, explicitly state the "remove old, add new" pattern for score updates
• Tie to real-world use: explain that competitive sites like LeetCode use similar ranked list structures for contest leaderboards

Follow-up Questions#

• How would you support millions of concurrent players with real-time updates? (Redis ZADD with sorted sets, read from ZREVRANGE)
• How would you handle ties in ranking? (Add player ID as a tie-breaker in the sort key)
• How would you support topByRegion(K, region) queries? (Separate leaderboard per region, or composite key with region prefix)
• What if scores could decrease as well as increase? (SortedList with remove-and-reinsert handles this; heapq does not support decreases without rebuild)
• How would you display a player's current rank, not just the top K? (Binary search on SortedList for rank position)

Key Takeaways#

• A hashmap of player scores with heapq.nlargest(K, values) is the simplest correct solution: O(N log K) per top query
• For high-frequency top queries, use a sorted container (Python SortedList) for O(log N) updates and O(K) queries
• reset sets score to 0 and must update the sorted container by removing the old value and adding 0 (or simply removing)
• When using a sorted structure, always remove the old score before inserting the updated score
• The production solution for leaderboards at scale is Redis sorted sets: ZADD is O(log N), ZREVRANGE O(K)
• heapq.nlargest(K, iterable) is more efficient than sorting the full list when K is much smaller than N
• Always initialise scores to 0 with defaultdict(int) to avoid KeyError on first addScore for a new player