Problem

Submissions

Solution

New

Discuss

3

Difficulty: EASY

Avg. time to solve

15 min

Success Rate

85%

Problem Statement

Suggest Edit

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

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

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

```
For each query, print the output returned after performing the corresponding operation on the data structure.
```

```
You do not need to print anything, it has already been taken care of. Just implement the given function.
```

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

Console