CareerCup

Lets see what we have in hand and what we have to do.

we 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.

Use requirements 1 to 3 -> What are some DSturctures that can do this?

Of the above, can you add operation 4 to any of them?

And just saying "O(1)" is a bit ambiguous..

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.

the answer can be found here: /question?id=6430339136225280

Use hash table + array. The hash table, on its own, should satisfy requirements 1 through 3. But in order to satisfy requirement 4, we use an additional array in addition the hash table.

This one is a "few" liner in Python, thanks to dictionary.keys() .

Anyone care to post code?

And we (meaning, comp sci community) are totally abusing "O" notation. Someone needs to reset its use.

We can use linked hash map that would satisfy conditions mentioned above.

We can use linked hash map that would satisfy conditions mentioned above.

i think it is looking for hashtable

hashtable+arrayList

hashtable+arrayList