Solution For Design A Leaderboard

Problem Statement:

We need to design a Leaderboard class, which will have the following methods:

• void addScore(int playerId, int score): Insert a score into the leaderboard of a player.
• int top(int K): Return the score sum of the top K players.
• void reset(int playerId): Reset the score of a player. It is guaranteed that the player was added to the leaderboard before calling this function.

Solution:

We will solve this problem using a HashMap and a PriorityQueue. The HashMap will store the playerId and the corresponding score, while the PriorityQueue will store the top K players’ scores. Whenever we call the top(K) method, we will retrieve the top K players scores from the PriorityQueue, and sum them up to return the answer.

In the addScore() method, we will update the player’s score in the HashMap. We will add the player’s score if the player is not present in the HashMap, and update the score if the player is already present. After updating the score, we will remove the player’s score from the PriorityQueue as well, because we need to re-calculate the top K scores.

In the reset() method, we will remove the player’s score from the HashMap and PriorityQueue because we need to recalculate the top K scores.

Code:

Let’s start by creating a Player class with playerId and score attributes:

“`
class Player{
int playerId;
int score;

public Player(int playerId, int score){
    this.playerId = playerId;
    this.score = score;
}

}
“`

Now, let’s implement the Leaderboard class:

“`
class Leaderboard {
Map scores;
PriorityQueue topK;

public Leaderboard() {
    scores = new HashMap<>();
    topK = new PriorityQueue<>((a, b) -> b - a); // Max heap
}

public void addScore(int playerId, int score) {
    int oldScore = scores.getOrDefault(playerId, 0);
    int newScore = oldScore + score;
    scores.put(playerId, newScore);

    topK.remove(oldScore); // Remove the old score
    topK.offer(newScore); // Add the new score
}

public int top(int K) {
    int sum = 0;
    for(int i=0; i<K; i++){
        if(topK.isEmpty()) break;
        sum += topK.poll();
    }
    return sum;
}

public void reset(int playerId) {
    int score = scores.get(playerId);
    scores.remove(playerId);
    topK.remove(score);
}

}
“`

The time complexity of this implementation will be O(log N) for addScore() and top() methods and O(1) for reset() method. The space complexity will be O(N), where N is the number of players.

Step by Step Implementation For Design A Leaderboard

/*

Design a Leaderboard class, which has following functions:

addScore(playerId, score): Update the leaderboard by adding score to the given player's record. If there is no record for the player, create one with the given player's id and score.

top(K): Return the score sum of the top K players.

reset(playerId): Reset the score of the player with the given id to 0 (in other words, erase it from the leaderboard). It is guaranteed that the player was added to the leaderboard before calling this function.

Initially, the leaderboard is empty.

 

Example 1:

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 leaderboard = new Leaderboard ();
leaderboard.addScore(1,73);   // leaderboard = [[1,73]];
leaderboard.addScore(2,56);   // leaderboard = [[1,73],[2,56]];
leaderboard.addScore(3,39);   // leaderboard = [[1,73],[2,56],[3,39]];
leaderboard.addScore(4,51);   // leaderboard = [[1,73],[2,56],[3,39],[4,51]];
leaderboard.addScore(5,4);    // leaderboard = [[1,73],[2,56],[3,39],[4,51],[5,4]];
leaderboard.top(1);           // returns 73;
leaderboard.reset(1);         // leaderboard = [[2,56],[3,39],[4,51],[5,4]];
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);           // returns 141 = 51 + 51 + 39;
 

Constraints:

1 <= playerId, K <= 10000
It's guaranteed that K is less than or equal to the current number of players.
1 <= score <= 100
There will be at most 1000 function calls.
*/

class Leaderboard {
    
    Map map;
    
    public Leaderboard() {
        map = new HashMap<>();
    }
    
    public void addScore(int playerId, int score) {
        if(map.containsKey(playerId)) {
            map.put(playerId, map.get(playerId) + score);
        } else {
            map.put(playerId, score);
        }
    }
    
    public int top(int K) {
        PriorityQueue pq = new PriorityQueue<>();
        for(int key : map.keySet()) {
            pq.add(map.get(key));
        }
        int sum = 0;
        for(int i = 0; i < K; i++) {
            sum += pq.poll();
        }
        return sum;
    }
    
    public void reset(int playerId) {
        map.put(playerId, 0);
    }
}

/**
 * Your Leaderboard object will be instantiated and called as such:
 * Leaderboard obj = new Leaderboard();
 * obj.addScore(playerId,score);
 * int param_2 = obj.top(K);
 * obj.reset(playerId);
 */

This problem can be solved using a min heap. We can keep track of the top K players in the heap, and every time a new player's score is added, we can compare it to the minimum score in the heap. If the new score is higher, we can remove the minimum score from the heap and add the new score. In this way, we can always maintain a heap of size K with the top K scores.

var Leaderboard = function() {
    // create a map to store the players and their scores
    this.players = new Map();
};

/** 
 * @param {number} playerId 
 * @param {number} score
 * @return {void}
 */
Leaderboard.prototype.addScore = function(playerId, score) {
    // if the player is not in the map, add them with a score of 0
    if (!this.players.has(playerId)) {
        this.players.set(playerId, 0);
    }
    
    // update the player's score
    this.players.set(playerId, this.players.get(playerId) + score);
};

/**
 * @param {number} K
 * @return {number[]}
 */
Leaderboard.prototype.top = function(K) {
    // create an array to store the top K players
    const topPlayers = [];
    
    // iterate through the map and push the players into the array in order from highest to lowest score
    for (const [player, score] of this.players) {
        topPlayers.push({ player, score });
    }
    
    topPlayers.sort((a, b) => b.score - a.score);
    
    // return an array of the player ids
    return topPlayers.slice(0, K).map(player => player.player);
};

/** 
 * @param {number} playerId
 * @return {void}
 */
Leaderboard.prototype.reset = function(playerId) {
    // remove the player from the map
    this.players.delete(playerId);
};

#include 
#include 
#include 
#include 

using System; 
using System.Collections.Generic; 

public class Leaderboard { 

// create a dictionary to store players and their scores 
Dictionary dictionary = new Dictionary(); 

// add a new score for a player 
public void AddScore(int playerId, int score) { 

// if the player is not in the dictionary, add them 
if(!dictionary.ContainsKey(playerId)) { 
dictionary.Add(playerId, score); 
} 
// otherwise, update their score 
else { 
dictionary[playerId] = score; 
} 
} 

// get the current top score 
public int GetCurrentTopScore() { 

// set the default to the lowest possible score 
int currentTopScore = Int32.MinValue; 

// loop through all the players in the dictionary 
foreach(KeyValuePair player in dictionary) { 

// if the player's score is higher than the current top score, update it 
if(player.Value > currentTopScore) { 
currentTopScore = player.Value; 
} 
} 

// return the current top score 
return currentTopScore; 
} 
}