Design A Leaderboard - Solution & Explanation

Problem Overview: Design a leaderboard system that tracks player scores. The API supports addScore(playerId, score), top(K) to return the sum of the top K scores, and reset(playerId). The challenge is maintaining fast updates while still retrieving the highest K scores efficiently.

Approach 1: Hash Map + Sorting on Query (add: O(1), top: O(n log n), reset: O(1), space: O(n))

Store each player's score in a hash map where the key is playerId and the value is the cumulative score. addScore simply updates the map entry in constant time. For top(K), extract all scores, sort them in descending order, and sum the first K elements. reset sets the player’s score back to zero or removes the entry. This approach is easy to implement using a hash table, but the repeated sorting step makes top(K) expensive when the number of players grows.

Approach 2: Hash Map + Ordered List (add/reset: O(log n), top: O(K), space: O(n))

Maintain two structures: a hash map for fast player lookups and an ordered list (or balanced tree) containing all scores in sorted order. When addScore updates a player's score, remove the old score from the ordered structure and insert the updated score at the correct position using binary search or a tree-based structure. The top(K) operation becomes efficient: iterate over the largest K values directly and sum them in O(K). reset removes the player’s score from the ordered structure and clears it in the map. This approach combines hash table lookups with efficient sorting-style ordering to avoid repeated full sorts.

Recommended for interviews: The hash map + ordered list approach is the expected design. The brute-force sorting method shows you understand the problem, but interviewers look for incremental ordering that avoids sorting the entire dataset every time top(K) runs. Maintaining a sorted structure demonstrates stronger system design and data structure selection.