# Data Structure Supporting Insert Delete And GetRandom

Easy
0/40
Average time to solve is 15m
Contributed by

## Problem statement

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?
``````
Detailed explanation ( Input/output format, Notes, Images )
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