Final answer:
The data structure that supports insert, remove, and getRandom operations in average O(1) time combines a dynamic array with a hash table. This ensures efficient insertion and removal by maintaining an index mapping, and allows equal probability random access through the array.
Step-by-step explanation:
To achieve average O(1) time complexity for insert, remove, and getRandom operations, we can design a data structure that uses a combination of a hash table and an array. This data structure will allow us to insert and remove elements efficiently while also providing a way to access a random element with equal probability.
Designing the Data Structure
The data structure consists of:
An array to store the elements.
A hash table (hash map) that maps values to their indices in the array.
Insert Operation
For the insert(val) operation:
Check if the val is already in the hash table.
If not, append it to the array and store the index of this new element in the hash table.
Remove Operation
For the remove(val) operation:
Find the index of val in the hash table.
Swap the last element of the array with the element to remove.
Update the index of the swapped element in the hash table.
Remove the last element of the array and delete the val from the hash table.
GetRandom Operation
For the getRandom operation:
Generate a random index within the bounds of the array.
Return the element at that random index.
Since insertions and deletions only involve appending/removing from the end of the array and updating the hash table, and since array indexing and hash table operations are O(1), the average time complexity of all operations will be O(1).