CareerCup

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

He asked for two, he gets two :-) If he is not satisfied, can give the third.

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

Do you mean Data needing to have an order defined? If not, care to clarify?

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)

when using Linked List, both Insert and Delete would take O(n), instead of O(1), since you need to search for duplicate for Insert and existence for Delete

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.