Data Structure Supporting Insert Delete And GetRandom

Easy
0/40
Average time to solve is 15m
profile
Contributed by
12 upvotes
Asked in companies
FlipkartFacebookIntuit

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.
Follow Up: 
Can you implement every operation such that it works in O(1) time?
Detailed explanation ( Input/output format, Notes, Images )
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
Hint

A simple and intuitive approach could be to use a resizable array as the required data structure.

Approaches (2)
Brute Force
  • 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.
Time Complexity

O(N) for Insert, Delete, and Search Operation.
O(1) for GetRandom Operation.

where ‘N’ is the number of elements in the array.

 

In the worst case, insert, remove, and search operations require iterating over the complete array whereas the getRandom operation can be performed in a constant time.

Space Complexity

O(N), where ‘N’ is the number of elements in the array.

 

Since in the worst-case O(N), extra space is required by the array and so, the overall space complexity is O(N).

Code Solution
(100% EXP penalty)
Data Structure Supporting Insert Delete And GetRandom
Full screen
Console