Efficient data structure for leaderboard

Question

I’d like to implement a leaderboard and I am realizing that even though this seem to be a simple tasks, this can get very complex. I could simply use a database with proper indexes, but I’d like to know if there’s an efficient data structure that can support the following operations.

• Add score for a given player
• Retrieve best score for a given player
• Retrieve rank for a given player
• Retrieve the players with the score above and below current player rank
• Support different timeframe: today’s score, this week, this year, etc.
• Scales to ~100,000 players
• Memory footprint as small as possible (i.e. runs on cheap machine)

Thanks for the help!

Answer 1

The solution is to use two data structure. The update operation will take O(n) as not just the given player but all the player's rank has to be re-calculated.

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