Design set with O(1) random access
Company: Google
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
Design a data structure ("FancySet") that stores unique integers and supports the following operations, each in average O(1) time:
- `add(x)`: Insert value `x` if it is not already present. Return whether the insert happened.
- `delete(x)`: Remove value `x` if it exists. Return whether a deletion happened.
- `getRandom()`: Return a uniformly random element currently in the set.
Requirements / follow-ups:
- All operations should be average O(1).
- Handle corner cases such as calling `getRandom()` on an empty set (define and justify behavior).
- Discuss how you would make this data structure thread-safe. Compare using a single lock for the whole set vs finer-grained locking (e.g., element-level locks), and explain trade-offs.
Quick Answer: This question evaluates skill in designing a composite data structure that supports average O(1) insertion, deletion, and uniform random access, and tests understanding of hashing, indexing, randomness, and concurrency control.
Design a data structure called FancySet that stores unique integers and supports these operations in average O(1) time: add(x), delete(x), and getRandom(). For this coding problem, implement a function `solution(operations, values, seed)` that simulates a newly created empty FancySet and returns the result of every operation.
Use the standard dynamic-array + hash-map behavior:
- Store current elements in an array-like list.
- Store each element's current index in a hash map.
- When deleting an element that is not at the end of the list, move the last element into the removed slot, then pop the last slot.
To make test cases deterministic, `getRandom()` does not use the language's built-in RNG. Instead, keep an internal 32-bit state initialized to `seed`. When `getRandom()` is called on a non-empty set, update the state with:
`state = (1664525 * state + 1013904223) mod 2^32`
and return the element at index `state % current_size` from the current internal list.
If `getRandom()` is called on an empty set, return `None` and do not advance the state.
In a real interview, picking a random index from the array gives uniform random access; the fixed generator above is only for reproducible grading.
Follow-up discussion (not graded by the code runner): explain how you would make FancySet thread-safe, and compare using one lock for the whole structure versus finer-grained locking.
Constraints
- 1 <= len(operations) <= 2 * 10^5
- len(values) == len(operations)
- Each operation is one of 'add', 'delete', or 'getRandom'
- For 'add' and 'delete', values[i] contains exactly one integer; for 'getRandom', values[i] is []
- -10^9 <= x <= 10^9
- All operations should run in O(1) average time
Examples
Input: (['add','add','getRandom','delete','getRandom','add','getRandom'], [[1],[2],[],[1],[],[2],[]], 7)
Expected Output: [True, True, 1, True, 2, False, 2]
Explanation: After inserting 1 and 2, the first deterministic random choice picks index 0, so it returns 1. Deleting 1 leaves only 2. Adding 2 again fails because it is already present.
Input: (['getRandom','add','add','delete','delete','getRandom'], [[],[5],[5],[7],[5],[]], 1)
Expected Output: [None, True, False, False, True, None]
Explanation: Calling getRandom on an empty set returns None. Adding 5 twice inserts it only once. Deleting 7 fails because it is not present. After deleting 5, the set becomes empty again.
Hints
- You need both fast membership/index lookup and fast access by numeric position. What two data structures combine to give that?
- Deleting from the middle of an array is expensive unless you replace the removed element with the last element and update that last element's stored index.