Perform Insert/Delete/Search/Get Random operations in O(1)
No predefined data structure that satisfies all these requirements.
Insertion supported by most of DS but Deletion and Get Random supported by few of Data structure.
To perform all operation in constant time, we have to use Hybrid of 2 or more data structures.
1. O(1) Insert
Stacks/Queues/Linked lists and hash tables support this operation, here BST, heap, Skip list, TRIE etc. are eliminated.
2. O(1) delete
Question doesn't clearly specify delete what? First element, last element or any element?
If we have to delete first element than we go for queues, if we have to delete last element we select stack, if we have to delete any element then we opt for hash.
So contenders in the list till now are - stack/Queues and Hash table.
3. O(1) search
At this step both stacks and queues are ruled out and only hash table remains in the list.
So at this step we are clear that one of the data structure should be hash table.
4. O(1) Get Random
Hash fails to fulfill this requirement, hash requires key to fetch any element and we have no way of generating random keys.
which data structure satisfies O(1) random access?
There is only one Arrays.
Just give index + starting address and boom array gives you the result in O(1).