Last Updated: 26 Dec, 2020
Data Structure Supporting Insert Delete And GetRandom
Easy
Asked in companies
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
Approaches
- 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.
- The previous approach required searching over the complete array to check if an element is present in the array or not.
- This can be avoided by the use of hashing.
- The idea is to use a hash map along with the resizable array.
- The array will store the set of elements currently present in the data structure and the hash map will store the indices corresponding to each element present in the array, i.e. the array values act as keys and the array index act as value (for the hash map).
- So, the required operations can be implemented as follows:
- Type 1: Insert('X') Operation:
- Check if the element ‘X’ is present in the array or not. This can be done by performing a lookup on the hash map.
- If the element is present, then no need to perform the operation.
- Otherwise, simply insert ‘X’ into the array.
- Type 2: Remove('X') Operation:
- Check if element ‘X’ is present in the array or not. This can be done by performing a lookup on the hash map.
- If the element is not present, then no need to perform the operation.
- Otherwise, find the position of element ‘X’ in the array using the hash map.
- Remove the element from the hash map.
- Swap the element with the last element in the array.
- Update the index of the last element in the hash map.
- Then remove the last element, i.e. ‘X’, from the array.
- Type 3: Search('X') Operation:
- Perform a lookup for ‘X’ in the hash map.
- Type 4: getRandom() Operation:
- Generate a random index value.
- Return the element present at the corresponding index in the array.