317/670

317. Insert Delete GetRandom O(1) - Duplicates allowed

Hard

The sequel to Insert Delete GetRandom O(1): same three operations, but now the container is a multiset — the same value may be stored many times.

Design a RandomizedCollection supporting all of these in average O(1) time:

insert(val) — always stores one more copy of val. Return true if the collection did not contain val before this call, false if it already held at least one copy.
remove(val) — delete one occurrence of val if any exists. Return true if a copy was deleted, false if val was absent.
get_random() (getRandom in C++/Java) — return one stored element such that each copy is equally likely: a value stored 3 times among 5 elements is returned with probability 3/5. Only called while the collection is non-empty.

Your class is driven by a scripted sequence of operations. The driver prints the boolean returned by each insert/remove; since random output can't be compared directly, each get_random is validated instead of diffed — the driver prints ok when your returned value currently has at least one stored copy, and bad otherwise. The probability weighting itself isn't graded, but an O(1) design forces the intended structure.

The new difficulty over the distinct-values version: a value no longer lives at one array index, so a single value → index map is not enough.

Example 1:

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

Output: [true, false, true, ok, true, ok]

Explanation: The first insert(1) finds the collection empty of 1s, so it returns true; the second returns false but still stores a second copy, giving [1, 1, 2]. getRandom should now return 1 with probability 2/3 (any stored value is accepted as ok). remove(1) deletes exactly one copy, leaving [1, 2].

Example 2:

Input: insert(7), remove(7), remove(7), insert(7)

Output: [true, true, false, true]

Explanation: The second remove(7) fails because the only copy is already gone; inserting afterwards finds no 7 present, so it returns true again.

Constraints:

-2³¹ ≤ val ≤ 2³¹ - 1
At most 2 × 10⁵ operations in one script.
getRandom is only called while the collection is non-empty.
Every operation must run in O(1) average time.

Hints:

Start from the distinct-values design: a dense array of every stored copy plus a hash map for positions. What breaks? One value now occupies many array slots, so the map must send each value to a *set of indices*, not a single index.

insert: append the copy, add its index to the value's index set, and return whether that set just went from empty to size one.

remove: grab any index i from val's index set, move the array's last element into slot i, then repair the moved value's index set — add i, drop the old tail index. Do those two set updates in that order and the case where the removed value IS the tail value works out by itself.

▶ Run checks these sample cases. Submit also runs hidden edge cases.

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

Expected output: [true, false, true, ok, true, ok]