Effective data structure for leaders

Question

I like to implement the leaderboard, and I understand that although it seems to be simple tasks, it can become very difficult. I could just use a database with corresponding indexes, but Id would like to know if a data structure is efficient that can support the following operations.

• Add rating for this player
• Get the best score for this player.
• Get rank for this player
• Get players with an account above and below the current player level
• Support for different timeframes: today's rating, this week, this year, etc.
• Scales up to ~ 100,000 players
• The amount of memory is as small as possible (i.e. it works on a cheap machine)

Thanks for the help!

Answer 1

You can use binary search trees (balanced, such as AVL or red-black) to store player information based on the total score. In the player’s structure, you can have different arrays for different time frames, with separate variables for the total score and the best result. Searching for a rank or players below or above a specific player will require a crawl.

Answer 2

The solution is to use two data structures. The update operation will accept O (n) as not only the given player, but all the player’s ranks must be recounted.

We will use two DS for this: a. Balanced Binary Search Tree b. Hash Map Each node of a Binary Search Tree is [Uid, Score, Reverse-rank] Uid: is the user id of a player. Score: is the score of a player. Reverse-rank: This is a rank of a player but in reverse order. The player scoring lowest will have this value as 1. The player scoring highest will have this value as the size of a BST. The Binary Search Tree is implemented based on the score of a player. The Hash Map structure is as follows: Key: Uid Value: BST Node. updateRank(userId, score) if player is new (userid not in map) 1. Insert the player in a BST. 2. Insert the player in a Map. 3. Calculate Rank: If a node is inserted to right, then its rank will be one less than its parent. If a node is inserted to left, then its rank will be one more than its parent. if player is old (userid exists in map) 1. Fetch the node from Map. 2. if new score and old score is same then do nothing. 3. Delete the old node. 4. Insert the new node. 5. Calculate Rank: Perform in-order and mark all the nodes from 1 to n (length). This op is expensive among all. It takes O(n) O(n) getRank(userId) Find a node from the map. return rank as (n + 1) - reverse rank O(1) display() Perform inorder traversal and return all the players. O(n) NOTE: 1. The tree has to be balanced BST. 2. We cannot use heap because, the display() would be difficult to implement. We would have to remove every element from heap which would take O(nlogn).