Design A Leaderboard

Medium

Asked by:

+1

12 views

Topics:

ArraysGreedy AlgorithmsDesign

Design a leaderboard with the following functions:

addScore(playerId, score): Record the player's score to the leaderboard. If the player already exists on the leaderboard, add the new score to the player's existing score.
top(K): Return the score sum of the top K players.
reset(playerId): Reset the player's score to 0. If the player does not exist, do nothing.

Implement the Leaderboard class:

Leaderboard() Initializes the object of this class.
void addScore(int playerId, int score) Adds score to the given playerId.
int top(int K) Returns the score sum of the top K players.
void reset(int playerId) Resets the score of the player with the given playerId to 0.

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, 30], [2]]
Output
[null, null, null, null, null, null, 73, null, null, null, 83]

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

Constraints:

1 <= playerId, K <= 10⁴
It is guaranteed that K is less than or equal to the current number of players.
1 <= score <= 100
At most 1000 calls will be made to each function.

Design A Leaderboard

Medium

Asked by:

12 views

Topics:

ArraysGreedy AlgorithmsDesign

Design a leaderboard with the following functions:

addScore(playerId, score): Record the player's score to the leaderboard. If the player already exists on the leaderboard, add the new score to the player's existing score.
top(K): Return the score sum of the top K players.
reset(playerId): Reset the player's score to 0. If the player does not exist, do nothing.

Implement the Leaderboard class:

Leaderboard() Initializes the object of this class.
void addScore(int playerId, int score) Adds score to the given playerId.
int top(int K) Returns the score sum of the top K players.
void reset(int playerId) Resets the score of the player with the given playerId to 0.

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, 30], [2]]
Output
[null, null, null, null, null, null, 73, null, null, null, 83]

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

Constraints:

1 <= playerId, K <= 10⁴
It is guaranteed that K is less than or equal to the current number of players.
1 <= score <= 100
At most 1000 calls will be made to each function.

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What are the maximum possible values for `playerId` and `score`? Are they limited to a specific range?
What should I return if `k` is greater than the number of players in the leaderboard?
If a player already exists, does the `addScore` function overwrite the previous score, or should it be handled differently (e.g., throw an error)?
Can I assume that the `playerId` is always valid and not null or empty?
Is the leaderboard expected to handle a very large number of players and score updates, and should I optimize for memory usage?

Brute Force Solution

Approach

For the Leaderboard problem, the brute force approach is all about trying every possible combination of updates and scores. We will keep track of everything, no matter how inefficient. This guarantees that we will find the correct result, even if it takes a long time.

Here's how the algorithm would work step-by-step:

When a player's score is updated, we simply record that change.
To get a player's score, we add up all the score changes we have recorded for that player.
To get the leaderboard, we calculate the total score for every player.
Then, we compare each player's score to every other player's score.
Using these comparisons, we sort all the players from the highest score to the lowest score.
The resulting sorted list is our leaderboard.

Code Implementation

class Leaderboard:

    def __init__(self):
        self.score_changes = {}

    def addScore(self, playerId: int, score: int) -> None:
        if playerId not in self.score_changes:
            self.score_changes[playerId] = []
        self.score_changes[playerId].append(score)

    def top(self, k: int) -> int:
        player_scores = {}
        for playerId, score_list in self.score_changes.items():
            player_scores[playerId] = sum(score_list)

        # Sort players based on their total scores.
        sorted_players = sorted(player_scores.items(), key=lambda item: item[1], reverse=True)

        top_scores_sum = 0
        for i in range(min(k, len(sorted_players))):
            top_scores_sum += sorted_players[i][1]

        return top_scores_sum

    def reset(self, playerId: int) -> None:
        # Clearing score changes to reset score to 0
        self.score_changes[playerId] = []

# Your Leaderboard object will be instantiated and called as such:
# leaderboard = Leaderboard()
# leaderboard.addScore(playerId, score)
# leaderboard.top(K)
# leaderboard.reset(playerId)

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

O(n^2) – Updating a player's score is O(1) as it's a simple record. Getting a player's score requires summing all their score changes which could be O(m) where m is the number of updates for that player; we treat this as O(1) for the leaderboard calculation since it will be calculated for each player. Creating the leaderboard involves calculating each player's score (assumed O(1) each), and then sorting these scores. Sorting n scores using the described brute-force comparison method (comparing each score to every other score to determine order) results in roughly n*(n-1) comparisons. Thus the sorting process is O(n^2), making the overall time complexity of the leaderboard O(n^2).

Space Complexity

O(N) – The solution described stores all score updates. In the worst case, each player (up to N players, where N is the number of players) could have a unique score update recorded. Therefore, we would potentially need to store N score updates. As such, the auxiliary space grows linearly with the number of players. Thus, the space complexity is O(N).

Optimal Solution

Approach

The goal is to create a system that keeps track of player scores and quickly provides rankings. We'll use a clever way to store scores so we can easily find the top players without checking every score each time.

Here's how the algorithm would work step-by-step:

First, use a way to quickly look up each player's score. Think of this like a phone book where you can find someone's number by their name.
Also, we'll keep the scores organized in a way that automatically sorts them. Imagine a staircase where each step represents a score, and players are standing on their score's step.
When a player's score changes, we update their score in the phone book. Then, we move them to the correct step on the staircase to keep the scores sorted.
To get the top players, we just start at the top of the staircase and work our way down until we have the number of players we need. This is much faster than searching through every single player's score.

Code Implementation

class Leaderboard:

    def __init__(self):
        self.player_scores = {}
        self.sorted_scores = []

    def addScore(self, player_id, score):
        if player_id in self.player_scores:
            self.player_scores[player_id] += score
            total_score = self.player_scores[player_id]
            self._update_score(player_id, total_score)
        else:
            self.player_scores[player_id] = score
            self._insert_score(player_id, score)

    def _insert_score(self, player_id, score):
        # Maintain sorted order
        index = 0
        while index < len(self.sorted_scores) and score <= self.sorted_scores[index][1]:
            index += 1
        self.sorted_scores.insert(index, (player_id, score))

    def _update_score(self, player_id, new_score):
        # Remove the old score and insert the updated score.
        for i, (player, score) in enumerate(self.sorted_scores):
            if player == player_id:
                del self.sorted_scores[i]
                break
        self._insert_score(player_id, new_score)

    def top(self, k):
        # Sum the top k scores.
        total = 0
        for i in range(k):
            total += self.sorted_scores[i][1]
        return total

    def reset(self, player_id):
        # Reset a players score and remove from score list.
        if player_id in self.player_scores:
            del self.player_scores[player_id]
            for i, (player, score) in enumerate(self.sorted_scores):
                if player == player_id:
                    del self.sorted_scores[i]
                    break

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

O(k + log n) – The system uses a hash map (or dictionary) for player score lookups which takes O(1) time. Inserting or updating a score in the sorted data structure (described as a 'staircase') takes O(log n) time, where n is the number of unique scores, as we need to find the correct position to maintain the sorted order. Retrieving the top k scores involves traversing the 'staircase' from the highest score down, which takes O(k) time. Therefore, the overall complexity for updating and retrieving top scores is O(k + log n).

Space Complexity

O(N) – The solution uses a hash map (the 'phone book') to store player scores, where N is the number of players. This hash map consumes space proportional to N. Additionally, the 'staircase' which sorts the scores likely uses a data structure such as a sorted set or a balanced tree, also requiring space proportional to N to store the scores of all players. Therefore, the overall auxiliary space complexity is O(N).

Edge Cases

Case	How to Handle
playerId is null or undefined	Throw an IllegalArgumentException, or return an error code indicating an invalid playerId.
score is negative	Throw an IllegalArgumentException as scores are defined as non-negative integers.
k is zero	Return 0 as the sum of the top 0 scores is zero.
k is larger than the number of players in the leaderboard	Return the sum of all scores in the leaderboard, as that is the sum of the top k if k is larger than the leaderboard size.
Adding the same playerId multiple times.	The score should be overwritten with the new score; handle accordingly.
Integer overflow when summing top k scores.	Use a larger data type (e.g., long) to store the sum to prevent potential overflow issues.
Very large number of players and frequent updates.	Optimize the data structure for efficient add, update, and top-k retrieval operations, such as using a priority queue or balanced tree.
playerId is an empty string	Treat it as an invalid input like null playerId and return an error or throw an exception.