News for hackers. Stuff that matters.
Re:Are you one of the 10% of programmers who can write a bin... by raganwald on Monday April 19, 2010 @03:40PM (#1277634)
> "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_algorith...

Re:Are you one of the 10% of programmers who can write a bin... by die_sekte on Monday April 19, 2010 @06:35PM (#1278057)
Re:Are you one of the 10% of programmers who can write a bin... by brazzy on Monday April 19, 2010 @04:25PM (#1277748)
Well, a skip list is just a bunch of linked lists...
Re:Are you one of the 10% of programmers who can write a bin... by sesqu on Monday April 19, 2010 @05:32PM (#1277906)
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.