medium

Insert Delete GetRandom O(1)

Design a set of integers supporting insert(x), remove(x) and getRandom(), where getRandom returns a uniformly random element among those currently stored. All three operations must run in average constant time.

Constraints

-2^31 ≤ x ≤ 2^31 - 1
At most 2 · 10^5 operations
getRandom is only called on a non-empty set

Examples

in: insert(1), remove(2), insert(2), getRandom(), remove(1), insert(2), getRandom()

out: true, false, true, 1 or 2, true, false, 2

Code it yourself

Solve in

Your python code

Test execution is not yet available for this exercise.Practice journal →Draft saved in this browser.

Hints:

Which approach applies?

Choose an approach to check your pattern recognition, or reveal the discussion when you need help.