10

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 πŸ™‚

Comments
  • 2
    Wait, they told you the data structure to use? Lame.
  • 5
    My employer has never asked me to implement any search. The last time I rolled my own linked list was also 20 years ago. How are these things relevant to a job today? I get the algorithm part, but not some kind of rote exercise. I feel like I would completely under-prepared for an interview these days.
  • 7
    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.
  • 3
    @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
  • 2
    @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).
  • 3
    @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)" >.<
Add Comment