33 — LLD: Leaderboard System

Understanding the Problem

A leaderboard tracks scores for millions of players and serves "top K" queries under high write load. The real exercise is picking a data structure that supports fast score updates and fast top-K reads at the same time — a single map or a single sorted list will not cut it.

What is a Leaderboard?

A ranked list of players by score, updated in real time. Common in gaming, fantasy sports, and engagement features. The interface is small — add score, query top K, reset — but the data structure behind it must handle 10M players and thousands of updates per second without tipping over.

---

Requirements

Clarifying Questions

You: Is top-K by score alone, or do we tie-break on something?

Interviewer: Higher score first, then lexicographic playerId for ties.

Gives a total ordering, so the sorted structure has a deterministic sort key.

You: Does reset(playerId) remove the player or zero them out?

Interviewer: Zero out. The player still exists.

So the sorted set retains zero-score entries — you do not shrink on reset.

You: Snapshot or live for top? Is stale-by-a-second acceptable if it reduces contention?

Interviewer: Live preferred, but slight staleness is fine.

Unlocks lock-free structures and lets you tolerate a tiny read-write race.

You: Scores can decrease, not just increase?

Interviewer: Both. The delta can be negative.

So you cannot rely on monotonic merges — you must remove the old entry and re-insert.

Final Requirements

1. addScore(playerId, delta) — apply delta to the player; create if new.
2. top(k) — return sum (or the list) of the top K scores.
3. reset(playerId) — zero out the player's score.
4. Scale: 10M players, thousands of writes per second, K up to 100.
5. Thread-safe under high concurrent writes.

Out of scope: Persistence, historical score tracking, sliding windows, cross-region replication.

Deferred tradeoff: Between sorted.remove(old) and sorted.add(new) a concurrent top(k) may see neither entry. Acceptable for display; for exact correctness use a single lock or versioning.

---

Core Entities and Relationships

Two indexes, one source of truth. The authoritative score-per-player lives in a hash map (O(1) read and write by id). A second index — a sorted structure keyed on (score desc, playerId asc) — powers top-K. When a score changes, you remove the old entry from the sorted index and insert the new one.

Entity	Responsibility
Leaderboard	Facade. addScore, top, reset. Coordinates the dual index.
scores: Map<String, Integer>	playerId → current score. Authoritative.
sorted: SortedSet<Entry>	(playerId, score) sorted by score desc, id asc.
Entry	Immutable (playerId, score) value object with a total order.

Why an immutable Entry? Sorted structures key on the comparison key. If you mutate the score in place, the sort invariant breaks. Remove old, insert new. That is the classic pattern for index maintenance.

Design is iterative. If you need sliding-window leaderboards later, each addScore will also stash a (timestamp, delta) entry for decay.

---

Class Design

Entry (value object)

• playerId: String, score: int.
• Natural order: higher score first; ties broken by playerId ascending.

Leaderboard

State:

• scores: ConcurrentHashMap<String, Integer>.
• sorted: ConcurrentSkipListSet<Entry> (or equivalent thread-safe sorted set).

Methods:

• addScore(playerId, delta).
• top(k) -> long (sum variant) or top(k) -> List<Entry>.
• reset(playerId).

Java

public final class Entry implements Comparable<Entry> {
    final String playerId;
    final int score;
    public Entry(String id, int s) { this.playerId = id; this.score = s; }
    public int compareTo(Entry o) {
        if (o.score != score) return Integer.compare(o.score, score);
        return playerId.compareTo(o.playerId);
    }
    @Override public boolean equals(Object o) {
        if (!(o instanceof Entry e)) return false;
        return score == e.score && playerId.equals(e.playerId);
    }
    @Override public int hashCode() { return playerId.hashCode() * 31 + score; }
}

public class Leaderboard {
    private final ConcurrentHashMap<String, Integer> scores = new ConcurrentHashMap<>();
    private final ConcurrentSkipListSet<Entry> sorted = new ConcurrentSkipListSet<>();

    public void addScore(String playerId, int delta) { /* ... */ }
    public long top(int k) { /* ... */ }
    public void reset(String playerId) { /* ... */ }
}

C++

struct Entry {
    std::string playerId;
    int score;
    bool operator<(const Entry& o) const {
        if (score != o.score) return score > o.score;
        return playerId < o.playerId;
    }
};

class Leaderboard {
    std::unordered_map<std::string, int> scores;
    std::set<Entry> sorted;
    std::mutex mtx;
public:
    void addScore(const std::string& id, int delta);
    long top(int k);
    void reset(const std::string& id);
};

TypeScript

// TS lacks a built-in red-black tree. Use a sorted array with binary search
// or a third-party library. Sketch below.
export interface Entry { playerId: string; score: number; }

export class Leaderboard {
  private scores = new Map<string, number>();
  private sorted: Entry[] = [];  // kept sorted by score desc, id asc

  addScore(id: string, delta: number): void { /* ... */ }
  top(k: number): number { /* ... */ }
  reset(id: string): void { /* ... */ }
}

Design principles at play:

• Facade: Leaderboard hides the dual-index detail from callers.
• Value Object: Entry is immutable; mutations are expressed as remove + insert.
• Information Expert: The sorted set knows how to answer top-K; the hash map knows current scores. Each does one thing.

---

Implementation

Core Logic: addScore

1. Compute new score = old score + delta.
2. If the player existed, remove the old Entry from the sorted set.
3. Insert the new Entry.
4. Update the scores map.

The three steps must happen atomically per player to keep the two indexes in sync. ConcurrentHashMap.compute locks the bin for that key and gives you that guarantee.

Core Logic: top(k)

Iterate the sorted set in order, taking the first K entries. ConcurrentSkipListSet iteration is weakly consistent — you may see the state from a slightly earlier point in time, but you will not see corruption.

Core Logic: reset

Same pattern as addScore — remove the old entry, insert a zero-score entry, update the map.

From Naive to Great

Bad Solution: One unsorted HashMap<playerId, score>. top(k) sorts the entire map every time — O(N log N) per query. At 10M players, that is seconds per query.

Good Solution: HashMap + maintained sorted List<Entry>. top(k) is O(K) but addScore is O(N) for the insertion into the sorted list.

Great Solution: ConcurrentHashMap + ConcurrentSkipListSet. addScore is O(log N) for both the remove and insert. top(k) is O(K) iteration. Both lock-free for reads on the skip list.

Implementations

Java

public void addScore(String playerId, int delta) {
    scores.compute(playerId, (id, prev) -> {
        int oldScore = prev == null ? 0 : prev;
        int newScore = oldScore + delta;
        if (prev != null) sorted.remove(new Entry(id, oldScore));
        sorted.add(new Entry(id, newScore));
        return newScore;
    });
}

public long top(int k) {
    long sum = 0;
    int taken = 0;
    for (Entry e : sorted) {
        if (taken >= k) break;
        sum += e.score;
        taken++;
    }
    return sum;
}

public void reset(String playerId) {
    scores.compute(playerId, (id, prev) -> {
        if (prev == null) return 0;
        sorted.remove(new Entry(id, prev));
        sorted.add(new Entry(id, 0));
        return 0;
    });
}

C++

void Leaderboard::addScore(const std::string& id, int delta) {
    std::lock_guard<std::mutex> lk(mtx);
    auto it = scores.find(id);
    int oldScore = it == scores.end() ? 0 : it->second;
    int newScore = oldScore + delta;
    if (it != scores.end()) sorted.erase({id, oldScore});
    sorted.insert({id, newScore});
    scores[id] = newScore;
}

long Leaderboard::top(int k) {
    std::lock_guard<std::mutex> lk(mtx);
    long sum = 0;
    int taken = 0;
    for (const auto& e : sorted) {
        if (taken >= k) break;
        sum += e.score;
        ++taken;
    }
    return sum;
}

void Leaderboard::reset(const std::string& id) {
    std::lock_guard<std::mutex> lk(mtx);
    auto it = scores.find(id);
    if (it == scores.end()) return;
    sorted.erase({id, it->second});
    sorted.insert({id, 0});
    scores[id] = 0;
}

TypeScript

addScore(id: string, delta: number): void {
  const oldScore = this.scores.get(id) ?? 0;
  const newScore = oldScore + delta;
  if (this.scores.has(id)) this.removeEntry({ playerId: id, score: oldScore });
  this.insertEntry({ playerId: id, score: newScore });
  this.scores.set(id, newScore);
}

top(k: number): number {
  let sum = 0;
  for (let i = 0; i < Math.min(k, this.sorted.length); i++) sum += this.sorted[i].score;
  return sum;
}

private compare(a: Entry, b: Entry): number {
  if (a.score !== b.score) return b.score - a.score;
  return a.playerId < b.playerId ? -1 : a.playerId > b.playerId ? 1 : 0;
}

private insertEntry(e: Entry): void {
  let lo = 0, hi = this.sorted.length;
  while (lo < hi) {
    const mid = (lo + hi) >>> 1;
    if (this.compare(this.sorted[mid], e) < 0) lo = mid + 1; else hi = mid;
  }
  this.sorted.splice(lo, 0, e);
}

private removeEntry(e: Entry): void {
  let lo = 0, hi = this.sorted.length;
  while (lo < hi) {
    const mid = (lo + hi) >>> 1;
    if (this.compare(this.sorted[mid], e) < 0) lo = mid + 1; else hi = mid;
  }
  if (this.sorted[lo]?.playerId === e.playerId && this.sorted[lo]?.score === e.score) {
    this.sorted.splice(lo, 1);
  }
}

Thread Safety

ConcurrentHashMap.compute locks the per-key bin, so updates to the same player serialize. ConcurrentSkipListSet is lock-free.

The subtle race: between sorted.remove(old) and sorted.add(new), a concurrent top(k) may briefly see neither entry for that player. The scores map is always consistent — the sorted index has a tiny window of inconsistency per player. Acceptable for a leaderboard display; for hard consistency use a single lock or version-tag entries.

Verification

Op	scores	sorted (top of set)	Returns
addScore(a, 10)		[(a,10)]	-
addScore(b, 20)		[(b,20), (a,10)]	-
addScore(a, 15)		[(a,25), (b,20)]	-
top(1)	-	-	25
top(2)	-	-	45
reset(a)		[(b,20), (a,0)]	-
top(1)	-	-	20

Note how addScore(a, 15) removed (a,10) from sorted, then inserted (a,25) — that is the core dance.

---

Complete Code Implementation

Java

import java.util.concurrent.*;

public final class Entry implements Comparable<Entry> {
    final String playerId;
    final int score;
    public Entry(String id, int s) { this.playerId = id; this.score = s; }
    public int compareTo(Entry o) {
        if (o.score != score) return Integer.compare(o.score, score);
        return playerId.compareTo(o.playerId);
    }
    @Override public boolean equals(Object o) {
        return o instanceof Entry e && score == e.score && playerId.equals(e.playerId);
    }
    @Override public int hashCode() { return playerId.hashCode() * 31 + score; }
}

public class Leaderboard {
    private final ConcurrentHashMap<String, Integer> scores = new ConcurrentHashMap<>();
    private final ConcurrentSkipListSet<Entry> sorted = new ConcurrentSkipListSet<>();

    public void addScore(String playerId, int delta) {
        scores.compute(playerId, (id, prev) -> {
            int oldScore = prev == null ? 0 : prev;
            int newScore = oldScore + delta;
            if (prev != null) sorted.remove(new Entry(id, oldScore));
            sorted.add(new Entry(id, newScore));
            return newScore;
        });
    }

    public long top(int k) {
        long sum = 0;
        int taken = 0;
        for (Entry e : sorted) {
            if (taken >= k) break;
            sum += e.score;
            taken++;
        }
        return sum;
    }

    public java.util.List<Entry> topEntries(int k) {
        java.util.List<Entry> out = new java.util.ArrayList<>(k);
        for (Entry e : sorted) {
            if (out.size() >= k) break;
            out.add(e);
        }
        return out;
    }

    public void reset(String playerId) {
        scores.compute(playerId, (id, prev) -> {
            if (prev == null) return 0;
            sorted.remove(new Entry(id, prev));
            sorted.add(new Entry(id, 0));
            return 0;
        });
    }
}

C++

#include <unordered_map>
#include <set>
#include <mutex>
#include <string>

struct Entry {
    std::string playerId;
    int score;
    bool operator<(const Entry& o) const {
        if (score != o.score) return score > o.score;
        return playerId < o.playerId;
    }
};

class Leaderboard {
    std::unordered_map<std::string, int> scores;
    std::set<Entry> sorted;
    std::mutex mtx;
public:
    void addScore(const std::string& id, int delta) {
        std::lock_guard<std::mutex> lk(mtx);
        auto it = scores.find(id);
        int oldScore = it == scores.end() ? 0 : it->second;
        int newScore = oldScore + delta;
        if (it != scores.end()) sorted.erase({id, oldScore});
        sorted.insert({id, newScore});
        scores[id] = newScore;
    }

    long top(int k) {
        std::lock_guard<std::mutex> lk(mtx);
        long sum = 0;
        int taken = 0;
        for (const auto& e : sorted) {
            if (taken >= k) break;
            sum += e.score;
            ++taken;
        }
        return sum;
    }

    void reset(const std::string& id) {
        std::lock_guard<std::mutex> lk(mtx);
        auto it = scores.find(id);
        if (it == scores.end()) return;
        sorted.erase({id, it->second});
        sorted.insert({id, 0});
        scores[id] = 0;
    }
};

TypeScript

export interface Entry { playerId: string; score: number; }

export class Leaderboard {
  private scores = new Map<string, number>();
  private sorted: Entry[] = [];

  private compare(a: Entry, b: Entry): number {
    if (a.score !== b.score) return b.score - a.score;
    return a.playerId < b.playerId ? -1 : a.playerId > b.playerId ? 1 : 0;
  }

  private insert(e: Entry): void {
    let lo = 0, hi = this.sorted.length;
    while (lo < hi) {
      const mid = (lo + hi) >>> 1;
      if (this.compare(this.sorted[mid], e) < 0) lo = mid + 1; else hi = mid;
    }
    this.sorted.splice(lo, 0, e);
  }

  private remove(e: Entry): void {
    let lo = 0, hi = this.sorted.length;
    while (lo < hi) {
      const mid = (lo + hi) >>> 1;
      if (this.compare(this.sorted[mid], e) < 0) lo = mid + 1; else hi = mid;
    }
    if (this.sorted[lo]?.playerId === e.playerId && this.sorted[lo]?.score === e.score) {
      this.sorted.splice(lo, 1);
    }
  }

  addScore(id: string, delta: number): void {
    const oldScore = this.scores.get(id);
    const base = oldScore ?? 0;
    const newScore = base + delta;
    if (oldScore !== undefined) this.remove({ playerId: id, score: oldScore });
    this.insert({ playerId: id, score: newScore });
    this.scores.set(id, newScore);
  }

  top(k: number): number {
    let sum = 0;
    const n = Math.min(k, this.sorted.length);
    for (let i = 0; i < n; i++) sum += this.sorted[i].score;
    return sum;
  }

  reset(id: string): void {
    const prev = this.scores.get(id);
    if (prev === undefined) return;
    this.remove({ playerId: id, score: prev });
    this.insert({ playerId: id, score: 0 });
    this.scores.set(id, 0);
  }
}

---

Extensibility

1. "Top-K with the actual scores, not just the sum?"

Already supported by iterating the sorted set and returning the first K Entry objects. See topEntries in the Java implementation.

2. "Sliding-window leaderboard — score over the last 24 hours?"

Each addScore enqueues (timestamp, delta) per player. A background sweeper subtracts expired deltas when they age out. Alternatively, precompute hourly buckets and recompute the sum of the last 24 at query time.

private final Map<String, Deque<TimedDelta>> history = new ConcurrentHashMap<>();

Tradeoff: Storage grows with throughput. Bucketing is the usual compromise.

3. "Sharded across hosts?"

Partition by hash(playerId). For top(k), fan out to all shards, ask for each shard's top K, then merge at the coordinator. Network cost is O(shards * K).

In production, this is exactly what Redis ZSET does in a single process — and a Redis Cluster handles the sharding layer. Name the mapping to production tech explicitly; interviewers appreciate it.

---

What is Expected at Each Level

Level	Expectations
Junior (L4)	Sort the whole map on every top(k) call. Correct but O(N log N) per query.
Mid (L5)	Dual index (HashMap + sorted structure), O(log N) writes, O(K) reads. Mentions the need for thread safety.
Senior (L5A)	ConcurrentHashMap.compute for atomic dual-index updates, ConcurrentSkipListSet for lock-free reads, articulates the small remove/insert race as acceptable. Proactively maps to Redis ZSET.
Staff (L6)	Sharded service design, sliding-window variants, percentile ranks, HyperLogLog for unique-player estimation, SLOs for write and read paths.