Problem 418236 · medium · Phase 04 Non-Linear Data Structures

Season Leaderboard With Resets

design · hash map · heap · classes

Design a class Season that keeps the scoreboard of a gaming season:

  • Season() starts with no players.
  • add(player, points) adds points (a positive integer) to player's total. A player who is not on the board yet joins with total 0 first.
  • top(k) returns the sum of the k highest totals on the board. If fewer than k players are on the board, sum all of them (an empty board gives 0).
  • reset(player) removes player from the board (a later add starts them again from 0). Resetting a player who is not on the board does nothing.

Examples

ops:  ["Season", "add", "add", "add", "add", "top", "reset", "top", "top", "add", "top"]
args: [[], ["ana", 40], ["bo", 25], ["cy", 50], ["bo", 30], [2], ["bo"], [2], [5], ["bo", 5], [3]]
Output: [None, None, None, None, None, 105, None, 90, 90, None, 95]
Explanation: bo reaches 55, so the top two are 55 + 50. After the reset the top two are cy and ana (90);
bo comes back with 5, and the top three sum to 50 + 40 + 5.

Constraints

  • 1 <= points <= 1000, 1 <= k <= 10**4, up to 10**4 calls in total
  • Target: add and reset in O(1), top(k) in O(n log k) for n players on the board

Goals

  • Keep running totals per player in a dictionary
  • Sum the k largest totals without sorting everything
Starting Python…