Printable View
Hi,
I was being asked a Qn in an interview to sort :
Array, LinkedList, Hashtable, BinaryTree
based on how quickly can u you access an element from them.
I found this question difficult to answer since I feel:
Hashtable and Array have constant access time.
Binary tree depends on how you implement them (AVL tree, Splay tree etc..).
Linkedlist depends on where the element is..
so how can one sort them!!
Any suggestion?
Best Regards,
Shal
it would depend if they are all sorted or not.
if they are all sorted, then i would say BinaryTree is definetly the fastest.. this is how i would order them in ascending access time:
BinaryTree, Hashtable, Array/LinkedList
theres alot of information and im sure theres many papers discussing this topic, check it out.
I disagree with nadroj's answer. I think they are probably looking at average, best or worst case running times. To my recollection, one of those is O(1), one is O(1) average case but O(n) worst case, one is O(log n) average case but O(n) worst case, and one is O(n). That would be the order I would put them in.
i think there are many variables to consider when answering this question.. the question was somewhat vague and lacking these details, and as well was my response.
i still think a balanced binarytree is the fastest of the others mentioned :)
Oh yes! I remember reading something like that... i will check it out , that would be better way to answer it. I guess thats what probably the interviewer was expecting!
>> i still think a balanced binarytree is the fastest of the others mentioned
No, it is not. I'd say why I disagree, but I don't want to give too much answer yet.
I disagree with the question. "Access to an element"? If I want access by index, the array is fastest. If I want access by element value, then it is probably not. Of course, elements in a hashtable do not have an index, so it is probably access by element value. But that's called lookup.
i wasnt assuming a pointer, or index. i was assuming the question was basically 'which of these methods provides quickest searching'. if i were to search for item X, then i think balanced binarytree is best. maybe im misunderstanding the question. oh well
A well-hashed hashtable is better.
I presumed it was not a trick question. Obviously the question is vague, but my guess is that if it is an interview question there is no absolutely correct answer. The point would probably be to hear/see your thought process in why you'd rank them as you do. If you make a certain assumption and then give a good answer based on that assumption, you'd still do well with the question.
On the other hand, IMO there is a single answer that is straightforward and mostly likely what they are looking for.
Well for starters even a perfectly balanced binary tree is at best O(logn) whereas a hash-table is O(1) in practice, even though it can be worse in theory, that pretty much never happens.Quote:
Originally Posted by nadroj
You can access an element from an array as easy as val = myArray[index]; The question only says 'access', not 'find'.
ok good info
>> that pretty much never happens
It absolutely happens. It caused a major performance bottleneck in a portion of our application. Given how easily it occurred, I'd be surprised if our situation was really that rare. Obviously the problem was due to programmer error, but it is still a situation that must be accounted for in practice.