Quick Overview

This question evaluates the ability to design efficient dynamic data structures and algorithms for maintaining per-player state and a real-time leaderboard, including score aggregation, room transitions, and high-throughput updates.

Design room progression with leaderboard

Company: Uber

Role: Machine Learning Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Onsite

Design a data structure to simulate a sequence of rooms where players solve tasks and can move only to the next room once finished. Support the following operations with high throughput: addPlayer(id); recordTask(playerId, roomId, points); moveToNextRoom(playerId); getPlayerState(playerId) -> {room, score}; and topK(k) -> the k players with highest total scores across all rooms at query time. Implement efficient updates to the leaderboard and explain how you will prevent duplicate entries when using a heap (e.g., lazy deletion, versioning, or indexed heaps). Analyze the time and space complexity of each operation and justify your design choices.

Quick Answer: This question evaluates the ability to design efficient dynamic data structures and algorithms for maintaining per-player state and a real-time leaderboard, including score aggregation, room transitions, and high-throughput updates.

Design a data structure that simulates a sequence of rooms where players solve tasks and may move only to the next room once they finish the current one. You will process a list of `operations` and return the outputs of the query operations in order. Implement a function `solution(operations)` that processes the following operation tuples: - `('addPlayer', id)` — register a new player. Each player starts in room `0` with a total score of `0`. Adding an existing id is a no-op (idempotent). - `('recordTask', playerId, roomId, points)` — award `points` to the player **only if** `roomId` equals the player's current room (you cannot score in a room you have already left or not yet reached). The points add to the player's running total across all rooms. - `('moveToNextRoom', playerId)` — advance the player to the next room (increment their room index by 1). - `('getPlayerState', playerId)` — append `{'room': r, 'score': s}` to the result list. If the player does not exist, append `None`. - `('topK', k)` — append a list of the `k` player ids with the highest total scores at query time, highest first. Break ties by smaller id. If fewer than `k` players exist, return all of them. Return the list of outputs produced by `getPlayerState` and `topK`, in the order they were called. **Leaderboard requirement:** keep `topK` efficient as scores update. Because a binary heap cannot update a key in place, a naive re-push leaves duplicate (stale) entries for the same player. Prevent duplicates using lazy deletion with version stamps: every score change bumps the player's version and pushes a fresh `(-score, id, version)` entry; at query time pop entries whose version no longer matches the player's current version and discard them. **Example:** `addPlayer 1`, `addPlayer 2`, `recordTask 1 0 50`, `recordTask 2 0 30`, `getPlayerState 1`, `topK 2` returns `[{'room': 0, 'score': 50}, [1, 2]]`.

Constraints

  • Player ids and room ids are non-negative integers.
  • recordTask only counts when roomId equals the player's current room.
  • topK breaks score ties by smaller player id and returns all players when k exceeds the player count.
  • Operations referencing unknown players are ignored (getPlayerState returns None).
  • 1 <= number of operations <= 10^5

Examples

Input: ([('addPlayer', 1), ('addPlayer', 2), ('recordTask', 1, 0, 50), ('recordTask', 2, 0, 30), ('getPlayerState', 1), ('topK', 2)],)

Expected Output: [{'room': 0, 'score': 50}, [1, 2]]

Explanation: Both players score in room 0. getPlayerState(1) reports room 0, score 50. topK(2) ranks player 1 (50) above player 2 (30).

Input: ([('addPlayer', 5), ('recordTask', 5, 0, 10), ('moveToNextRoom', 5), ('recordTask', 5, 1, 25), ('getPlayerState', 5)],)

Expected Output: [{'room': 1, 'score': 35}]

Explanation: Player 5 scores 10 in room 0, moves to room 1, scores 25 there. Total score 35 accumulates across rooms; current room is 1.

Hints

  1. Track three maps keyed by player id: current room, total score, and a version counter.
  2. For recordTask, guard on roomId == current room before adding points — a player can only score in the room they currently occupy.
  3. A binary heap can't decrease-key in place. Re-push a fresh (-score, id, version) entry on every score change and skip any popped entry whose version no longer matches the player's current version (lazy deletion).
  4. During topK, pop valid entries into a buffer (dedup with a 'seen' set) until you have k, then push the valid entries back so the heap is preserved. Ordering by (-score, id) gives highest-score-first with smaller-id tie-breaking.

Loading coding console...