DIY: Insert Delete GetRandom O(1) - Duplicates Allowed

Problem statement

Implement a set data structure that allows duplicates and can perform the following operations:

The obj parameter being passed as an argument in the insert(), remove() ,and get_random() methods refers to the struct object.

• insert(obj, data): This function should insert data into the set (if the set does not contain it already). It should return false if the data already exists in the set. Otherwise, it should return true.
• remove(obj, data): If the data is present, this function should remove data from the set and return true. If the data does not exist in the set, the function should return false.
• get_random(obj): This function should return a random element from the set in constant time.

Note: Your implementation should aim for constant running time (on average) for each operation.

Constraints

• $-2^{31}$ <= value <= $2^{31} - 1$
• At most $2 * 10^{5}$ calls in total will be made to insert(), remove(), and get_random().
• There will be at least one element in the data structure to call get_random().

Input

You will insert, delete and get the random values using the insert(), remove() ,and get_random() methods of the module respectively. Let’s see how to insert, delete and get the random values below:

insert(1)
insert(1)
insert(2)
get_random()
remove(1)
remove(1)
insert(1)
insert(2)
insert(3)
get_random()
remove(2)
remove(2)

Output

The following is the output of the above input:

true
false
true
1 or 2
true	
true
true
false
true
1 or 2 or 3	
true
true

Coding exercise

Implement the RandomizedCollection module and initialize its empty object. Create three methods insert(), remove(), and get_random() of RandomizedCollection module. The insert() and remove() methods return true or false, and the get_random() method return integer number.