Live Leaderboard
A fantasy-cricket contest table: add points, show the top k, answer “what is my rank?”.
the brief
What you are building
During an IPL match, a fantasy-cricket app updates every player's points after each ball.
Lakhs of users keep refreshing two screens: the top 10 table and my rank.
Your job: the in-memory leaderboard behind those two screens. Points come in, the table must always be right.
must have
Requirements
addScore(player, points)adds points to the player's total. A new player starts at 0.- The table order: a higher total first. Equal totals go in alphabetical order of the name (
String.compareTo). top(k)returns the bestkplayers in that order. If there are fewer thankplayers, return all of them.rank(player)returns the player's 1-based position in that order, or-1if they are not on the board.reset(player)takes the player off the board. Resetting an unknown player does nothing. If they score again, they start from 0.
the contract
The Java API: class Leaderboard
public Leaderboard()- An empty board.
public void addScore(String player, int points)- Adds
points(≥ 1) to the player's total. public List<String> top(int k)- The best
knames, best first. public int rank(String player)- 1-based position, or
-1. public void reset(String player)- Removes the player from the board.
- 1 ≤ points per call, and a player's total stays ≤ 10⁹ (so it fits in an
int) - 1 ≤ k ≤ 100
- up to 10,000 calls and 1,000 players
- names are non-empty and case-sensitive (
Raviandraviare two players)
example session
Calls in, answers out
Three players, a tie, a comeback and a reset.
| call | returns | why |
|---|---|---|
new Leaderboard() | — | |
addScore("rahul", 50) | — | |
addScore("priya", 70) | — | |
addScore("amit", 50) | — | |
top(2) | ["priya", "amit"] | amit and rahul tie at 50; amit comes first alphabetically |
rank("rahul") | 3 | |
addScore("rahul", 30) | — | rahul now has 80 |
top(3) | ["rahul", "priya", "amit"] | |
rank("neha") | -1 | neha is not on the board |
reset("priya") | — | |
top(5) | ["rahul", "amit"] | k is bigger than the board |
rank("amit") | 2 |
time plan
Your 90 minutes
- 10 minclarify — How are ties broken? Can points be negative? What does
top(k)do when k is bigger than the board? - 10 mindesign — Two questions: what is this player's total? and who is in order? Pick one structure for each, and decide how they stay in sync.
- 40 mincore code —
addScoreandtopfirst, run the example. Thenrankandreset. - 20 minedge cases — Empty board, one player, all tied, reset then score again, very large totals.
- 10 minpolish — Clear names, one comparator in one place. Be ready to discuss making
rankfaster.
Practise under real pressure: a 90-minute clock with the phases above. It keeps running if you reload the page.
your turn
Build it here
Write the whole class in the editor. Run replays the example session; Submit adds the hidden tests (edge cases and large random sessions). Stuck for 20 minutes? Open one hint at a time.
Build Leaderboard in the browser
Design: implement every operation. Compiled by the real javac (Java 17) and judged right here — nothing is sent anywhere.
The reference, the data-structure reasoning and the rubric are hidden so you can build it first. Even a half-working attempt teaches you more than reading a perfect answer.
Opening all three hints also shows it.
reference
One clean way to build it
A HashMap for lookups plus a TreeSet that is always sorted. To change a score: remove, then add.
class Leaderboard { /** An immutable (player, score) pair. To change a score: remove the old entry, add a new one. */ record Entry(String player, int score) {} /** Higher score first; equal scores in alphabetical order of the name. */ private static final Comparator<Entry> ORDER = (a, b) -> a.score() != b.score() ? Integer.compare(b.score(), a.score()) : a.player().compareTo(b.player()); private final Map<String, Entry> byPlayer = new HashMap<>(); // player → current entry: O(1) private final TreeSet<Entry> ranking = new TreeSet<>(ORDER); // always sorted: O(log n) per change public void addScore(String player, int points) { Entry old = byPlayer.get(player); int total = points; if (old != null) { ranking.remove(old); // remove BEFORE the score changes, or the TreeSet cannot find it total += old.score(); } Entry now = new Entry(player, total); byPlayer.put(player, now); ranking.add(now); } public List<String> top(int k) { List<String> result = new ArrayList<>(Math.min(k, ranking.size())); for (Entry e : ranking) { // in order, best first; stop after k: O(k) if (result.size() == k) break; result.add(e.player()); } return result; } public int rank(String player) { Entry e = byPlayer.get(player); if (e == null) return -1; return ranking.headSet(e).size() + 1; // everyone strictly ahead, plus one. O(rank): the view is counted } public void reset(String player) { Entry e = byPlayer.remove(player); if (e != null) ranking.remove(e); }}the choices
Which data structures, and why
HashMap<String, Entry>Player → their current entry. Finds the entry to remove in O(1), and answers "is this player on the board?".
O(1) average per lookup.
TreeSet<Entry> with a comparatorEvery entry, always in table order (a red-black tree inside). top(k) just walks the first k.
add/remove O(log n); top(k) O(k + log n).
record Entry(String player, int score)An immutable pair. Because it cannot change, it cannot silently break the tree's order.
One small object per player.
headSet(e).size() for rankCounts the players ahead. Honest note: Java's tree view counts by walking, so this is O(rank), not O(log n).
O(rank). For O(log n) rank you need an order-statistic tree or a Fenwick tree over scores — a great follow-up to mention.
self-check
Mark yourself like the interviewer would
Tick only what your code really does. Nothing is saved or sent — this is just for you.
your honest self-score: 0 / 100
traps
Common mistakes
- Changing a score while the entry is inside the
TreeSet. The tree is now in the wrong order andremovecannot find the entry any more. Always remove → change → add. - A comparator that returns 0 for two different players with the same score. A
TreeSettreats them as the same element and silently drops one. Break ties by name. - Writing
b.score - a.scorein the comparator. Here scores are never negative, so it happens to be safe — but the day a penalty makes a score negative, the subtraction can overflow and the order breaks.Integer.compare(b.score, a.score)is always safe. - Sorting the whole list on every
topcall and calling it done. Say the cost out loud, then improve it.
what they ask next
Follow-ups and extensions
Make rank O(log n).
Use an order-statistic tree: a balanced BST where every node also stores the size of its subtree. Walking down to my entry, add up the sizes of the subtrees you skip on the left: O(log n). Java has no built-in one, so you would write it. If every possible score is known in advance, a Fenwick tree over the (compressed) scores also counts "players with a higher score" in O(log n); ties by name then need a little extra care.
Show the 5 players just above and below me.
Find my entry, then walk ranking.lower(e) five times and ranking.higher(e) five times. Each step is O(log n).
Lakhs of updates per second. What then?
Batch updates and rebuild the top list every second instead of per ball. Shard players by id across machines, keep a top-k per shard, and merge the small lists with a heap. Redis sorted sets are a common real-world tool for this.
Ties should go to whoever reached the score first.
Add a counter that increases on every addScore, store it in the entry, and compare by it instead of the name.
revise