# Data Structure Supporting Insert Delete And GetRandom

Posted: 26 Dec, 2020
Difficulty: Easy

## 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?
``````
##### 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
`````` Approach 1
• The idea is to use a resizable array to store the elements currently present in the data structure.
• The required operations can be implemented as follows:
• Type 1: Insert('X') Operation:
• Search if the element is present in the array or not.
• If the element is present, then no need to perform the operation.
• Otherwise, simply insert ‘X’ into the array.
• Type 2: Remove('X') Operation:
• Search if the element is present in the array or not.
• If the element is not present, then no need to perform the operation.
• Otherwise, find the position of element ‘X’ in the array.
• Remove ‘X’, by shifting all the elements, present after the element ‘X’, one position towards the left.
• Then remove the last element.
• Type 3: Search('X') Operation:
• Search operation can be performed by iterating over the array to check whether element ‘X’ is present in the array or not.
• Type 4: getRandom() Operation:
• Generate a random index value.
• Return the element present at the corresponding index in the array.