Design a Leaderboard: Sorted Sets, Top-K and Player Rank

"Design a leaderboard" looks like a database query and turns out to be a data structure question. ORDER BY score DESC LIMIT 100 works on a thousand players. On ten million, with scores changing thousands of times a second, sorting at read time is out, and the interesting part is the question most candidates skip: "what's my rank?", asked by the player in nine-millionth place.

The problem it solves

With illustrative assumptions: ten million players, thousands of score updates a second, and three reads that must each take a few milliseconds:

• Top K: the first hundred players, in order.
• My rank: the position of one player, anywhere in the list.
• Around me: the players just above and below one player.

Scores only change through updates, so the order can be kept on the way in instead of rebuilt on the way out.

The intuition

Keep two structures side by side. A hash map from player to current score answers "what is this player's score?" in O(1) and finds the old entry when a score changes. A score-ordered set holds (score, player) pairs in order, so an update is "remove the old pair, insert the new one", a logarithmic walk, and top K is a range read off the front.

The ordered set is a skip list or a balanced tree. Redis sorted sets are the usual interview answer: as of September 2026, the documented costs are O(log N) for ZADD and for rank lookups (ZRANK, ZREVRANK) and O(log N + M) for a range of M entries. Rank lookups are logarithmic because each link in its skip list also stores how many entries it skips, so a walk can add up positions as it goes.

That detail decides the hardest read. Exact rank is cheap only if the structure keeps counts. A B-tree index in a relational database does not, so COUNT(*) WHERE score > x reads every row above the player: nine million rows for the nine-millionth. Once the board is sharded by player, every rank query also has to ask every shard and add the answers. The common compromise is to keep counts per score band: a small array of running totals. A player's rank is then the sum of the bands above plus an estimate inside their own band. Bands one point wide make that estimate exact, which works whenever scores are bounded integers.

The ranked set lives in memory, because a durable write per score change breaks first, and scores are persisted asynchronously so the set can be rebuilt after a restart.

Watch it run

The animation starts from the constraint: ten million players, thousands of changes a second, and a board never sorted at read time. A score arrives, raj 960; nothing is recounted, and one entry is going to move. The set finds its place with a logarithmic walk and slides it in, from third place to second. Order is now an invariant of the structure, not something a query recreates, so the top hundred is a range read off the front: no scan, no comparison. All of it lives in memory, because a disk write per score change is what breaks first, and the durable copy is written behind the change, not in front of it. Then someone in nine-millionth place asks for their rank; without per-node counts, that means counting everyone above them. So players are also counted per score band, kept as a handful of running totals, and their rank becomes a sum of a few numbers: close, and cheap enough to serve. Exactness is the thing traded away, and only the top of the board ever needed it.

The code

A toy model of the in-memory tier: a dict, a sorted list standing in for the skip list (insort shifts elements, so O(n) here), and band counters. Ties break by name:

from bisect import bisect_left, insort

class Leaderboard:
    def __init__(self, max_score=1_000, band=100):
        self.score = {}                                  # player -> score
        self.ranked = []                                 # (-score, player), kept sorted
        self.band = band
        self.bands = [0] * (max_score // band + 1)       # players per score band

    def update(self, player, new_score):
        old = self.score.get(player)
        if old is not None:                              # remove the old entry first
            self.ranked.pop(bisect_left(self.ranked, (-old, player)))
            self.bands[old // self.band] -= 1
        self.score[player] = new_score
        insort(self.ranked, (-new_score, player))        # the logarithmic walk, in a real set
        self.bands[new_score // self.band] += 1

    def top(self, k):
        return [(p, -s) for s, p in self.ranked[:k]]     # a range read off the front

    def rank(self, player):
        """Exact: 1 + players with a strictly higher score (ties share a rank)."""
        return bisect_left(self.ranked, (-self.score[player], "")) + 1

    def approx_rank(self, player):
        """Bands above, plus the share of the own band assumed (uniformly) to be higher."""
        s = self.score[player]
        b = s // self.band
        within = self.bands[b] * ((b + 1) * self.band - 1 - s) // self.band
        return sum(self.bands[b + 1:]) + within + 1

lb = Leaderboard()
for player, s in [("ada", 980), ("lin", 940), ("raj", 910), ("kim", 420), ("sol", 415)]:
    lb.update(player, s)
lb.update("raj", 960)                                    # the animation's score change
print(lb.top(3))             # [('ada', 980), ('raj', 960), ('lin', 940)]
print(lb.rank("raj"), lb.rank("kim"), lb.approx_rank("kim"))   # 2 4 5

The exact rank above is the list position, which a real skip list gets from its per-link counts. With bounded integer scores there is a second exact option: one-point bands in a Fenwick tree, so "how many scored above s?" is a prefix sum in O(log S) for S possible scores:

class ScoreCounts:
    """Fenwick tree over scores 0..max_score: exact 'how many scored above s' in O(log S)."""
    def __init__(self, max_score):
        self.n = max_score + 1
        self.tree = [0] * (self.n + 1)

    def add(self, s, delta):
        i = s + 1
        while i <= self.n:
            self.tree[i] += delta
            i += i & -i

    def at_most(self, s):
        i, total = s + 1, 0
        while i > 0:
            total += self.tree[i]
            i -= i & -i
        return total

    def rank(self, s):
        return self.at_most(self.n - 1) - self.at_most(s) + 1

counts = ScoreCounts(1_000)
for s in lb.score.values():
    counts.add(s, 1)
print(counts.rank(lb.score["kim"]), counts.rank(lb.score["raj"]))   # 4 2

Checked on 300 seeded random runs of 400 updates against a brute force that sorts every player for each read. The approximate rank must stay within the size of the player's own band, and be exact for one-point bands:

import random

rng = random.Random(31)
ok = True
for _ in range(300):
    lb, counts = Leaderboard(max_score=1_000, band=rng.choice([1, 10, 100])), ScoreCounts(1_000)
    players = [f"p{i}" for i in range(rng.randint(1, 60))]
    for _ in range(400):
        p, s = rng.choice(players), rng.randint(0, 1_000)
        if p in lb.score:
            counts.add(lb.score[p], -1)
        lb.update(p, s)
        counts.add(s, 1)
    board = sorted(lb.score.items(), key=lambda kv: (-kv[1], kv[0]))   # brute force: sort all
    k = rng.randint(1, len(board))
    ok &= lb.top(k) == board[:k]
    for p, s in board:
        exact = 1 + sum(1 for _, t in board if t > s)
        ok &= lb.rank(p) == exact == counts.rank(s)
        ok &= abs(lb.approx_rank(p) - exact) <= lb.bands[s // lb.band]
        if lb.band == 1:
            ok &= lb.approx_rank(p) == exact             # one-point bands are exact
print(ok)                                                # True

The complexity

• Update: O(log n) in a skip list or balanced tree, plus O(1) for the hash map and the band counter.
• Top K: O(log n + K), a range read.
• Exact rank: O(log n) with per-node counts, O(log S) with a Fenwick tree over bounded scores, O(rank) with a plain index.
• Approximate rank: O(B) for B bands, and B is small by design.
• Memory: ten million small entries fit in one machine's memory; shard only when they no longer do.

Where it goes wrong

• Sorting at read time. Any ORDER BY over all players on the read path falls over.
• Ties. Two players on 960 need a rule: the earlier achiever wins, via a timestamp folded into the sort key, or both share a rank.
• Sharding by player without a plan for rank. Top K becomes a merge of each shard's top K, which is cheap, but every rank query becomes a fan-out to every shard.
• Durable writes in the hot path. Persist asynchronously; replay after a crash.
• Resets. Weekly boards are simpler as a new key per period than as millions of deletes.

When it shows up in interviews

As "design a gaming leaderboard", "design a real-time top-K" or inside a contest platform. Follow-ups: rank far down the list, ties, sharding, resets. The algorithmic cousins are top-K with a heap for one-off queries, and top-K frequent elements, whose bucket trick is the same idea as score bands.

How to say it in an interview

"I'd keep the board in memory as a sorted set, a hash map from player to score plus a skip list ordered by score, so an update is a logarithmic remove-and-insert and the top hundred is a range read. Scores are persisted asynchronously so the set can be rebuilt. For a player's rank, a skip list with per-link counts gives an exact answer in log n; if the board is sharded or lives in a database index, I'd keep counts per score band and answer approximately, or use one-point bands in a Fenwick tree if scores are bounded integers. Ties I'd break by who reached the score first."