Initially, the leaderboard is empty.

Example:

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;

Solution:

This is very good real-world problem to ask in an interview to assess someone's deep knowledge and understanding of data structures.

As with all other problems in our Low Level Design course, for this one too we come up with whatever solution comes to our mind first, and then show you how we logically go on optimizing our solution and land our final most efficient design and implementation.

If you are a beginner or an intermediate, after reading the problem statement it may seem like there is a lot to handle, and you might start think that it is so overwhelming to think about all the data structures needed to accomplish everything given in the requirements.

But as with every other problems, we would see here how breaking down the requirements into small pieces would help us conquer the problem. What we need here is systematic and logical thinking.

So let's analyze the requirements first. Think as if you are the Lead Software Engineer in a leading Games Development company and your task is to design and build the internals of generic Leadership Board that could be reused in various different games. How would you go about it ? You would talk to the business and gather the requirements. In our case we already have the requirements in the form of the given problem statement. Analyzing the requirements would be very next logical step and that is exactly what we are going to do now:

1. We need keep a list of all the players and their scores.
2. We need to (efficiently) keep track of top K scores.
3. We need the capability to reset score of any given player.
   This also means that we should be able to efficiently access score of any given player.

The above discussion is a very good start. Now let's start with a simple solution, and as always we will go on optimizing it. If you are preparing for interviews, feel free to directly jump on the most optimized solution that you can think of since you would have limited time, but quickly mentioning other solutions and discussing their trade-offs, pros and cons (given you have time) is never a bad idea.

#1. Our first solution:

For a very simple brute force solution the first thing that comes to mind is using a hash map. We would be able to accomplish everything mentioned in our requirements, even though it might not be the most efficient solution. I have discussed the algorithm (along with complexity analysis) in the inline comments in the code below:

Code Implementation:

Java:

class Leaderboard {
    private Map<Integer, Integer> scores;
    public Leaderboard() {
        scores = new HashMap<>();
    }
    
    public void addScore(int playerId, int score) { // Time Complexity: O(1)
        // if the player is not already present, initialize
        // the player's score to 0
        if (!scores.containsKey(playerId)) { // O(1)
            scores.put(playerId, 0); // O(1)
        }
        // add the given score to the current score of the player
        scores.put(playerId, scores.get(playerId) + score); // O(1)
    }
    
    public int top(int K) { // Time Complexity: O(NlogN) + O(K) = O(NlogN) where N = total number of players
        // we have all the scores in our hash map.  how do we get the top K scores ?
        // Simple. sort all the values contained in the map and return the 
        // max K elements from the sorted scores.
        // We would sort in descending order and grab the first K entries
        List<Integer> values = new ArrayList<Integer>(scores.values());
        Collections.sort(values, Collections.reverseOrder()); // O(NlogN)
        
        int sum = 0;
        for (int i = 0; i < K; i++) { // O(K)
            sum += values.get(i);            
        }
        return sum;
    }
    
    public void reset(int playerId) { // Time Complexity: O(1)
        // update score of given player to zero
        scores.put(playerId, 0); // O(1)
    }
    
    // Space Complexity: O(N), where N = total number  of players. We are keeping scores of all the players in the map.
}

    

Python:

class Leaderboard:
    def __init__(self):
        self._scores = {}

    def addScore(self, playerId, score):
        if playerId not in self._scores.keys():
            self._scores[playerId] = 0

        self._scores[playerId] = self._scores[playerId] + score

    def top(self, K):
        values = list(self._scores.values())
        sorted(values, reverse=True)
        sumi = 0
        for i in range(0, K):
            sumi += values[i]
        return sumi

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

    

#2. Optimize top(int K) method implementation:

Let's revisit our requirements to see if we could find a way to optimize the above solution:

1. We need keep a list of all the players and their scores.
2. We need to (efficiently) keep track of top K scores.
3. We need the capability to reset score of any given player.
   This also means that we should be able to efficiently access score of any given player.

Let's double click on the second requirement: keeping track of top K scores. Min heap automatically comes to mind as a very efficient data structure whenever something like "finding top K values" is what we are trying to accomplish. This is true for this problem as well.

We already have O(1) addScore(..) and reset(..) implementation and that is the best we can get. So let's concentrate on improving the performance of top(int K) method implementation.

We would optimize our solution above by using our knowledge that Min heap is a very efficient data structure whenever something like "finding top K values" is what we are trying to accomplish. Using heap or priority queue almost always beats the performance we get from using sorting.

Using the knowledge above let's see what we can do: in the top(int K) method we can use heap or priority queue instead of sorting. Let's see how that optimizes the time complexity:

Code Implementation:

Java:

class Leaderboard {
    
    private Map<Integer, Integer> scores;
    public Leaderboard() {
        scores = new HashMap<>();
    }
    
    public void addScore(int playerId, int score) { 
        if (!scores.containsKey(playerId)) { 
            scores.put(playerId, 0);
        }
        scores.put(playerId, scores.get(playerId) + score); 
    }
    
    public int top(int K) {  
        // We are taking a min-heap containing values of the hash map. 
        PriorityQueue<Integer> minHeap = new PriorityQueue<>((a, b) -> a - b);
        
        for (int score : scores.values()) { // O(N)
            minHeap.offer(score);
            if (minHeap.size() > K) {
                minHeap.poll(); // extract min because we are interested in Top elements
                                // O(logK) 
            }
        } // Overall time complexity to execute this foreach loop: O(NlogK)
        
        int sum = 0;
        for (int a : minHeap) { // O(K)
            sum += a;
        }
        return sum;

    // Time complexity: O(K) + O(NlogK) = O(NlogK)
    }
        
    
    public void reset(int playerId) { // Time Complexity: O(1)
        // update score of given player to zero
        scores.put(playerId, 0); // O(1)
    }
    
    /*
    Space Complexity: O(N + K), where N = total number  of players.
    We are keeping scores of all the players in the map.
    O(K) is used by the heap in top(K) method.
    */
}

Python:

import queue


class Leaderboard:
    def __init__(self):
        self._scores = {}

    def addScore(self, playerId, score):
        if playerId not in self._scores.keys():
            self._scores[playerId] = 0
        self._scores[playerId] = self._scores[playerId] + score

    def top(self, K):
        x,y = lambda a, b: a - b
        minHeap = queue.PriorityQueue(x)
        for score in self._scores.values():
            minHeap.put(score)
            if minHeap.qsize() > K:
                minHeap.task_done()
        sum = 0
        for a in minHeap.get():
            sum += a
        return sum

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

    

So we were able able to optimize the performance of top(K) operation from O(NlogN) to O(NlogK), which is definitely a big improvement in performnace.
Let's see if we can do even better.

#3. Balanced Binary Search Tree based efficient solution that is used in real-world game leaderboard implementation on Production:

This solution will show your deep understanding of basic data structures like Binary Search Tree. We know that Binary Search Tree is a great fit to store elements as per their rank since for every node A all nodes with key less than or equal to the key of node A are on in its left subtree and all nodes with key greater than key of node A are in the right subtree of node A. These are discussed in great details in the Binary Search Tree chapter which is part of our Algorithms course. Since Leaderboard is all about displaying the players according to their ranks, balanced binary search tree is a great fit for building solution for this problem, specifically for finding top K players according to their rank (higher the score, better the rank).

The main objective we are trying to achieve is to improve the performance of the top(K) operation. If we can keep the scores of the players in descending order then it would be very easy for us to get top K scores in a very efficient way. To achieve that what we will do is store all scores in a balanced binary search tree in the reverse order of natural order (so that the BST stores scores in descending order). We would also store how many players have that score in the BST nodes. So in every BST node we would store a (key, value) pair, where score will be the key and the number of players who have gotten that score will be the corresponding value. This balanced BST would be used particularly to optimize top(K) operation.

In addition, we will have a map to store the leaderboard. The map will contain player ids and their corresponding scores.

In a balanced binary search tree like Red Black tree, amortized time complexity for getting the first k elements in inorder traversal would be O(K). This is discussed in more details in the inline comments in the top(K) implementation in the code below. This is a huge improvement in performance for top(K) operation. However, we are making a trade-off of degrading the performance of addScore(..) and reset(..) from O(1) to O(logN) since insertion and deletion operation on a balanced binary search tree are both O(logN) operations, as we will see in the code below.

In cae you are wondering why we are interested only in using Balanced BST and not just any BST, the answer to that is the worst case time complexity for BST operations is O(N) but for BALANCED BST the worst case time complexity of the BST operations are O(logN).

Code Implementation with Detailed Algorithmic Discussion:

Java:

// Solution using Balanced Binary Search Tree
// Time Complexity:
// addScore, reset: O(logN)
// top(K): O(K)
// Space Complexityt: O(N)
class Leaderboard {
    
    TreeMap<Integer, Integer> sortedScores; // type needs to be TreeMap and not just Map interface, since we 
                                  // cannot just use any implementation of Map and need to use TreeMap 
                                  // only as we are looking for Balanced BST (balanced binary search tree)
                                  //
                                  // this map basically keeps all the scores in descending order along
                                  // with the number of players that currently have that score
                                  //
                                  // we have this data structure entirely to optimize top(K) method, it has no other purpose.
    Map<Integer, Integer> leaderboard; // map to keep playerId and their score, i.e, playerId -> score
    
    public Leaderboard() {
        sortedScores = new TreeMap<>(Collections.reverseOrder()); // sort keys in descending order
        leaderboard = new HashMap<Integer, Integer>();
    }
    
    public void addScore(int playerId, int score) { 
        // two scenarios we need to handle:
        // scenario #1: this player is not present in our leaderboard yet:
        // in this case (1) add the player in the leaderboard and (2) increment 
        // the value associated with the score by 1 in the sortedScores map
        //
        // scenario #2: the player is already present in the leaderboard:
        // (1) update the score in the leaderboard
        // and (2) decrement the value associated with old score by 1
        // and increment the value associated with updated score by 1 in the sortedScores map
        //
        // from the above discussion a good and experienced coder would come up with
        // below concise and clean code.
        
        int newScore = leaderboard.getOrDefault(playerId, 0) + score; //O(1) amortized
        
        leaderboard.put(playerId, newScore);  // applies to both scenario #1 and #2
                                              // O(1) amortized
        sortedScores.put(newScore, sortedScores.getOrDefault(newScore, 0) + 1); // applies to both scenario #1 and #2
                                                                                // O(logN)
        
        if (newScore != score) { // updatedScore == score only when the player's previous score 
            // was 0 i.e, NOT in leaderboard. So updatedScore != score means 
            // this player was already present in the leaderboard
            int oldScore = newScore - score;
            sortedScores.put(oldScore, sortedScores.get(oldScore) - 1); // O(logN)
        } 
    }   Overall time complexity for addScore method = O(logN), where N = total number of players
    
    public int top(int K) {
        // Recall: inorder traversal of a BST gives us the elements in the order.
        // If a BST has [5,2,1,3,4] then the inorder traversal would
        // give 1 -> 2 -> 3 -> 4 -> 5 if we go by natural ordering.
        // In our case since we are interested in getting elements in 
        // descending order (since we are interested in top K scores)
        // we do not consider natural ordering, rather we consider Collections.reverseOrder()
        //
        // So in our case we do inorder traversal of the balanced BST and
        // sum up the scores of the first K players. The
        // BST implementation we have here sorts the player in the descending order
        // of their score, since score is the key of the BST nodes.
        //
        // In TreeMap we would achieve this just by iterating over it from the first 
        // entry making sure we do not sum up scores of more than K players
        // as we encounter them.

        int remaining = K;
        int sum = 0;
        
        // In-order traversal over the scores in the TreeMap
        for (Map.Entry<Integer, Integer> entry: sortedScores.entrySet()) { // amortized complexity of getting next node in an inorder traversal
                                // in red-black tree is O(1). TreeMap is implemented using Red-Black tree which is a balanced binary search tree. 
            int score = entry.getKey(); // getting key from entry is O(1)
            int numberOfPlayers = entry.getValue(); // getting value from an entry is O(1)
            if (remaining >= numberOfPlayers) {
                sum += score * numberOfPlayers;
            } else {
                sum += score * remaining;
            }
            remaining -= numberOfPlayers;
            if (remaining <= 0) {
                break;
            }
        } // Overall time complexity of this loop: O(K)

        return sum;

    } // Overall time complexity of top(K) method is O(K)
    
    public void reset(int playerId) {
        int score = leaderboard.get(playerId); // according to problem statement playerId is guaranteed to be present in the leaderboard if reset operation is being done for playerId
        
        // remove the player from leaderboard
        leaderboard.remove(playerId); // O(1) amortized
        
        // now that we have reset this player
        // remove this player from the sorted scores map by 
        // decrementing the number of players with the score same as this player's.
        //
        // if numberOfPlayer for this score goes down to zero, remove the score from the balanced BST altogether
        // as after this reset() operation there is no more player with this same score.
        int numberOfPlayersWithThisCore = sortedScores.get(score); // O(logN)
        if (numberOfPlayersWithThisCore == 1) { // this player is the only player with the score he/she has
            sortedScores.remove(score); // O(logN)
        } else {
            sortedScores.put(score, sortedScores.get(score) - 1); // O(logN)
        }
    } // Overall time complexity of reset operation = O(logN), where N = total number of players
}

Python:

class Leaderboard:
    def __init__(self):
        self.sortedScores = {}
        self.leaderboard = {}

    def addScore(self, playerId, score):
        newScore = 0
        if playerId in self.leaderboard:
            newScore = self.leaderboard[playerId]
        newScore = newScore + score
        self.leaderboard[playerId] = newScore
        value = 0
        if newScore in self.sortedScores:
            value = self.sortedScores[newScore]
        self.sortedScores[newScore] = value + 1
        if newScore != score:
            oldScore = newScore - score
            self.sortedScores[oldScore] = self.sortedScores[oldScore] - 1

    def top(self, K):
        remaining = K
        sum = 0
        for entry in self.sortedScores:
            score = self.sortedScores[entry]
            numberOfPlayers = score
            if remaining >= numberOfPlayers:
                sum += score * numberOfPlayers
            else:
                sum += score * remaining
            remaining -= numberOfPlayers
            if remaining <= 0:
                break
        return sum

    def reset(self, playerId):
        score = self.leaderboard[playerId]
        self.leaderboard.pop(playerId)
        numberOfPlayersWithThisCore = self.sortedScores[score]
        if numberOfPlayersWithThisCore == 1:
            self.sortedScores.pop(score)
        else:
            self.sortedScores[score] = self.sortedScores[score] - 1

    

This is overall a better solution since top(K) operation plays an important role in designing the Leaderboard and would be frequently used to display the Leaderboard in a real-world Game scenario. Leaderboard is all about displaying the top K players according to their ranks. So, even though we are making a trade-off of having O(logN) implementation of reset and addScore operations instead of O(1) implementations that we had in our first two solutions, this implementation is far more practical and more efficient solution in a real-world situation for Game Development. I hope you learned a lot from this chapter!