Design A Leaderboard using Priority Queue, Hash Map (unordered_m

Time：2020-09-15 16:10:27
Class：Weblog
Read：17

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:

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:

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)

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

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.

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:

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:

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.

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:

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.

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) —

Recommend：
The Top Client-Attraction Strategies
Side Hustle Tips for the Social Media Savvy
A Quick Guide To Creating A User Persona For Your Blog
7 Top Image Compression Plugins For Your WordPress Blog
3 Ways to Convert Blog Readers to Leads
7 Ways To Deal With AdBlock Users If You’re A Blogger
2020 Design Trends [Infographic]
8 Content Marketing Plugins You Need For Your WordPress Blog
Tips to Make Money from the Comfort of Your Own Home
5 Tips for Protecting Your Freelance Business from Liabilities

Comment list

Comment add: Name：　Check：