Solution: Insert Delete GetRandom O(1)

Explore how to design a custom data structure that supports insert, delete, and getRandom operations in average constant time. Understand the use of arrays combined with hash maps to achieve efficient element storage, quick lookups, and constant-time random access. This lesson guides you through the trade-offs and implementation details for building scalable and performant solutions to this common coding interview challenge.

We'll cover the following...

Statement
Solution
- Naive approach
- Optimized approach using an array and a hash map

Statement

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$

...