Design a Set with $O(1)$ `insert`, `remove`, and `getRandom`
Design a data structure that supports inserting a value, removing a value, and getting a random element, all in $O(1)$ average time. This requires combining an Array and a Hash Map.
Why Interviewers Ask This
Google interviewers ask this to evaluate your ability to balance time and space complexity trade-offs. They specifically test if you understand that Arrays provide O(1) random access while Hash Maps offer O(1) lookups, but neither alone supports efficient removal from the middle without shifting elements or scanning. This question probes your depth in combining data structures to solve constraints that a single structure cannot handle.
How to Answer This Question
1. Clarify requirements: Confirm that 'average' O(1) is acceptable and that duplicates are not allowed unless specified. 2. Propose the hybrid approach: Explain that you will use a dynamic array (or list) for storage to enable constant-time random access via index, paired with a hash map mapping values to their indices. 3. Detail Insertion: Describe adding the value to the end of the array and storing its index in the map. 4. Explain Removal Strategy: Highlight the critical trick of swapping the element to be removed with the last element in the array before popping it, then updating the map entry for the swapped element. 5. Discuss Random Access: Reiterate that picking a random index from the array yields an O(1) result. 6. Analyze Complexity: Explicitly state that all three operations remain O(1) on average due to these mechanisms.
Key Points to Cover
- Explicitly stating the need to swap the target element with the last element during removal
- Explaining how the hash map tracks indices to allow O(1) lookup after the swap
- Clarifying that duplicates are typically excluded in standard set implementations
- Acknowledging the distinction between worst-case O(1) and average O(1) due to hash collisions
- Demonstrating awareness of space complexity being linear relative to the number of elements
Sample Answer
To achieve O(1) for insert, remove, and getRandom, I would combine a dynamic array with a hash map. The array allows us to access any element by index in constant time, which solves the getRandom requirement. However, re…
Common Mistakes to Avoid
- Attempting to remove an element by shifting all subsequent items in the array, resulting in O(n) removal time
- Using only a hash map without an array, which makes retrieving a random element inefficient as it requires iterating keys
- Failing to update the hash map when swapping elements, leading to incorrect indices and runtime errors
- Overlooking edge cases like removing the last element or inserting into an empty set without proper checks
Sound confident on this question in 5 minutes
Answer once and get a 30-second AI critique of your structure, content, and delivery. First attempt is free — no signup needed.