PracHub
QuestionsCoachesLearningGuidesInterview Prep
|Home/Coding & Algorithms/xAI

Constant-Time Insert, Remove, and Uniform Random Sampling

Last updated: Jul 2, 2026

Constant-Time Insert, Remove, and Uniform Random Sampling

Company: xAI

Role: Machine Learning Engineer

Category: Coding & Algorithms

Difficulty: hard

Interview Round: Onsite

A data-sampling service maintains a dynamically changing pool of integer example IDs. Examples are continuously added and retired, and the service must repeatedly draw a uniformly random example from the current pool. All three operations must run in **average O(1)** time. Implement a class `RandomizedPool` supporting: - `insert(val)` — inserts `val` into the pool if it is not already present. Returns `true` if `val` was inserted, `false` if it was already present. - `remove(val)` — removes `val` from the pool if it is present. Returns `true` if `val` was removed, `false` if it was not present. - `getRandom()` — returns a uniformly random element from the current pool. Each element currently in the pool must have an **equal probability** of being returned. `getRandom` is only called when the pool is non-empty. The pool contains no duplicates: inserting a value that is already present is a no-op (returning `false`). **Example** ``` pool = RandomizedPool() pool.insert(1) -> true (pool = {1}) pool.remove(2) -> false (2 not present; pool = {1}) pool.insert(2) -> true (pool = {1, 2}) pool.getRandom() -> 1 or 2, each with probability 1/2 pool.remove(1) -> true (pool = {2}) pool.insert(2) -> false (2 already present; pool = {2}) pool.getRandom() -> 2 (only element) ``` **Constraints** - `-2^31 <= val <= 2^31 - 1` - At most `2 * 10^5` calls in total will be made across `insert`, `remove`, and `getRandom` - `getRandom` is called only when the pool contains at least one element - All three operations must run in **average O(1)** time — solutions that take O(n) per operation (for example, scanning a list to remove an element, or converting a hash set to a list on every `getRandom` call) are not acceptable

Related Interview Questions

  • Flatten and unflatten nested Python structures - xAI (nan)
  • Compute dasher pay from order events - xAI (nan)
  • Compute total active time per Twitter Space - xAI (medium)
  • Design a Recoverable Iterator - xAI (medium)
  • Implement Distributed Matrix Multiplication - xAI (hard)
|Home/Coding & Algorithms/xAI

Constant-Time Insert, Remove, and Uniform Random Sampling

xAI logo
xAI
May 30, 2025, 12:00 AM
hardMachine Learning EngineerOnsiteCoding & Algorithms
0
0

A data-sampling service maintains a dynamically changing pool of integer example IDs. Examples are continuously added and retired, and the service must repeatedly draw a uniformly random example from the current pool. All three operations must run in average O(1) time.

Implement a class RandomizedPool supporting:

  • insert(val) — inserts val into the pool if it is not already present. Returns true if val was inserted, false if it was already present.
  • remove(val) — removes val from the pool if it is present. Returns true if val was removed, false if it was not present.
  • getRandom() — returns a uniformly random element from the current pool. Each element currently in the pool must have an equal probability of being returned. getRandom is only called when the pool is non-empty.

The pool contains no duplicates: inserting a value that is already present is a no-op (returning false).

Example

pool = RandomizedPool()
pool.insert(1)     -> true   (pool = {1})
pool.remove(2)     -> false  (2 not present; pool = {1})
pool.insert(2)     -> true   (pool = {1, 2})
pool.getRandom()   -> 1 or 2, each with probability 1/2
pool.remove(1)     -> true   (pool = {2})
pool.insert(2)     -> false  (2 already present; pool = {2})
pool.getRandom()   -> 2      (only element)

Constraints

  • -2^31 <= val <= 2^31 - 1
  • At most 2 * 10^5 calls in total will be made across insert , remove , and getRandom
  • getRandom is called only when the pool contains at least one element
  • All three operations must run in average O(1) time — solutions that take O(n) per operation (for example, scanning a list to remove an element, or converting a hash set to a list on every getRandom call) are not acceptable

Submit Your Answer to Earn 20XP

Sign in to leave a comment

Loading comments...

Browse More Questions

More Coding & Algorithms•More xAI•More Machine Learning Engineer•xAI Machine Learning Engineer•xAI Coding & Algorithms•Machine Learning Engineer Coding & Algorithms
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.