Problem · Segment Tree
Dynamic Fixed-K Score Leaderboard
Learn this problem● Hard
CoinbaseFULLTIMEONSITE INTERVIEW
CoinbaseFULLTIMEONSITE INTERVIEWProblem statement
Build a leaderboard with a fixed positive rank k. You are given equal-length arrays operations, userIds, and scores. Process each index in order:
"add"inserts the user with the supplied score, or replaces that user's previous score."remove"deletes the user if present; removing an absent user is a no-op."query"asks for the current kth-highest score, counting every user separately even when scores tie.
For query, ignore the corresponding user ID and score. Return one string for each query, in order: the decimal kth-highest score, or "null" when fewer than k users are present.
Function
processLeaderboard(k: int, operations: String[], userIds: String[], scores: int[]) → String[]Examples
Example 1
k = 2operations = ["add","query","add","query","add","query","remove","query"]userIds = ["u1","","u2","","u1","","u2",""]scores = [10,0,5,0,3,0,0,0]return = ["null","5","3","null"]One user is insufficient for the first query. After adding u2, the second-highest score is 5. Updating u1 to 3 changes it to 3, and removing u2 leaves too few users.
Example 2
k = 2operations = ["add","add","query","remove","query"]userIds = ["a","b","","a",""]scores = [7,7,0,0,0]return = ["7","null"]Equal scores belong to two separate users, so the second-highest score is still 7. After one user is removed, only one remains.
Example 3
k = 1operations = ["remove","query","add","query"]userIds = ["ghost","","n",""]scores = [0,0,-4,0]return = ["null","-4"]The absent removal changes nothing. Negative scores are valid leaderboard values.
Constraints
1 <= k <= 100000.operations.length == userIds.length == scores.length.0 <= operations.length <= 100000.- Every operation is exactly
"add","remove", or"query". - An add or remove user ID is non-empty and contains at most 50 Unicode characters.
-1000000000 <= scores[i] <= 1000000000for add operations.