Design a Randomized Multiset

Create an integer multiset that allows repeated values and exposes three operations, each with expected $$O(1)$$ cost: insert(val): store one more copy of val; return true when val was not stored before the call, otherwise return false. remove(val): delete one copy of val if it exists; return true when a copy was deleted, otherwise return false. getRandom(): return a stored occurrence sampled uniformly from all occurrences currently in the multiset, so a value with more…