How do I practice coding and algorithm questions?

Use PracHub's coding console to write, test, and debug your solutions in Python or JavaScript. View hints, test against sample inputs, and compare with official solutions.

What difficulty level is this coding question?

This is a medium difficulty Coding & Algorithms question, commonly asked during Technical Screen rounds at Uber.

What role is this question designed for?

This question is commonly asked for Frontend Engineer candidates at Uber during technical interviews.

Implement a Constant-Time Random Pool

Quick Overview

This question evaluates a candidate's ability to design and implement an efficient data structure supporting average O(1) add, remove, and uniform random selection, testing concepts such as hashing, random sampling, and space–time trade-offs within the Coding & Algorithms domain.

Company: Uber

Role: Frontend Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Technical Screen

Design a data structure `RandomPool` that stores unique integers and supports the following operations in average `O(1)` time: `add(value)`, which inserts `value` if it is not already present and returns whether an insertion happened; `remove(value)`, which removes `value` if present and returns whether a removal happened; and `pickRandom()`, which returns one currently stored value uniformly at random. If the pool is empty, define and document a reasonable behavior such as returning `null` or throwing an exception. Use `O(n)` extra space.

Quick Answer: This question evaluates a candidate's ability to design and implement an efficient data structure supporting average O(1) add, remove, and uniform random selection, testing concepts such as hashing, random sampling, and space–time trade-offs within the Coding & Algorithms domain.

Design a data structure for unique integers that supports add, remove, and random selection in average O(1) time. To make the problem testable in a deterministic way, you will process a batch of operations. Maintain the pool using the following exact rules: - add(x): If x is not already present, append it to the end of the internal array and return "true". Otherwise return "false". - remove(x): If x is present, remove it in O(1) time by swapping it with the last element of the internal array, updating any stored index, and then popping the last element. Return "true". If x is not present, return "false". - pickRandom(r): In a real RandomPool, this would return a uniformly random stored value. For deterministic grading, if the pool is non-empty, return the value at index (r % current_size) of the current internal array. If the pool is empty, return "null". Given two arrays, operations and values, where operations[i] is one of "add", "remove", or "pickRandom", and values[i] is the integer argument for that operation, return a list of string results for all operations in order. This problem tests whether you can combine an array with a hash map to achieve constant-time updates and selection.

Constraints

1 <= len(operations) == len(values) <= 200000
-10^9 <= values[i] <= 10^9
operations[i] is one of: "add", "remove", "pickRandom"
All operations should run in average O(1) time
Use O(n) extra space, where n is the number of stored values

Examples

Input: (["add", "add", "add", "remove", "pickRandom", "add", "remove", "pickRandom"], [10, 20, 30, 20, 1, 40, 10, 2])

Expected Output: ["true", "true", "true", "true", "30", "true", "true", "40"]

Explanation: After removing 20, the pool becomes [10, 30]. pickRandom(1) returns index 1 -> 30. After adding 40 and removing 10 by swap-with-last, the pool becomes [40, 30]. pickRandom(2) uses 2 % 2 = 0 -> 40.

Input: (["pickRandom", "remove", "add", "add", "pickRandom", "remove", "pickRandom"], [5, 1, 1, 1, 0, 1, 7])

Expected Output: ["null", "false", "true", "false", "1", "true", "null"]

Explanation: The first pickRandom happens on an empty pool, so it returns "null". Adding 1 twice only inserts once. After removing 1, the pool is empty again.

Input: (["add", "add", "add", "remove", "pickRandom", "remove", "pickRandom"], [-1, 0, 2, -1, 3, 2, 4])

Expected Output: ["true", "true", "true", "true", "0", "true", "0"]

Explanation: After removing -1 by swapping with the last element, the pool becomes [2, 0]. pickRandom(3) uses index 1 -> 0. Removing 2 leaves [0], so the final pickRandom also returns 0.

Input: (["add", "remove", "add", "pickRandom", "remove", "pickRandom"], [8, 8, 9, 10, 10, 1])

Expected Output: ["true", "true", "true", "9", "false", "9"]

Explanation: Adding and then removing 8 leaves the pool empty. After adding 9, pickRandom always returns 9 because it is the only element. Removing 10 fails because 10 is not present.

Hints

Use a hash map from value to its index in a dynamic array.
To remove in O(1), swap the element to delete with the last array element, update the moved element's index, and then pop the array.

Quick Overview