How do I practice coding and algorithm questions?

Use PracHub's coding console to write, test, and debug your solutions in Python or JavaScript. View hints, test against sample inputs, and compare with official solutions.

What difficulty level is this coding question?

This is a medium difficulty Coding & Algorithms question, commonly asked during Technical Screen rounds at Anchorage Digital.

What role is this question designed for?

This question is commonly asked for Software Engineer candidates at Anchorage Digital during technical interviews.

Design a dynamic leaderboard with rank queries | Anchorage Digital Coding Question

Design a dynamic leaderboard with rank queries

Company: Anchorage Digital

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Technical Screen

## Problem: Dynamic Leaderboard You are asked to implement a **leaderboard** that maintains scores for a set of elements (e.g., players/items). Scores can change over time, and you must support efficient ranking queries. ### Data model - Each element has a unique `id` (string or integer). - Each element has a numeric `score` (integer). - Higher score means a better rank. - **Rank 1** is the highest score. - **Ties:** if multiple elements have the same score, break ties by `id` in ascending order (so ordering is total and deterministic). ### Operations to support Implement a data structure (or API) supporting these operations: 1. **Update score** - `update(id, delta)` or `updateTo(id, newScore)` (choose one and clearly document it). - If `id` does not exist, it is created. 2. **Delete element** - `remove(id)` removes the element from the leaderboard. If it doesn’t exist, do nothing. 3. **Get top-K elements** - `topK(k)` returns the `k` highest-ranked element IDs (or `(id, score)` pairs). - If `k` exceeds the number of elements, return all elements. 4. **Get rank of a specific element** - `getRank(id)` returns the 1-indexed rank of `id` under the ordering rules. - If `id` does not exist, return `-1`. ### What to discuss - The time complexity of each operation. - How you would optimize for real-world usage patterns (e.g., frequent updates, frequent top-K queries, many deletes). ### Constraints (assume) - Up to ~1e5 elements. - Up to ~1e5 operations. Define clearly what your `update` operation means (delta vs set), and ensure your design supports all operations correctly.

Quick Answer: This question evaluates proficiency with dynamic data structures and order-statistics, including maintaining sorted order under updates, deterministic tie-breaking, and analyzing time complexity for rank and top-K operations.

Implement a leaderboard that supports score updates, deletion, top-K queries, and rank queries. Each element has a unique integer id and an integer score. Higher scores rank first. If scores are tied, the smaller id ranks first. Rank is 1-indexed. For this problem, update means updateTo: set the element's score to a new absolute score, creating the element if it does not already exist. You are given all operations in order and must return the results of query operations.

Constraints

0 <= len(operations) <= 100000
At most 100000 elements are active at any time
-1000000000 <= id <= 1000000000
-1000000000 <= score <= 1000000000
0 <= k <= 100000
The total number of ids returned across all topK operations is at most 200000

Examples

Input: ([[1,101,50],[1,102,70],[1,103,70],[3,2],[4,103],[4,101]],)

Expected Output: [[102,103],[2],[3]]

Explanation: Players 102 and 103 both have score 70, so id 102 ranks before id 103. Player 101 has score 50 and ranks third.

Input: ([[1,5,10],[1,2,20],[1,8,15],[4,5],[1,5,25],[3,5],[2,2],[4,2],[3,2]],)

Expected Output: [[3],[5,2,8],[-1],[5,8]]

Explanation: Initially id 5 ranks third. After updating id 5 to score 25, the order is 5, 2, 8. Removing id 2 makes its rank -1, leaving 5 then 8.

Input: ([[3,3],[4,1],[2,1],[1,1,0],[3,0],[4,1]],)

Expected Output: [[],[-1],[],[1]]

Explanation: TopK on an empty leaderboard returns an empty list, and a missing id has rank -1. topK(0) also returns an empty list.

Input: ([[1,-1,-5],[1,3,-5],[1,2,-10],[3,10],[4,2],[1,2,-5],[3,3],[2,-1],[4,3]],)

Expected Output: [[-1,3,2],[3],[-1,2,3],[2]]

Explanation: Negative scores are valid. With equal score -5, ids are ordered ascending, so -1 comes before 3, and later -1, 2, 3 are ordered by id.

Input: ([[1,1,100],[1,1,50],[1,2,50],[1,0,50],[3,10],[4,1],[2,42],[2,0],[3,10]],)

Expected Output: [[0,1,2],[2],[1,2]]

Explanation: Updating an existing id replaces its old score. When ids 0, 1, and 2 all have score 50, they rank in id order. Removing a nonexistent id does nothing.

Hints

Convert the ranking rule into a normal ascending sort key: (-score, id). Smaller keys are better ranks.
You need a structure that can count how many active keys are before a given key and can find the k-th active key. An order-statistics tree works; since all operations are known, coordinate compression plus a Fenwick tree is also possible.

Quick Overview

This question evaluates proficiency with dynamic data structures and order-statistics, including maintaining sorted order under updates, deterministic tie-breaking, and analyzing time complexity for rank and top-K operations.