Design a waitlist system with top/bottom K

Waitlist System Design

Design a Waitlist class that manages users represented by unique string IDs and their associated integer priority scores. The system must support the following operations:

• add_or_update(user_id, score): Adds a user to the waitlist or updates their score if they already exist. Time complexity should be O(log N).
• remove(user_id): Removes a user from the waitlist. Time complexity should be O(log N).
• get_top_k(k): Returns a list of user IDs with the k highest scores, sorted in descending order. If scores are tied, order them by user_id lexicographically.
• get_bottom_k(k): Returns a list of user IDs with the k lowest scores, sorted in ascending order. If scores are tied, order them by user_id lexicographically.

Constraints

• The number of users N can reach up to 10^5.
• The number of operations can reach up to 10^5.
• k will always be a positive integer where 1 <= k <= N.

Example

# Waitlist configuration
w = Waitlist()
w.add_or_update("alice", 50)
w.add_or_update("bob", 10)
w.add_or_update("charlie", 50)

# Top 2 scores: alice and charlie (both 50, sorted alphabetically)
w.get_top_k(2) # Expected: ["alice", "charlie"]

# Bottom 1 score: bob
w.get_bottom_k(1) # Expected: ["bob"]

Implementation Requirements

Provide a Python class implementation. Consider how to handle score updates efficiently, as you may need to move an item within your data structure when its priority changes.