Design a dynamic leaderboard with rank queries

Leaderboard System

Design a class Leaderboard that tracks user scores in a competitive environment. The system must support updating scores and retrieving the rank of a specific user. Your implementation should handle dynamic changes efficiently.

Requirements

Implement the following methods:

1. update_score(user_id: int, score: int): Updates the score of user_id to the given value. If the user doesn't exist, add them. If they exist, replace their current score.
2. get_rank(user_id: int) -> int: Returns the rank of user_id. The rank is defined as 1 + (number of users with a strictly higher score than user_id).
3. get_top_k(k: int) -> List[int]: Returns a list of user_ids for the top k scores, sorted in descending order of score. In case of ties in scores, sort by user_id in ascending order.

Constraints

• user_id are unique integers.
• Assume up to 100,000 total user_ids.
• update_score and get_rank should ideally perform better than O(N) where N is the total number of users.

Examples

# Initialize
lb = Leaderboard()
lb.update_score(1, 50)
lb.update_score(2, 80)
lb.update_score(3, 80)

# Rank of 1 is 3 (80 > 80 > 50)
print(lb.get_rank(1)) # Output: 3

# Top 2: [2, 3] (80, 80 tied, sorted by id 2 < 3)
print(lb.get_top_k(2)) # Output: [2, 3]

Edge Cases

• Updating a score to the same value.
• Querying a user_id that does not exist.
• Handling a k larger than the number of users currently in the leaderboard.