~/problems / Binary search / Sorted containers (bisect)

OA: Game leaderboard

medium 3 levels ~70 min

Level 1 Scores and the top list

Build Leaderboard for an online game. Every method takes a timestamp (an integer, milliseconds) first. Timestamps strictly increase from one call to the next. Level 1 doesn't need them, but later levels do.

  • add_score(timestamp, player, points) -> int: add points (a positive integer) to the player's score and return the new score. A player who hasn't scored before joins the board with a score of 0 first.
  • get_score(timestamp, player) -> int | None: the player's current score, or None if they aren't on the board.
  • top(timestamp, k) -> list[str]: the first k players in board order, each written as "name(score)". Board order is higher score first; equal scores are ordered by name, smaller string first. With fewer than k players, return them all. k may be 0.
lb = Leaderboard()
lb.add_score(1, "mia", 40)   # 40
lb.add_score(2, "leo", 25)   # 25
lb.add_score(3, "ava", 40)   # 40
lb.add_score(4, "leo", 10)   # 35
lb.get_score(5, "leo")       # 35
lb.get_score(6, "zoe")       # None
lb.top(7, 2)                 # ["ava(40)", "mia(40)"]   tie on 40: "ava" < "mia"
lb.top(8, 10)                # ["ava(40)", "mia(40)", "leo(35)"]

At this level there are at most a few hundred players, so sorting them for each top call is fine.

Show hint

A dictionary from name to score covers the first two methods. For top, sort by the pair (-score, name).

Level 2 unlocks when level 1 passes.

Level 3 unlocks when level 2 passes.

Topic: Sorted containers (bisect). Ordered-set operations in Python: bisect.insort, floor/ceiling lookups.

Read the visual guide
0:00
Ctrl ' run · Ctrl ↵ submit
esc