A streamer runs a giveaway. Viewers join and leave the draw at any time, and every so often the streamer draws a winner, who stays in the draw for later rounds. Each viewer is an integer id.
Build RandomizedSet(rng), where rng is a random.Random. Use it for every random choice (for example rng.randrange(k)), never the global random module.
insert(val) -> bool: addvalto the set. ReturnTrueif it was added,Falseif it was already there.remove(val) -> bool: takevalout of the set. ReturnTrueif it was removed,Falseif it wasn't there.get_random() -> int: return a value from the set, each value currently in it equally likely. The value stays in the set. It is only called when the set isn't empty.
Every method should take O(1) time on average.
s = RandomizedSet(random.Random(7))
s.insert(14) # True
s.insert(3) # True
s.insert(14) # False: 14 is already in
s.insert(25) # True
s.remove(8) # False: 8 was never added
s.remove(14) # True
s.get_random() # 3 or 25, each with probability 1/2
Constraints: ids fit in a signed 32-bit integer, and there are up to 2 * 10^5 calls in total.
⭐ Bonus: an O(n) remove or get_random (deleting from the middle of a list, or copying the set into a list to draw from) still passes; a speed test with 100,000 viewers and 100,000 more calls earns a star when every call is O(1).
Show hint
a list makes drawing easy (pick a random index) and a dict makes lookups easy. Keep both: the dict maps each value to its index in the list. To remove from the middle of the list in O(1), move the last item into the gap.