Cruxly

Cruxly › Low-level design › LLD Exercises

Leaderboard

the update is O(log n), the read is O(1), and rank is a derived value, not stored state

Open the interactive lesson

Prompt: design a real-time leaderboard. updateScore(userId, delta) changes a user's score; getRank(userId) returns their current rank; getTopN(n) returns the top N users by score. Scores update frequently (thousands per second); rank queries must be fast and always reflect the latest scores.

45 minutes. The interesting part isn't storing scores — it's that "rank" is a relative, derived quantity that changes for potentially many users on every single update, and the exercise is picking a structure where that doesn't mean recomputing everything.

Applying the five moves: the nouns are deceptively few — User and Score — and move 2's real work here is refusing to add Rank as a stored noun, because rank is derived, and a stored rank field is exactly the thing that goes stale for thousands of other users on every single update. The invariant is "rank is always computed from current scores, never stored" — one sentence that eliminates an entire class of staleness bug before any structure is chosen. There's no meaningful interface seam to add (a scoring-rule interface would be inventing variation the prompt never hinted at) — saying that explicitly beats adding one reflexively. Concurrency: thousands of updates per second against a structure that concurrent readers are also traversing is the real pressure — name whether reads see a consistent snapshot or a possibly-mid-update view, because "always reflect the latest scores" in the prompt is a consistency claim that deserves an explicit answer rather than an assumption.

Scope, and why rank cannot be a stored field

In scope: updateScore, getRank, getTopN, single-server in-memory implementation. Out of scope (say it): distributed/sharded leaderboards across machines (a much harder follow-up, name it as a different exercise), tie-breaking rules beyond "say what happens on equal scores," historical rank-over-time tracking.

The tempting first design stores a rank field on each user and updates it on every score change — this is the wrong shape, and the reason is structural, not a performance detail. A user's rank depends on every other user's score, so a single updateScore call can change the rank of every user between the old and new position — updating N users' rank fields for one score change is not a bug to optimize away later, it's evidence the data model has the wrong primitive as first-class. Rank has to be a derived value, computed on demand from a structure that keeps scores ordered, never a field that has to be kept in sync by hand.

This reframes the whole exercise: pick a structure where "insert/update a score" and "find a user's position among all scores" are both efficient, and rank falls out as a query, not a maintained field.

The classes: a sorted structure plus a hash index for O(1) lookup by user

public class Leaderboard {
    // TreeMap<score, set-of-userIds> gives O(log n) insert/remove and an
    // ordered walk for getTopN; userScores gives O(1) "what is X's current score."
    private final TreeMap<Long, LinkedHashSet<String>> byScore = new TreeMap<>(Collections.reverseOrder());
    private final Map<String, Long> userScores = new HashMap<>();

    public void updateScore(String userId, long delta) {
        Long oldScore = userScores.get(userId);
        long newScore = (oldScore == null ? 0 : oldScore) + delta;

        if (oldScore != null) {
            LinkedHashSet<String> bucket = byScore.get(oldScore);
            bucket.remove(userId);
            if (bucket.isEmpty()) byScore.remove(oldScore);   // don't leak empty score buckets
        }
        byScore.computeIfAbsent(newScore, k -> new LinkedHashSet<>()).add(userId);
        userScores.put(userId, newScore);
    }

    public long getScore(String userId) {
        return userScores.getOrDefault(userId, 0L);
    }

    public List<String> getTopN(int n) {
        List<String> result = new ArrayList<>();
        for (var entry : byScore.entrySet()) {
            for (String userId : entry.getValue()) {
                result.add(userId);
                if (result.size() == n) return result;
            }
        }
        return result;
    }
}

byScore maps a score to the set of users at that score, not one user per key — ties are the normal case at scale, not an edge case, and a TreeMap<Long, String> (one user per score) simply cannot represent two users tied at the same value. LinkedHashSet for the bucket keeps insertion order among tied users, which is one reasonable, statable tie-breaking rule ("earliest to reach this score ranks higher") — the exercise expects a stated rule, not necessarily this one.

Removing a user from their old score bucket before inserting into the new one, and cleaning up an emptied bucket, is the detail most first attempts skip — leaving stale empty buckets in a TreeMap doesn't break correctness immediately, but it means getTopN and rank-computation walks do wasted work on buckets nobody occupies, growing without bound as scores fluctuate over time.

getRank in better than O(n): the actual hard part

public int getRank(String userId) {
    long targetScore = userScores.get(userId);
    int rank = 1;
    for (var entry : byScore.entrySet()) {
        if (entry.getKey().equals(targetScore)) return rank;
        rank += entry.getValue().size();
    }
    return -1;
}

Follow-ups they will ask

"Scale this to 100 million users across multiple servers." This is a sharding problem layered on top of the single-server design, not a bigger version of one TreeMap — scores get partitioned across shards (by user ID, typically), and getTopN becomes a scatter-gather: query the top N from every shard, merge the results, and take the global top N from that merged set, the same fan-in pattern as any sharded top-K query. getRank for one user is cheap (query only that user's shard for their local rank, but computing their global rank requires knowing how many users on other shards outrank them) — naming that global rank is genuinely harder than global top-N in a sharded design is the sophisticated answer.

"What if score updates arrive out of order or duplicated (a user's score-update event is retried)?" This is the same idempotency discipline as the notification and ad-click exercises elsewhere in this track — if updateScore takes a raw delta and the same delta event is retried, the score is double-counted. The fix is either an idempotency key per update event (skip if already applied) or, where possible, sending absolute scores instead of deltas so a retried "set score to 4500" is naturally idempotent regardless of how many times it's applied.

"Real-time rank changes should push to connected clients, not require polling getRank." This is a pub/sub problem stacked on top of the leaderboard (the same Pub/Sub exercise elsewhere in this track) — updateScore publishes a rank-changed event for every user whose rank shifted, and subscribed clients receive pushes instead of polling. The naive version (publish for every affected user on every update) doesn't scale to a viral leaderboard shift; a real system batches and rate-limits rank-change notifications rather than pushing on every single update.

How to say it in the interview

"A rank is not a property of one user, it's a property of one user relative to everyone else, so storing rank directly means every score update could invalidate ranks for other users too. The actual exercise is picking a structure - a sorted set / skip list - where getRank and getTopN are both fast without ever storing a rank field that could go stale."

Checklist

Practice this interactively
Share this lessonWhatsAppLinkedInX

Related lessons