Amazon Interview Question
SDE1sCountry: India
Interview Type: In-Person
+1
But to cut things short...requirements 1, 2, 3 are the "usual" operations for sets/dictionaries/collections/whatever/datastructures.
So it's better if you take them together, and find the data structure(s) that satisfy 1/2/3....
Then try to satisfy 4 on top of that.
oh yes, absolutely.
stacks/queues/LL were eliminated in step-2 only, I was just trying to demonstrate how to approach a problem like this.
looking at requirement 1,2 and 3 Hashtable was an obvious choice .
And arrays offer random access so best choice for 4th requirement.
how to merge hash + array that was the basic question.
We can use combination of doubly linked list and hashmap of <value,node>;
Each time we add a node in DLL , we will add it into hashmap also.
now lets see how it gives o(1) complexity.
1) insert is ofcource O(1). insert at frond or rear.
2) we can search in hashmap for the desired node.
3) look up in hashmap . if node present than get the node from hashmap. Since its a doubly link list , and we have pointer of node to be deleted , we can delete from DLL in O(1).
4) I am not sure what they expect in this one.
Lets see what we have in hand and what we have to do.
- varun October 08, 2013we have to perform Insert/Delete/Search/Get Random all operations in O(1).
It is clear there is no data structure that satisfies all the requirements, some support one of the operations, some 2 but neither supports all 4 operations.
By now, it is evident we have to use Hybrid of 2 or more data structures.
Now question we have in front of us is which ones?
Lets move operation by operation and we will keep the ones that are present in maximum operations.
1. O(1) Insert
==========
Stacks/Queues/Linked lists and hash tables support this operation, at this step 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
================
we have selected hash as our choice of data structure for this problem, but hash fails to fulfill this requirement, hash requires key to fetch any element and we have no way of generating random keys...now what to do?
Let's follow the approach we were following in our earlier steps:
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).
But our problem is still not solved, how to use this property with hash and also how can we generate a random hash key??
re generating random key, it is clear it is something we can't do because key might or might not be present in hash table but there is one thing we can do we can generate random integers.
How to use these random integers?
this is the final part of our solution simple keep all hash keys in an array, use a random number generator to generate a random number between 0 and totalNumberofkeys-1.
Fetch the key stored at this index O(1) and get value corresponding to this key O(1) again and return the result.
keeping array for storing keys involve inserting keys in array (insert op) and also deleting keys in array (delete op), I'll leave that to you guys for implementation.