Insert Delete GetRandom O(1)
On this page
Problem statement
Design a set of integers with three operations, each in O(1) average time:
insert(val)adds val and returns true if it was not already present;remove(val)deletes val and returns true if it was present;getRandom()returns a uniformly random element of the current set.getRandomis only called when the set is non-empty.
A favorite "combine two structures" design question: each obvious structure gives you two of the three operations, and the trick is a small swap that gets you the third. Original problem: LeetCode 380.
Example

insert(10) -> true
insert(20) -> true
insert(30) -> true
insert(20) -> false # already there
remove(10) -> true
getRandom() -> 20 or 30, each with probability 1/2
Constraints (assumed)
- Up to 2 × 10⁵ calls; values fit in a 32-bit integer.
What this question tests
- Knowing what each structure gives: a hash map finds a value, an array allows random access by index.
- The swap-with-last trick that removes from the middle of an array in O(1).
- Keeping two structures consistent, including the edge case where they overlap.
Questions to ask first
- Are duplicates allowed? (Here: no, it is a set. With duplicates it becomes the follow-up.)
- Must getRandom be exactly uniform? (Here: yes.)
- Does the order of elements matter? (No, which is what makes the swap legal.)
- Is "O(1)" average or worst case? (Average; hash maps are O(1) on average.)
Try it yourself first
You have the full problem. Sketch your answer, then sign up free to read the complete walkthrough.
- The complete design, flow by flow, with pictures
- Deep dives into the hard parts
- What mid, senior and staff candidates are expected to say
- Full company question lists
Free forever. No card needed.