You run a lucky draw. The coupon numbers are kept in a box. You must be able to add a coupon, remove a coupon, and pull out one coupon at random. A number is never kept twice.
Write a class RandomizedSet with these methods:
RandomizedSet(): make an empty set.insert(val): add val if it is not in the set yet. Return true if it was added. Return false if it was already there.remove(val): take val out if it is in the set. Return true if it was removed. Return false if it was not there.getRandom(): return one number from the set, picked at random. Every number in the set must have the same chance of being picked.
Every method must run in O(1) average time.
Examples
Example 1:
Input
["RandomizedSet", "insert", "insert", "insert", "remove", "getRandom", "remove", "insert"]
[[], [7], [7], [3], [7], [], [9], [3]]
Output
[null, true, false, true, true, 3, false, false]
Explanation
insert(7) adds 7. The second insert(7) returns false, because 7 is already there.
insert(3) adds 3. remove(7) takes 7 out.
The set is now {3}, so getRandom() can only return 3.
remove(9) returns false, because 9 was never added. insert(3) returns false, because 3 is already there.
Example 2:
Input
["RandomizedSet", "insert", "getRandom", "remove", "insert", "getRandom", "insert"]
[[], [12], [], [12], [-5], [], [-5]]
Output
[null, true, 12, true, true, -5, false]
Explanation
The set is {12}, so getRandom() returns 12.
After remove(12) and insert(-5), the set is {-5}, so getRandom() returns -5.
The last insert(-5) returns false.
Note for this judge: a random answer can not be compared with one fixed expected output. So the tests call getRandom() only when the set holds exactly one element.