Insert Delete GetRandom O(1) - Duplicates Allowed

Design a data structure that supports inserting and removing integers (including duplicates) and returning a random element, all in O(1) average time. Each element must have equal probability of being returned by getRandom.

Implement a function that processes an array of operations and an array of arguments:

• "RandomizedCollection" — Initializes the collection.
• "insert" — Inserts val into the collection. Returns true if val was not already present, false if it was.
• "remove" — Removes one occurrence of val from the collection. Returns true if val was present, false otherwise.
• "getRandom" — Returns a random element. Each element (including duplicates) must have equal probability.

Examples

Example 1:

Input: operations = ["RandomizedCollection","insert","insert","insert","remove","getRandom"], args = [[],[1],[1],[2],[1],[]]

Output: [null,true,false,true,true,1]

Explanation: Insert 1 (new→true), insert 1 again (dup→false), insert 2 (new→true). Remove one 1 (→true). Collection is [1,2]. getRandom must return 1 (only one left if 2 wasn't the answer — here collection has equal 1s and 2s; getRandom=1 in this deterministic test).

Example 2:

Input: operations = ["RandomizedCollection","insert","insert","insert","remove","remove","getRandom"], args = [[],[1],[1],[1],[1],[1],[]]

Output: [null,true,false,false,true,true,1]

Explanation: Insert 1 three times. Remove 1 twice. One 1 remains. getRandom returns 1.

Constraints

• -2^31 <= val <= 2^31 - 1
• At most 2 * 10^5 calls to insert, remove, and getRandom
• There will be at least one element when getRandom is called