Vultr DocsLatest Content

Design A Leaderboard

Updated on 22 May, 2025
Design A Leaderboard header image

Problem Statement

The task is to design and implement a Leaderboard class which manages player scores in a dynamic format. The class should support the following functionalities:

  1. addScore(playerId, score): When this method is invoked, the score of a player identified by playerId should be increased by the specified score value. If the player does not exist in the leaderboard, they should be added with the initial score.

  2. top(K): This method should return the sum of the scores of the top K players in the leaderboard. Players are ranked based on their scores, with the highest scores being considered for the sum.

  3. reset(playerId): This functionality will reset the score of the specified player to zero, effectively removing or disregarding their score from the leaderboard. It is pre-conditioned that the player with playerId exists in the leaderboard before this method is called.

Initially, the leaderboard starts off without any players or scores.

Examples

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.

Approach and Intuition

The operations defined in this problem can be handled effectively using a combination of data structures that support dynamic insertion, deletion, and ordered data management. Here’s a conceptual breakdown of our approach:

  1. Managing Player Scores:

    • We could use a hash table (or a dictionary in Python terms), to keep track of each player's score, where the playerId is the key, and the current score is the value. This enables O(1) average time complexity for adding scores (addScore) and resetting scores (reset), because hash tables provide very efficient access using keys.

  2. Finding the Top K Scores:

    • To get the top K scores efficiently, maintaining a sorted data structure could be beneficial. However, frequent insertion might make ordinary sorting inefficient.
    • Alternatively, maintaining a max-heap (or priority queue) could be useful. Although directly using a max-heap challenges direct access (by playerId) or removing a player. An augmented tree structure or a balanced binary search tree could also be considered, which supports order statistics.

  3. Resetting a Player's Score:

    • The simplest way would be directly resetting the score in the hash table. However, for maintaining sorted order or top scores accurately (in a heap or tree), we may need to handle the removal of scores efficiently. An auxiliary structure or logic might be required to ensure consistency between the hash table and the ordered structure. For simplicity in typical scenarios with less frequent reset operations, re-building the leaderboard from scratch post reset can occasionally be acceptable depending on frequency and leaderboard size considerations.

The considerations in implementation would vastly depend on the specifics of usage patterns (e.g., frequency of score additions vs top K calculations), but would likely rely heavily on a combination of hash tables for direct access by playerId and a heap or self-balancing tree for maintaining sorted order of the scores.

Solutions

  • Java
  • Python
java 
class Scoreboard {

    Map<Integer, Integer> playerScores;
    TreeMap<Integer, Integer> rankedScores;
    
    public Scoreboard() {
        this.playerScores = new HashMap<Integer, Integer>();
        this.rankedScores = new TreeMap<>(Collections.reverseOrder());
    }
    
    public void recordScore(int playerId, int score) {
        
        if (!this.playerScores.containsKey(playerId)) {
            playerScores.put(playerId, score);
            rankedScores.put(score, rankedScores.getOrDefault(score, 0) + 1);
        } else {
            int currentScore = playerScores.get(playerId);
            int numberOfPlayers = rankedScores.get(currentScore);
            
            if (numberOfPlayers == 1) {
                rankedScores.remove(currentScore);
            } else {
                rankedScores.put(currentScore, numberOfPlayers - 1);
            }
            
            int updatedScore = currentScore + score;
            playerScores.put(playerId, updatedScore);
            rankedScores.put(updatedScore, rankedScores.getOrDefault(updatedScore, 0) + 1);
        }
    }
    
    public int top(int K) {
        int totalScores = 0;
        int scoreSum = 0;
        
        for (Map.Entry<Integer, Integer> entry : rankedScores.entrySet()) {
            int count = entry.getValue();
            int score = entry.getKey();
            
            for (int i = 0; i < count; i++) {
                scoreSum += score;
                totalScores++;
                
                if (totalScores == K) {
                    break;
                }
            }
            
            if (totalScores == K) {
                break;
            }
        }
        
        return scoreSum;
    }
    
    public void reset(int playerId) {
        int scoreToRemove = playerScores.get(playerId);
        rankedScores.put(scoreToRemove, rankedScores.get(scoreToRemove) - 1);
        if (rankedScores.get(scoreToRemove) == 0) {
            rankedScores.remove(scoreToRemove);
        }
        
        playerScores.remove(playerId);
    }
}

The Java solution outlines the design and functionality of a Scoreboard class to manage player scores and rankings effectively. Here's a breakdown of the core functionalities of this system:

  • Initialization:

    • Initialize playerScores using a HashMap to store each player's cumulative score.
    • Use a TreeMap, rankedScores, to sort scores in descending order and to maintain the count of each score.

  • Recording Scores:

    • Implement the recordScore() method to add or update scores for players:
      • If a new player ID is encountered, add the initial score to both playerScores and rankedScores. In rankedScores, increase the count of that score.
      • For existing player IDs, update both maps by adjusting the existing values and ensuring that rankedScores remains accurate, either by decrementing a score's count or removing it if its count hits zero before adding the new cumulative score.

  • Fetching Top Scores:

    • The top(int K) method retrieves the sum of the top K scores:
      • Traverse entries in rankedScores, which are ordered from highest to lowest.
      • Keep track of scores added and ensure to stop once K scores have been accounted for.

  • Resetting Scores:

    • The reset(int playerId) method removes a player's score:
      • First, reduce the count of the player’s score in rankedScores. If the count becomes zero, remove the score from rankedScores.
      • Remove the player's ID and score from playerScores.

This system ensures efficient score updating and retrieval, leveraging the properties of HashMap for quick lookups and TreeMap to maintain sorted scores, facilitating rapid access to top scores.

python 
from sortedcontainers import SortedDict

class ScoreTracker:

    def __init__(self):
        self.player_scores = {}
        self.score_board = SortedDict()

    def record_score(self, player_id: int, score: int) -> None:
        if player_id not in self.player_scores:
            self.player_scores[player_id] = score
            self.score_board[-score] = self.score_board.get(-score, 0) + 1
        else:
            old_score = self.player_scores[player_id]
            current_count = self.score_board.get(-old_score)
            if current_count == 1:
                del self.score_board[-old_score]
            else:
                self.score_board[-old_score] = current_count - 1

            new_score = old_score + score
            self.player_scores[player_id] = new_score
            self.score_board[-new_score] = self.score_board.get(-new_score, 0) + 1

    def top_k_scores(self, K: int) -> int:
        counter, sum_scores = 0, 0

        for score_key, count_value in self.score_board.items():
            for _ in range(count_value):
                sum_scores += -score_key
                counter += 1

                if counter == K:
                    break

            if counter == K:
                break

        return sum_scores

    def reset_player(self, player_id: int) -> None:
        player_old_score = self.player_scores[player_id]
        if self.score_board[-player_old_score] == 1:
            del self.score_board[-player_old_score]
        else:
            self.score_board[-player_old_score] -= 1
        del self.player_scores[player_id]

The code defines a Python class ScoreTracker for managing a leaderboard system, primarily aimed at tracking player scores and accessing top scores efficiently.

Overview of ScoreTracker operations:

  • Initialization: The __init__ method sets up essential structures. player_scores dictionary to keep track of each player's cumulative score, and score_board, a SortedDict from the sortedcontainers module, to maintain scores in a way that facilitates efficient retrieval of the highest scores.

  • Recording Scores: The record_score method updates scores for a player. If a new player, their score is added; if existing, their old score is adjusted. The scores are kept in score_board as keys, representing aggregate occurrences of each score (for faster top-k lookup).

  • Retrieve Top Scores: top_k_scores computes the sum of the top k scores. It iterates over the scores from highest to lowest, maintaining a running sum until k scores are considered.

  • Resetting a Player: The reset_player method removes a player's score from the system. This involves altering or removing their score from score_board and deleting them from player_scores.

Key Functionalities:

  • Efficient score adjustment and top score retrieval using SortedDict, which keeps the scores sorted in real-time for fast maximum score access.
  • Flexibility to add, update, and reset player scores dynamically.

This solution effectively uses a combination of a dictionary for direct access and manipulation of player scores, paired with a sorted data structure for sorted order maintenance and quick max-score computations. This implementation provides a balance between efficiency (via sorted data access) and flexibility (allowing for dynamic score updates and player resets), which makes it suitable for real-time leaderboard management systems.

Comments

No comments yet.