[commandlinefan]

I used to work with a guy who tech-screened applicants by demanding that they come up with the binary-search algorithm: “given a sorted list of numbers, find the fastest way to locate an element in the array”. Of course, if you had any university-level exposure to CS, you would have already seen the solution - I sort of suspected this was his tricky way to filter out non-CS graduates.

[Hermitian909]

I wouldn't characterize it that way, I don't have a CS degree and could solve this trivially.

I think the question first asks the interviewee to have cracked an algorithms textbook or be clever enough to come up with the method on the spot.

Second, it asks if you can explain the concept to another engineer. I've met engineers in their 40s who can implement something like depth first search but cannot explain it. That's an immediate red flag to me that, at the very least, the person I'm talking to is not able to meet the responsibilities of a senior engineer.

[pbalau]

Divide and conquer? I don't have a cs degree, but this was thought in highschool in Romania. If you went to the right kind of high school.

Reading the other comments I'm not sure d and c is the answer. Might be terminology, but I would split the array in two at the middle, see if the value I'm om is the one I'm searching for. If not, recursively do the same thing on the left or right side of the array.

[mercutio2]

I... have a hard time imagining what coding job wouldn’t want candidates to know how to find a log N solution to a search problem.

I guess this is the old “there are two clusters of tech jobs” problems, where I can barely fathom the techniques of the other cluster.

[commandlinefan]

That was his position - I just recall that all of the CS grads got it, and none of the self-taught/bootcamp types did, though.

[jiveturkey]

What are you getting at? That this is a trick or bad question?

This is on the order of fizzbuzz +1 level maybe. It's elementary stuff.

Or was he looking for best-case optimization or something more than just binary search.

[commandlinefan]

It seemed like a bit much to me at the time. It's not something that I've ever had occasion to actually use (I don't search sorted lists much...). I wondered if I would have been able to come up with it if I hadn't already seen it in data structures class years ago - I mean, of course I figured out the "algorithm" when I was a little kid playing "guess the number", but I'll never know if I would have come up with it in that context if I hadn't already seen it. The consensus here seems to be that it's a reasonable question, though - but I do remember that the only people who ever got it were people with CS degrees.

[mlthoughts2018]

binary search is very widely misimplemented,

- https://en.m.wikipedia.org/wiki/Binary_search_algorithm#Impl...

> “When Jon Bentley assigned binary search as a problem in a course for professional programmers, he found that ninety percent failed to provide a correct solution after several hours of working on it, mainly because the incorrect implementations failed to run or returned a wrong answer in rare edge cases. A study published in 1988 shows that accurate code for it is only found in five out of twenty textbooks. Furthermore, Bentley's own implementation of binary search, published in his 1986 book Programming Pearls, contained an overflow error that remained undetected for over twenty years. The Java programming language library implementation of binary search had the same overflow bug for more than nine years.”

[luc4sdreyer]

The bug only manifests if the range you're searching is within MAX_INT/2 (or whatever numeric datatype you're using). I'm not sure I understand the point you're trying to make.

[mjevans]

I didn't understand what you were talking about offhand and thought range might be the value of the stored/searched data, not a pointer arithmetic issue.

When the array/list consumes a memory footprint larger than ptrdiff_t it was possible that the specific implementations might fail. It is crucial to remember that the difference between memory address is signed and that the size of objects (even if bare machine integers of some size) in the set might be displayed as a number smaller than one of the powers of two many recall.

On a 32 bit machine this wouldn't be approx 2 billion but rather often 500M 32 bit words or 250M-ish 'double' precision numbers. Let alone if the search is over more complex structures representing objects. For a smaller 16-bit embedded system I could even more readily see this occurring.

[luc4sdreyer]

You make a good point. I was actually speaking about the general case, where you're simply pulling the bounds of x_min and x_max closer until f(x) reaches a target value or the bounds converge to the same value. f could be an array and x could be an index, but it doesn't have to be. The bug still exists in this general case. All you need is a numerical datatype that can overflow, and most of them can.

[mlthoughts2018]

It seems you’re deliberately not trying to understand.

[luc4sdreyer]

I assure you I'm being sincere.

[mlthoughts2018]

Yet you focus only on one aspect of the linked discussion on the high rate of misimplementations, an aspect that represents the least relevant part, and then act as if this invalidates the point?

That’s not sincere, it’s disingenuous.

[luc4sdreyer]

I didn't say it invalidates the point, because I honestly don't know what your point was to begin with. Which is why I asked the question originally. I'm still no closer to knowing, and it seems like you're not interested in elaborating. Suit yourself.