Amazon Interview Question
Software Engineer / Developerssounds reasonable. But don't you think interviewer expect one solution that uses hash_table ie. provides O(1) look up ? I think intention is to know if we know how map is actually implemented.
T missed a very important reason to use BST, which has nothing to do with speed. For some reason he put it as a con
btw,
why didn't anyone point out that the Delete running time I gave for Linked List is wrong?
Hashtable: given a key, calculate a hashcode for the key. hashcode mod size_of_table gives you a bucket where item is placed.
Why I would not use a linked list: hashtable requires random access, which is O(n) for each insert/delete/lookup with a linked list.
It is true, that linked list is dynamic which makes it better then an array, but, in this case its not an advantage since every time the size increases every item has to be re-inserted. So inserting n items will take O(n*n) operations.
I'd use an array. Average case for insert/delete/lookup is O(1)
You're spot on for a BST. Advantage: avoid worst case O(n) operations. If you ever want to iterate over the items you get them in order thanks to BST's order property.
The last point - ordered traversal of items is really the only reason I'd used a BST backed hashtable.
Disadvantage: sacrifice best-case lookup O(1)
Have a look at Java collections and perhaps the book from Algorithms course. Java Collection Maps come in 2 flavors - array backed and BST backed. Never (ever) use a linked list.
Saying "Never ever" is a sign of ignorance, IMO. There are always exceptions (or, in order not to fall in the same trap, there are likely to be exceptions).
Based on the usage patterns, there are situations where using a Linked List could be better.
btw, I was in no way suggesting that you use Linked List as a map for your daily use.
Comments like this are quite idiotic.
Suppose the usage pattern was only to lookup recently inserted elements and very few deletions. Linked list works perfectly fine for this.
btw, read the question. It just asked for 2 data structures which can be used and their comparison. It does not ask for the best ones, which btw, depends on the usage... and it is ignorant to claim one is always better than the other without knowing the context of usage.
Lookup:It is like a cache, the most recent will be present in the lookup.
lookup is used to reduce the access time of most recently used elements.
Implementation:
---------------
suppose lookup size is K, then it is implemented with a hash table.
and all the elements will be stored in a BST, so insertion will take o(log n) time.
If an element is found in the lookup, its search time is 0(1), if not found search time is o(log n) to search in the BST.
Not sure what Rider is talking about.
Lookup = Search for an element I thought. Where did cache/most recently used come into the picture?
Two example structures that can be used:
- T March 19, 2009