**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).

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;

}

}

Thanks for the great analysis and code. This is a great interview question that has been asked by Google and Uber recently. I also wrote an article that analyzes the same question here: http://bit.ly/2bCPP47.

ReplyDelete