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.
Follow Up:
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
Reset Code
Full screen
copy-code
Console