## Problem Maintain scores for users while supporting updates, removals, and queries for the current `k`th-highest score. The value of `k` is fixed when the structure is created. Operations are: - `ADD user score`: insert the user, or replace that user's previous score. - `REMOVE user`: remove the user if present. - `QUERY`: return the `k`th-highest score, counting users separately even when scores tie. Return `null` when fewer than `k` users exist. ### Function Contract Implement `kthScoreResults(k, operations)` and return the result of each `QUERY` in order. Represent an operation as `['add', user, score]`, `['remove', user]`, or `['query']`. ### Constraints & Assumptions - `1 <= k <= 100,000`. - At most `200,000` operations occur. - User IDs are unique nonempty ASCII strings; scores are signed 32-bit integers. - Updating a user must remove the old score before inserting the new one. - Target `ADD` and `REMOVE` time is `O(log n)`. ### Clarifying Questions to Ask - How are tied scores ranked? Each user occupies one position; the query returns only the score. - What happens when an unknown user is removed? Nothing. - Is `k` different per query? No. ```hint Partition users around the answer Maintain exactly the top `k` user-score pairs in one ordered multiset and all remaining pairs in another. The minimum score in the top side is the answer. ``` ```hint Remove stale state before updates A user-to-score map identifies the exact old pair to delete. Then insert the new pair and rebalance sizes and boundary order. ``` ### Example ```text k = 2 operations = [ ["add","a",10], ["add","b",7], ["query"], ["add","c",12], ["query"], ["add","b",20], ["query"], ["remove","c"], ["query"] ] result = [7,10,12,10] ``` ### Evaluation Focus - Replaces rather than duplicates an existing user's score. - Keeps exactly `min(k, userCount)` entries on the top side. - Restores ordering when an update or removal crosses the boundary. - Handles ties by retaining a unique `(score, user)` pair. - Meets logarithmic update/removal and constant or logarithmic query bounds. ### Extensions to Discuss 1. What changes if `k` varies on every query? 2. How would the design work without an ordered-multiset library? 3. How would you persist and recover the state from an event log?