Home
Design A Leaderboard using Priority Queue, Hash Map (unordered_map), or Hash Set (multi_set)
Tags:, , , , , , , ,

Design A Leaderboard using Priority Queue, Hash Map (unordered_map), or Hash Set (multi_set)

December 11, 2019 No Comments algorithms, c / c++, data structure, design questions, programming languages, python

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. It is guaranteed that the player was added to the leaderboard before calling this function.

Initially, the leaderboard is empty.

Example 1:
Input: 

1
2

["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]]
["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: 

1

[null,null,null,null,null,null,73,null,null,null,141]
[null,null,null,null,null,null,73,null,null,null,141]

Explanation: 

1
2
3
4
5
6
7
8
9
10
11

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

Hints:
What data structure can we use to keep the players’ data?
Keep a map (dictionary) of player scores.
For each top(K) function call, find the maximum K scores and add them.

Your Leaderboard object will be instantiated and called as such:

1
2
3
4

Leaderboard* obj = new Leaderboard();
obj->addScore(playerId,score);
int param_2 = obj->top(K);
obj->reset(playerId);
Leaderboard* obj = new Leaderboard();
obj->addScore(playerId,score);
int param_2 = obj->top(K);
obj->reset(playerId);

Using a Priority Queue and Hashmap (unordered_map) in C++ to create a Leader Board

We can use a Hashmap (unordered_map in C++) to store the players and their scores. The space complexity is O(N). The time complexity of adding a score, and reseting a score is O(1) constant due to usage of a hash map.

To return the sum of the top K scores, we need to push all the values into a priority queue – which takes O(N logN). Then we need to pop first K values and sum them. The overall complexity is O(NLogN + K)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

class Leaderboard {
public:
    Leaderboard() {
        
    }
    
    void addScore(int playerId, int score) {
        scores[playerId] += score;
    }
    
    int top(int K) {
        priority_queue<int> pq;
        for (auto it = scores.begin(); it != scores.end(); it ++) {
            pq.push(it->second);
        }
        int sum = 0;
        for (int i = 0; i < K; ++ i) {
            if (!pq.empty()) {
                sum += pq.top();
                pq.pop();
            }
        }
        return sum;
    }
    
    void reset(int playerId) {
        scores[playerId] = 0;
    }
private:
    unordered_map<int, int> scores;
};
class Leaderboard {
public:
    Leaderboard() {
        
    }
    
    void addScore(int playerId, int score) {
        scores[playerId] += score;
    }
    
    int top(int K) {
        priority_queue<int> pq;
        for (auto it = scores.begin(); it != scores.end(); it ++) {
            pq.push(it->second);
        }
        int sum = 0;
        for (int i = 0; i < K; ++ i) {
            if (!pq.empty()) {
                sum += pq.top();
                pq.pop();
            }
        }
        return sum;
    }
    
    void reset(int playerId) {
        scores[playerId] = 0;
    }
private:
    unordered_map<int, int> scores;
};

Using Two Hashmap (unordered_map and map) in C++ to create a Leader Board

We can store the scores and their frequency in a map – which is sorted by the keys. The time complexity stays constant O(1) for method addScore and reset. The complexity of Top K will be O(K).

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38

class Leaderboard {
public:
    Leaderboard() {
        
    }
    
    void addScore(int playerId, int score) {
        if (--scores[players[playerId]] <= 0) {
             scores.erase(players[playerId]);
        }
        players[playerId] += score;
        scores[players[playerId]] ++;
    }
    
    int top(int K) {
        int sum = 0;
        auto it = scores.end();        
        for (; K > 0; it --) {
            if (it->second > 0) { // this check is optional
                for (int u = 0; u < min(it->second, K); u ++) {
                    sum += it->first;
                }
                K -= it->second;
            }
        }
        return sum;
    }
    
    void reset(int playerId) {
        if (--scores[players[playerId]] <= 0) {
            scores.erase(players[playerId]);
        } 
        players[playerId] = 0;
    }
private:
    unordered_map<int, int> players;
    map<int, int> scores;
};
class Leaderboard {
public:
    Leaderboard() {
        
    }
    
    void addScore(int playerId, int score) {
        if (--scores[players[playerId]] <= 0) {
             scores.erase(players[playerId]);
        }
        players[playerId] += score;
        scores[players[playerId]] ++;
    }
    
    int top(int K) {
        int sum = 0;
        auto it = scores.end();        
        for (; K > 0; it --) {
            if (it->second > 0) { // this check is optional
                for (int u = 0; u < min(it->second, K); u ++) {
                    sum += it->first;
                }
                K -= it->second;
            }
        }
        return sum;
    }
    
    void reset(int playerId) {
        if (--scores[players[playerId]] <= 0) {
            scores.erase(players[playerId]);
        } 
        players[playerId] = 0;
    }
private:
    unordered_map<int, int> players;
    map<int, int> scores;
};

Design and Implement a Leader Board using a Multi-Set and Hash Map (unordered_map) in C++

We can use a C++ std::multi_set to store the scores. A multi_set is basically a hash set (like std::set) but allowing the duplicates. Then the Top K function is a bit simpler compared to using unordered_map to store the scores. We can add from the last iterator until K elements are iterated.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

class Leaderboard {
public:
    Leaderboard() {
        
    }
    
    void addScore(int playerId, int score) {
        auto it = scores.find(players[playerId]);
        if (it != scores.end()) {
            scores.erase(it);
        }
        players[playerId] += score;
        scores.insert(players[playerId]);
    }
    
    int top(int K) {
        int sum = 0;
        for (auto it = --scores.end(); K > 0; -- K, it --) {
            sum += *it;
        }
        return sum;
    }
    
    void reset(int playerId) {
        scores.erase(scores.find(players[playerId]));
        players.erase(playerId);
    }
private:
    unordered_map<int, int> players;
    multiset<int> scores;
};
class Leaderboard {
public:
    Leaderboard() {
        
    }
    
    void addScore(int playerId, int score) {
        auto it = scores.find(players[playerId]);
        if (it != scores.end()) {
            scores.erase(it);
        }
        players[playerId] += score;
        scores.insert(players[playerId]);
    }
    
    int top(int K) {
        int sum = 0;
        for (auto it = --scores.end(); K > 0; -- K, it --) {
            sum += *it;
        }
        return sum;
    }
    
    void reset(int playerId) {
        scores.erase(scores.find(players[playerId]));
        players.erase(playerId);
    }
private:
    unordered_map<int, int> players;
    multiset<int> scores;
};

Note that:

1

auto it == --scores.end();
auto it == --scores.end();

is essential to:

1
2

auto it = scores.end();
it --;
auto it = scores.end();
it --;

Both will make iterator it point to the last element of the multi_set which will be the largest score.

Python Implementation of the Leader Boards

Python often gives a shorter implementation, The Leaderboard object will be instantiated and called as such in Python:

1
2
3
4

obj = Leaderboard()
obj.addScore(playerId,score)
param_2 = obj.top(K)
obj.reset(playerId)
obj = Leaderboard()
obj.addScore(playerId,score)
param_2 = obj.top(K)
obj.reset(playerId)

We can use the sum, list comprehension and the array slicing in Python:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

class Leaderboard(object):
    def __init__(self):
        self.scores = dict() # same as {}
 
    def addScore(self, playerId, score):
        if playerId in self.scores:
            self.scores[playerId] += score
        else:
            self.scores[playerId] = score
 
    def top(self, K):        
        return sum(sorted(self.scores.values(), reverse = True)[:K])
 
    def reset(self, playerId):
        if playerId in self.scores:
            del self.scores[playerId]
class Leaderboard(object):
    def __init__(self):
        self.scores = dict() # same as {}

    def addScore(self, playerId, score):
        if playerId in self.scores:
            self.scores[playerId] += score
        else:
            self.scores[playerId] = score

    def top(self, K):        
        return sum(sorted(self.scores.values(), reverse = True)[:K])

    def reset(self, playerId):
        if playerId in self.scores:
            del self.scores[playerId]

We can use the collections.defaultdict to further shortening the addScore implementation – no need to check if the key exists in the dictionary.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

import collections
 
class Leaderboard(object):
    def __init__(self):
        self.scores = collections.defaultdict(int)
 
    def addScore(self, playerId, score):
        self.scores[playerId] += score
 
    def top(self, K):        
        return sum(sorted(self.scores.values(), reverse = True)[:K])
 
    def reset(self, playerId):
        if playerId in self.scores:
            del self.scores[playerId]
import collections

class Leaderboard(object):
    def __init__(self):
        self.scores = collections.defaultdict(int)

    def addScore(self, playerId, score):
        self.scores[playerId] += score

    def top(self, K):        
        return sum(sorted(self.scores.values(), reverse = True)[:K])

    def reset(self, playerId):
        if playerId in self.scores:
            del self.scores[playerId]

We can also use the heapq to use the heap library in Python:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

import heapq
class Leaderboard:
 
    def __init__(self):
        self.heap = {}        
 
    def addScore(self, playerId: int, score: int) -> None:
        if playerId not in self.heap.keys():
            self.heap[playerId] = score
        else:
            self.heap[playerId] += score
 
    def top(self, K: int) -> int:
        return sum(heapq.nlargest(K, self.heap.values()))
 
    def reset(self, playerId: int) -> None:
        if playerId in self.heap.keys():
            self.heap[playerId] = 0
import heapq
class Leaderboard:

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

    def addScore(self, playerId: int, score: int) -> None:
        if playerId not in self.heap.keys():
            self.heap[playerId] = score
        else:
            self.heap[playerId] += score

    def top(self, K: int) -> int:
        return sum(heapq.nlargest(K, self.heap.values()))

    def reset(self, playerId: int) -> None:
        if playerId in self.heap.keys():
            self.heap[playerId] = 0

The heapq.nlargest returns the Top N largests elements.

Also, we can use the collections.Counter().most_common to return the Top K elements.

1
2
3
4
5
6
7
8
9
10
11
12

class Leaderboard(object):
    def __init__(self):
        self.A = collections.Counter()
 
    def addScore(self, playerId, score):
        self.A[playerId] += score
 
    def top(self, K):
        return sum(v for i,v in self.A.most_common(K))
 
    def reset(self, playerId):
        self.A[playerId] = 0
class Leaderboard(object):
    def __init__(self):
        self.A = collections.Counter()

    def addScore(self, playerId, score):
        self.A[playerId] += score

    def top(self, K):
        return sum(v for i,v in self.A.most_common(K))

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

–EOF (The Ultimate Computing & Technology Blog) —

GD Star Rating
loading...
1248 words
Last Post: 5 Innovative Ways Ecommerce Businesses Are Leveraging Machine Learning
Next Post: Greedy Algorithm to Group the Numbers/Items Given the Group Size They Belong To

The Permanent URL is: Design A Leaderboard using Priority Queue, Hash Map (unordered_map), or Hash Set (multi_set)

Related posts:

  1. Teaching Kids Programming – High Accuracy Multiplication Algorithm (Multiply Strings) Teaching Kids Programming: Videos on Data Structures and Algorithms Given two non-negative integers num1 and...
  2. Microbit Programming: Snake Game with Growing Body and Greedy Strategy Last week, we show the possibility of playing a simple Snake Game on the Microbit...
  3. Depth First Search Algorithm to Delete Insufficient Nodes in Root to Leaf Paths in Binary Tree Given the root of a binary tree, consider all root to leaf paths: paths from...
  4. PHP Function to Get Exchange Rate Between Cryptocurrency (BTC, LTC, ETH) to Fiat Currency? The Cryptocurrencies such as Bitcoins, Litecoins, ETH coins are the top coins among others. The...
  5. How to Fix Visual Studio Search in Files Not Displaying List of Files Error? In Visual Studio, you can use short-cut Ctrl+Shift+F to find string in files (in solution,...
  6. Fixing Profile Query Command due to API Change in Steem Blockchain Due to an API change in SteemIt see this post, the following code to get...
  7. How to Fix a Slow/Incorrect Clock on Windows? I have been using HP Z800 Server for a couple of years and lately, the...
  8. WordPress Hosting Services You Can’t DIY If you happen to be using WordPress for your website, there’s no doubt that you’re...

Leave a Reply