• Customer Support: admin@thealgorists.com
  • Feedback: We are listening to your every feedback, and taking action to constantly improve your learning experience. If you have any feedback, please use this form: https://thealgorists.com/Feedback.




Problem Statement:

Design a Leaderboard class, which has 3 functions:

addScore(playerId, score): Update the leaderboard by adding score to the given player's score. If there is no player with such id in the leaderboard, add him to the leaderboard with the given 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:

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:

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.
}

/**
 * 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);
 */
    


#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:

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.
    */
}




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 is a Premium Content.
Please subscribe to Low Level Design course to access the content.




The above content is written by:

Abhishek Dey

Abhishek Dey

A Visionary Software Engineer With A Mission To Empower Every Person & Every Organization On The Planet To Achieve More

Microsoft | University of Florida

View LinkedIn profile


If you have any feedback, please use this form: https://thealgorists.com/Feedback.




Subscribe to Our Youtube Channel

Follow Us On LinkedIn
wave