Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding
Ninjas X Naukri.com

Problem of the day

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.
```

```
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

```
1 <= Q <= 10^5
1 <= P <= 4
-10^5 <= X <= 10^5
Time Limit: 1 sec
```

```
5
1 10
1 20
1 10
4
3 20
```

```
True
True
False
10
True
```

```
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.
```

```
6
2 52
1 66
1 89
1 78
3 60
2 89
```

```
False
True
True
True
False
True
```