Qn related to Array, LinkedList, Hashtable, BinaryTree

This is a discussion on Qn related to Array, LinkedList, Hashtable, BinaryTree within the C++ Programming forums, part of the General Programming Boards category; Hi, I was being asked a Qn in an interview to sort : Array, LinkedList, Hashtable, BinaryTree based on how ...

  1. #1
    Registered User
    Join Date
    May 2006
    Posts
    41

    Qn related to Array, LinkedList, Hashtable, BinaryTree

    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

  2. #2
    Registered User
    Join Date
    Oct 2006
    Location
    Canada
    Posts
    1,243
    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.

  3. #3
    Registered User
    Join Date
    Jan 2005
    Posts
    7,317
    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.

  4. #4
    Registered User
    Join Date
    Oct 2006
    Location
    Canada
    Posts
    1,243
    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

  5. #5
    Registered User
    Join Date
    May 2006
    Posts
    41
    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!

  6. #6
    Registered User
    Join Date
    Jan 2005
    Posts
    7,317
    >> 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.

  7. #7
    Cat without Hat CornedBee's Avatar
    Join Date
    Apr 2003
    Posts
    8,893
    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.
    All the buzzt!
    CornedBee

    "There is not now, nor has there ever been, nor will there ever be, any programming language in which it is the least bit difficult to write bad code."
    - Flon's Law

  8. #8
    Registered User
    Join Date
    Oct 2006
    Location
    Canada
    Posts
    1,243
    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

  9. #9
    Cat without Hat CornedBee's Avatar
    Join Date
    Apr 2003
    Posts
    8,893
    A well-hashed hashtable is better.
    All the buzzt!
    CornedBee

    "There is not now, nor has there ever been, nor will there ever be, any programming language in which it is the least bit difficult to write bad code."
    - Flon's Law

  10. #10
    Registered User
    Join Date
    Jan 2005
    Posts
    7,317
    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.

  11. #11
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,299
    Quote Originally Posted by nadroj
    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
    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.

    You can access an element from an array as easy as val = myArray[index]; The question only says 'access', not 'find'.

  12. #12
    Registered User
    Join Date
    Oct 2006
    Location
    Canada
    Posts
    1,243
    ok good info

  13. #13
    Registered User
    Join Date
    Jan 2005
    Posts
    7,317
    >> 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.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Replies: 7
    Last Post: 11-25-2008, 12:50 AM
  2. Question related to array and pointers
    By Q4u in forum C++ Programming
    Replies: 6
    Last Post: 07-26-2002, 12:54 PM
  3. Help with an Array
    By omalleys in forum C Programming
    Replies: 1
    Last Post: 07-01-2002, 08:31 AM
  4. Hi, could someone help me with arrays?
    By goodn in forum C Programming
    Replies: 20
    Last Post: 10-18-2001, 09:48 AM
  5. mode of an array
    By Need Help in forum C Programming
    Replies: 15
    Last Post: 09-17-2001, 08:03 AM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21