Data Structure Supporting Insert Delete And GetRandom

Posted: 26 Dec, 2020
Difficulty: Easy

PROBLEM STATEMENT

Try Problem

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
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.
Try Problem