Amazon Interview Question Software Engineer / Developers
you can store any datatype in hashtable...there are many ways to implement a hash table...simplest is array implementation..since the range of the valuse is given...we can safely implement hashtable using arrays...and we just have to store the count of each value.
other way to implement hashtable is to using self balancing binary trees but the insertion deletion lookup is O(logn)
I didn't get what does FindAny do. But basically what u need is not exactly a hash table! You need an int[1000]. If findAny needs to return the last insertion the codes would be:
Integer lastInsert = null;
void insert(i){array[i]++; lastInsert = i;}
void delete(i){if(array[i] > 0) array[i]--;}
boolean isThere(i){return (array[i] != 0);}
Integer findAny{return lastInsert; /*it would be null if there is no insertion*/}
what if I deleted the value stored in lastInsert..how will you get findAny() ??
for ex: insert(10)->insert(8)->delete(8)->findAny()???
output should be 10..but your code will be still 8
I'm not sure why we even bother with Hashtable as the input will always be between 1-1000. We can simply store it in Array and ignore first index and map all elements 1-to-1.
I think if you just say hashtable you will fail since a "hashtable" is assumed to have collision so you should say a "perfect hashtable" or you should explain the fact since we know the range we can setup hashtable with no collision.
---CORRECT ANSWER---(everything else above is crap)
maintain following two DSs:
1. hash table (direct addressing table for 1-1000)
2. doubly linked list
for every insertion in hash table insert the element at head of DLL and store the pointer to this newly created node (DLL node) in the node in the hash table. during deletion from hash table, delete from DLL as well (deletion from DLL takes O(1) time)...going to the corresponding node is also O(1) as we've already stored the pointer for the node in DLL. for findAny return the head of the DLL. the isThere is trivial.
Further optimisation: club DLL into the hash table itself. needn't store the ptr to DLL node explicitly.
-PS
Courtesy: lallu
Your solution is so bad.
Just an array of int[1000] which initialized to 0
insert will be O(1), since we just need to set 0 to 1 when we need to insert an element
Delete will be O(1), since we just have to set 1 back to 0
IsThere will be O(1), since there is no collision
FindAny, i dont know what they want......
hash table
- Anonymous May 23, 2011