Design a data structure that supports insert, delete, search and get random in constant time

Perform Insert/Delete/Search/Get Random operations in O(1)

No predefined data structure that satisfies all these requirements.

Insertion supported by most of data structure 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 as search is not possible in O(1) 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).

import java.util.*;

class FastestDS {

      // A resizable array used to get Random element at runtime

      ArrayList<Integer> array;

      // A hash where keys are array elements and values are indexes in arr[]

      HashMap<Integer, Integer>  hashMap;

      // Constructor (creates arr[] and hash)

      public FastestDS() {

            array = new ArrayList<Integer>();

            hashMap = new HashMap<Integer, Integer>();

      }

      // A Theta(1) function to add an element to FastestDS data structure

      void add(int x) {

            // If element is already present, then noting to do

            if (hashMap.get(x) != null) {

                  return;

            }

            // Else put element at the end of arr[]

            int s = array.size();

            array.add(x);

            // And put in hash also

            hashMap.put(x, s);

      }

      // A Theta(1) function to remove an element from FastestDS data structure

      void remove(int x) {

            // Check if element is present

            Integer index = hashMap.get(x);

            if (index == null) {

                  return;

            }

            // If present, then remove element from hash

            hashMap.remove(x);

            // Swap element with last element so that remove from

            // arr[] can be done in O(1) time

            int size = array.size();

            Integer last = array.get(size-1);

            Collections.swap(array, index,  size-1);

            // Remove last element (This is O(1))

            array.remove(size-1);

            // Update hash table for new index of last element

            hashMap.put(last, index);

      }

      // Returns a random element from FastestDS

      int getRandom() {

            // Find a random index from 0 to size - 1

            Random rand = new Random();

            int index = rand.nextInt(array.size());

            // Return element at randomly picked index

            return array.get(index);

      }

      // Returns index of element if element is present, otherwise null

      boolean contains(int x) {

            return hashMap.get(x)!=null?true:false;

      }

}