PracHub
QuestionsCoachesLearningGuidesInterview Prep

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.

  • Medium
  • Uber
  • Coding & Algorithms
  • Machine Learning Engineer

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.

Input: ([('addPlayer', 1), ('addPlayer', 2), ('addPlayer', 3), ('recordTask', 1, 0, 100), ('recordTask', 2, 0, 100), ('recordTask', 3, 0, 40), ('topK', 2)],)

Expected Output: [[1, 2]]

Explanation: Players 1 and 2 tie at 100; the tie is broken by smaller id, so the order is [1, 2] and player 3 (40) is excluded from the top 2.

Input: ([('recordTask', 9, 0, 5), ('getPlayerState', 9), ('topK', 3)],)

Expected Output: [None, []]

Explanation: Player 9 was never added, so recordTask is ignored, getPlayerState returns None, and topK returns an empty list.

Input: ([('addPlayer', 7), ('recordTask', 7, 0, 20), ('recordTask', 7, 0, 30), ('recordTask', 7, 1, 999), ('moveToNextRoom', 7), ('recordTask', 7, 1, 15), ('getPlayerState', 7), ('topK', 1)],)

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

Explanation: While in room 0, player 7 gains 20+30=50; the recordTask for room 1 (999) is ignored because the player is still in room 0. After moving to room 1, the 15 counts. Total 50+15=65.

Input: ([('addPlayer', 1), ('addPlayer', 1), ('recordTask', 1, 0, 10), ('topK', 5)],)

Expected Output: [[1]]

Explanation: The second addPlayer(1) is a no-op (idempotent). topK with k=5 returns all existing players — just [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.
Last updated: Jun 26, 2026

Loading coding console...

PracHub

Master your tech interviews with 8,000+ real questions from top companies.

Product

  • Questions
  • Learning Tracks
  • Interview Guides
  • Resources
  • Premium
  • For Universities
  • Student Access

Browse

  • By Company
  • By Role
  • By Category
  • Topic Hubs
  • SQL Questions
  • AI Coding Questions
  • Compare Platforms
  • Discord Community

Support

  • support@prachub.com
  • (916) 541-4762

Legal

  • Privacy Policy
  • Terms of Service
  • About Us

© 2026 PracHub. All rights reserved.

Related Coding Questions

  • Deep Equality of Two Records - Uber (medium)
  • Shortest Path in a Grid with Blocked Cells - Uber (medium)
  • Design and Implement an LRU Cache - Uber (medium)
  • Reconstruct the Alphabet Order of an Alien Language - Uber (medium)
  • Maximize Throughput and Count Trigger Components - Uber (medium)