Implement a Random Set data structure that can perform the following operations:

• Constructor(): This initializes the Random Set object.
• Insert(): This function takes an integer, data, as its parameter and, if it does not already exist in the set, add it to the set, returning TRUE. If the integer already exists in the set, the function returns FALSE.
• Delete(): This function takes an integer, data, as its parameter and, if it exists in the set, removes it, returning TRUE. If the integer does not exist in the set, the function returns FALSE.
• GetRandom(): This function takes no parameters. It returns an integer chosen at random from the set.

Note: Your implementation should aim to have a running time of $O(1)$ (on average) for each operation.

Constraints:

• $-2^{31} \leq$ data $\leq 2^{31}$
• No more than $2 \times 10^5$ calls will be made to the Insert(), Delete() and GetRandom() functions.
• There will be at least one element in the data structure when the GetRandom() function is called.

So far, you’ve probably brainstormed some approaches on how to solve this problem. Let’s explore some of these approaches and figure out which one to follow while considering time complexity and any implementation constraints.

The naive approach to solve this problem is by using an array. Elements can be inserted and deleted from an array. Random values from an array can also be fetched by getting a random index first and then retrieving the array element.

The time complexity for this approach will be $O(n)$, but our approach should have a running time of $O(1)$ ...