Design A Leaderboard

medium design hash map sorting

Problem

Design a Leaderboard class supporting three operations. addScore(playerId, score) adds score to the player's total (creating the player at 0 if new). top(K) returns the sum of the K highest player scores. reset(playerId) sets the player's score back to 0. The leaderboard starts empty.

InputaddScore(1,73) addScore(2,56) addScore(3,39) top(2)

Output129

Scores are {1:73, 2:56, 3:39}. The two highest are 73 and 56, summing to 129.

operations (one per token: add:id:score, reset:id, top:k)

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(sorted(self.scores.values(), reverse=True)[:K])

    def reset(self, playerId):
        self.scores[playerId] = 0

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

class Leaderboard {
    private Map<Integer, Integer> scores = new HashMap<>();

    public void addScore(int playerId, int score) {
        scores.merge(playerId, score, Integer::sum);
    }

    public int top(int K) {
        List<Integer> vals = new ArrayList<>(scores.values());
        vals.sort(Collections.reverseOrder());
        int sum = 0;
        for (int i = 0; i < K && i < vals.size(); i++) sum += vals.get(i);
        return sum;
    }

    public void reset(int playerId) {
        scores.put(playerId, 0);
    }
}

class Leaderboard {
    unordered_map<int, int> scores;
public:
    void addScore(int playerId, int score) {
        scores[playerId] += score;
    }
    int top(int K) {
        vector<int> vals;
        for (auto& p : scores) vals.push_back(p.second);
        sort(vals.rbegin(), vals.rend());
        int sum = 0;
        for (int i = 0; i < K && i < (int)vals.size(); i++) sum += vals[i];
        return sum;
    }
    void reset(int playerId) {
        scores[playerId] = 0;
    }
};

Explanation

This is a deliberately simple design: a single hash map from playerId to their running total score. All three operations are easy reads or writes on that one map.

addScore(playerId, score) adds to the player's existing total, defaulting to 0 for a new player — that is exactly what self.scores.get(playerId, 0) + score does. reset(playerId) simply sets the stored score back to 0.

top(K) is where the work happens: we take all the score values, sort them from high to low with sorted(..., reverse=True), slice off the first K, and sum them. This is O(n log n) per call because of the sort, while add and reset stay O(1).

Example: after addScore(1,73), addScore(2,56), addScore(3,39), the map is {1:73, 2:56, 3:39}. top(2) sorts to [73, 56, 39], takes the first two, and returns 73 + 56 = 129.

Time: O(n log n) per top(K), O(1) per add/reset Space: O(n)