Interviewer: Implement Binary Search on a Linked List

Me: * did so on the whiteboard *

Interviewer: *irritated* This is complete BS

Me: Yes, a complete Binary Search 🙂

Wait, they told you the data structure to use? Lame.

A binary search on a data structure that has O(n) access? Am I missing something?

I mean yeah with a skip list overlay in parallel, but then even insertion and deletion wouldn't be fast anymore so that the linked list would be pointless.

@Fast-Nop
Exactly. I'd expect at least a red-black tree here.

Rocket scientist likely assumed that the linkedlist was sorted or started with a middle node or supported atIndex

@SortOfTested Or something I actually had recently, with two lists where I needed to find all elements from list 1 that were not in list 2, both as arrays. Sort list 2 in O(n log n), and then for each element of list 1, a binary search in list 2, also O(n log n).

@Fast-Nop
I would definitely have ignored the question and said, "create a Set from the list L, map list R for LSet contains Ri, O(n+m)" >.<