Design A Leaderboard Leetcode Solution

Difficulty Level Medium
Frequently asked in Amazon Bloomberg Facebook Google Microsoft Twitch Twitter Uber Wayfair
Design Hashing SortingsViews 47

System design interview questions can be so open-ended, that it's too hard to know the right way to prepare. Now I am able to crack the design rounds of Amazon, Microsoft, and Adobe after buying this book. Daily revise one design question and I promise you can crack the design round.

Problem Statement

The Design A Leaderboard LeetCode Solution – “Design A Leaderboard” asks you to complete 3 functions:

  • addScore(playerId, score): Update the leaderboard by adding a score to the given player’s score. If there doesn’t exist any player, add such id on the leaderboard.
  • top(K): Return the top sum of K players
  • reset(playerId): Reset the score of the given player ID.

Example:

Input:  ["Leaderboard","addScore","addScore","addScore","addScore","addScore","top","reset","reset","addScore","top"]
        [[],[1,73],[2,56],[3,39],[4,51],[5,4],[1],[1],[2],[2,51],[3]]
Output: [null,null,null,null,null,null,73,null,null,null,141]

Explanation:

  • Leaderboard = new Leaderboard();
  • leaderboard.addScore(1, 73), leaderboard.addScore(2, 56), leaderboard.addScore(3, 39), leaderboard.addScore(4, 51), leaderboard.addScore(5, 4). Leaderboard = [[1, 73], [2, 56], [3, 39], [4, 51], [5, 4]].
  • leaderboard.top(1): 73
  • leaderboard.reset(1), leaderboard.reset(2). Leaderboard = [[3, 39], [4, 51], [5, 4]].
  • leaderboard.addScore(2, 51). Leaderboard = [[2, 51], [3, 39], [4, 51], [5, 4]].
  • leaderboard.top(3): 141 [51 + 51 + 39]

Approach

Idea:

  1. The main idea to solve this problem is to use Hashset or PriorityQueue.
  2. Maintain a hashset that will store the score of each unique Player ID, also, use multiset to store all scores.
  3. For a reset operation, erase the occurrence of the player ID from the hashset. Also remove it’s occurrence from the hashset, It takes logarithmic time to perform the operation.
  4. For top() operation, iterate the multiset of scores and add up all the top k scores to your answer.
  5. Multiset will store scores in non-increasing order.
  6. For addScore() operation,  introduce the entry into hashset if the hashset doesn’t contain the player ID and insert score into the multiset.
  7. Insertion and Deletion from multiset and hashset takes logarithmic time to perform the operation.

Code

Design A Leaderboard Leetcode C++ Solution:

class Leaderboard {
public:
    map <int, int> playerScore;
    multiset <int, greater <int>> s;
    
    Leaderboard(){
        s.clear();
        playerScore.clear();
    }
    
    void addScore(int playerId, int score) {
        if(!playerScore.count(playerId)){
            playerScore[playerId] = 0;
        }
        else{
            s.erase(s.find(playerScore[playerId]));
        }
        
        playerScore[playerId] += score;
        s.insert(playerScore[playerId]);
    }
    
    int top(int K) {
        int ans = 0;
        
        for(auto& x : s){
            if(K == 0){
                break;
            }
            
            K--;
            ans += x;
        }
        
        return ans;
    }
    
    void reset(int playerId) {
        s.erase(s.find(playerScore[playerId]));
        playerScore.erase(playerId);
    }
};

Design A Leaderboard Leetcode Java Solution:

class Leaderboard {
    Map<Integer, Integer> map;
    TreeMap<Integer, Integer> sorted;
    public Leaderboard() {
        map = new HashMap<>();
        sorted = new TreeMap<>(Collections.reverseOrder());
    }
    
    public void addScore(int playerId, int score) {
        if (!map.containsKey(playerId)) {
            map.put(playerId, score);
            sorted.put(score, sorted.getOrDefault(score, 0) + 1);
        } else {
            int preScore = map.get(playerId);
            sorted.put(preScore, sorted.get(preScore) - 1);
            if (sorted.get(preScore) == 0) {
                sorted.remove(preScore);
            }
            int newScore = preScore + score;
            map.put(playerId, newScore);
            sorted.put(newScore, sorted.getOrDefault(newScore, 0) + 1);
        }
    }
    
    public int top(int K) {
        int count = 0;
        int sum = 0;
        for (int key : sorted.keySet()) {
            int times = sorted.get(key);
            for (int i = 0; i < times; i++) {
                sum += key;
                count++;
                if (count == K) {
                    break;
                }
            }
            if (count == K) {
                break;
            }
        }
        return sum;
    }
    
    public void reset(int playerId) {
        int preScore = map.get(playerId);
        sorted.put(preScore, sorted.get(preScore) - 1);
        if (sorted.get(preScore) == 0) {
            sorted.remove(preScore);
        }
        map.remove(playerId);
    }
}

Complexity Analysis for Design A Leaderboard Leetcode Solution

Time Complexity

The time complexity of the addScore() and reset() function is O(logN) per call and the time complexity of the top() function is O(k) per call.

Insertion and deletion takes logarithmic time in multiset and hashset.

Space Complexity

The space complexity of the above code is O(N) since we’re maintaining map of player IDs where N is the maximum amount of players.

Crack System Design Interviews
Translate »