3 ms·

I'm amazed how many interviewees can't even properly explain binary search, down to saying "linked list" as the base data structure.

• raganwald 17y ago
  > "linked list" as the base data structure. I would enjoy reading a logically correct implementation of a binary search on a linked list. Discussing the performance complexity would be an obvious next question in the interview. http://en.wikipedia.org/wiki/Schlemiel_the_Painters_algorithm http://en.wikipedia.org/wiki/Schlemiel_the_Painters_algorith...
  • brazzy 17y ago
    Well, a skip list is just a bunch of linked lists...
    • sesqu 17y ago
      I would describe it more as a multiply-linked list. The important distinction in a skip list is that you get random access, in a different sense of the term, and so binary search makes sense. Similarly, you could justify a binary (or another non-sequential) search on a traditional linked list by assuming huge evaluation costs.
  • die_sekte 17y ago
    Done: http://news.ycombinator.com/item?id=1278055 http://news.ycombinator.com/item?id=1278055