3

# Data Structure Supporting Insert Delete And GetRandom

Difficulty: EASY
Avg. time to solve
15 min
Success Rate
85%

Problem Statement
Suggest Edit

#### Design and implement a data structure which supports the following operations:

``````insert(X): Inserts an element X in the data structure and returns true if the element was not present, and false otherwise.

remove(X): Removes the element X from the data structure, if present. Returns true if the element was present and false otherwise.

search(X): Search the element X in the data structure. Returns true if the element was present and false otherwise.

getRandom(): Return a random element present in the data structure.
``````

#### Four types of queries denote these operations:

``````Type 1: for insert(X) operation.
Type 2: for remove(X) operation.
Type 3: for search(X) operation.
Type 4: for getRandom() operation.
``````
##### Note:
``````It is guaranteed that at least one element will be present in the data structure when getRandom() operation is performed.
``````
``````Can you implement every operation such that it works in O(1) time?
``````
##### Input format:
``````The first line of input contains an integer ‘Q’ denoting the number of queries.

The next ‘Q’ lines specify the type of operation/query to be performed on the data structure. Each query contains an integer ‘P’ denoting the type of query.

For queries of type 1, 2 and 3 the integer ‘P’ is followed by another integer ‘X’.
``````
##### Output format:
``````For each query, print the output returned after performing the corresponding operation on the data structure.
``````
##### Note:
``````You do not need to print anything, it has already been taken care of. Just implement the given function.
``````
##### Constraints:
``````1 <= Q <= 10^5
1 <= P <= 4
-10^5 <= X <= 10^5

Time Limit: 1 sec
``````
##### Sample Input 1:
``````5
1 10
1 20
1 10
4
3 20
``````
##### Sample Output 1:
``````True
True
False
10
True
``````
##### Explanation 1:
``````Initially, our DS is empty. The number of operations we need to perform are 5.
The first operation is of type 1 i.e. insert(10) into the DS. Since 10 is not present, so we can insert it. Hence, the new state of our structure is [10]. Return True.

The second operation is of type 2 i.e. insert(20) into the DS. Since 20 is not present, so we can insert it. Hence, the new state of our structure is [10, 20]. Return True.

The third operation is of type 1 i.e. insert(10) into the DS. Since 10 is already present, so we don’t insert it. Hence, the state of our structure remains the same, i.e [10, 20]. Return False.

The fourth operation is of type 4 i.e. getRandom(). So, return a random element which is present in the data structure.

The fifth operation is of type 3 i.e. remove(10) from the DS. Since 10 is present, so we can remove it. Hence, the new state of our structure is [10]. Return True.
``````
##### Sample Input 2:
``````6
2 52
1 66
1 89
1 78
3 60
2 89
``````
##### Sample Output 2:
``````False
True
True
True
False
True
``````
Console