DSA · Design · #85
Insert Delete GetRandom O(1)
Module 57 · difficulty 3/5·⏱ 30:00starts on first keystroke
Implement the `RandomizedSet` class that supports inserting, removing, and returning a random element, all in average O(1) time. - `RandomizedSet()` initializes the empty set. - `insert(val)` inserts `val` if not already present. Returns `true` if it was inserted, `false` if it was already there. - `remove(val)` removes `val` if present. Returns `true` if it was removed, `false` if it was absent. - `getRandom()` returns a uniformly random element currently in the set. It is guaranteed that at least one element exists when `getRandom` is called. Implement the class named `RandomizedSet`.
Examples
insert(1), remove(2), insert(2), getRandom(), remove(1), insert(2), getRandom()→true, false, true, 2 or 1, true, false, 2— After insert(1): {1}. remove(2): absent -> false. insert(2): {1,2}. getRandom: 1 or 2. remove(1): {2}. insert(2): already there -> false. getRandom: only 2 remains.insert(0), insert(0)→true, false— Second insert of 0 is a no-op since it already exists.remove(5)→false— Removing from an empty set returns false.
Constraints
- · -2^31 <= val <= 2^31 - 1
- · At most 2 * 10^5 calls in total to insert, remove, and getRandom.
- · getRandom is only called when there is at least one element in the set.
- · insert, remove, and getRandom must each run in average O(1) time.
Session phases
A · Clarify
B · Approach
C · Complexity
D · Edges
E · Code
F · Tradeoff
G · Score
Phase A — Clarify
Ask questions about input bounds, types, and edge constraints.
Ask the coach clarifying questions about the problem.
When you've covered this phase, advance to the next.