The majority of working programmers rarely have to write a correct binary search from scratch. Why should you ask it? A better question would be to ask when it's appropriate to use the algorithm, and possibly provide a set of data and a scenario (i.e. context) that the candidate might encounter in which using the algorithm is an appropriate solution but not necessarily obviously so, then see if his process of thinking about the problem leads him there.

The issue is not not being able to write binary-search; but, given a set of constraints, a very well defined set of steps, and ample enough time; is the candidate able to write it in code what's there in their head (a pretty straight forward algorithm).

I expect candidates to write in code what they can explain verbally, given that the code is do-able in the confines of an interview.

That said, I also get what you're trying to say: Capably implementing Binary Search may not be the best indicator of skill, since Software Engineering is so much more than just converting thought to code.

Right. There are two ways you get to implementing binary search in an interview: (1) figuring it out from some basics & possibly hints or (2) reciting it from memory. 1 is useful, 2 is useless. Having used inteviewing.io, it facilitates #1 much more than #2, as a good process should. Interviewer ratings help that.

It's not a complicated algorithm. It's one that people might even use in their every day life (the example I used to use is finding a name in a phone book, I guess that's pretty dated now). I still see candidates who seem to have a conceptual understanding of it fail to translate it into code. That's why I ask it, it's a very simple "here's a thing that intuitively makes sense, now formalize it" question. Maybe this question rules out people who can only copy existing patterns and change values within them, but that's fine as far as I'm concerned. I don't want to hire engineers who can only mimic.

> I don't want to hire engineers who can only mimic.

How is a binary search not mimicry? Probably only 1 in a million people could figure out how to do it if they didn't already know how it is done elsewhere. The only reason most people know how binary search works is because they were taught it somewhere along the line.

Ask an interviewee how to Voronoi diagram the surface of a sphere or something. Then you'll see how things look when people don't do mimicry. You don't get original ideas by asking first-semester programming puzzles.

It's actually just how you would find a number in a paper phone book.

No it's not. Some parts of a phone book search resemble a binary search, but choosing your pivot and processing the last few pages do not. I've never seen someone not do a linear scan at some point.

But all that's irrelevant to my point. Asking for a bog-standard solution to an industry-standard question is in no way a demonstration of someone's originality. You don't ask it to prove that they aren't doing "mimicry" you ask it to prove that they can, and thus are capable of learning the basic tools of their trade from others.

I'm pretty sure I independently invented binary search when I was a child (as have many others).

It's a pretty darn obvious thing to do when you're physically handling an ordered collection of records.

It's the recursion (or parameters to functions in recursion that kills most candidates). It's pretty intuitive in the head.

But I agree, plain vanilla binary search is easy.

People are free to implement an iterative version.

Exactly

> Probably only 1 in a million people could figure out how to do it if they didn't already know how it is done elsewhere.

They already know how it is done elsewhere; it's how one finds a word in a (paper) dictionary or an book index.

Does every language include a generic binary search method? Where?

Or similar, if I asked you to find a specific value in a list of Comparable objects, in my language of choice, how would you do it?

read pseudocode definition of the algorithm and implement in your language of choice, alternatively you could port from one language to another language

In which case I'm curious why it's an unreasonable interview question.

The argument is always "use the stdlib one", but if there isn't one, and you need to implement it, why isn't it fair game?

it's fair game, but to have the best shot of implementing the algorithm the correct way would be to look up the algorithm definition in a reputable algorithms book and implement directly from that, doing so also provides the developer with additional knowledge and context about the algorithm's use and performance characteristics, my 2 cents

Replace "algo book" with "person asking you the question", and I see relatively little difference.

One difference is that this penalizes people with social anxiety.

Don't all in person interviews do this?

Some more than others. It can be mitigated, and probably should be for certain roles.

I guess it depends on what you're interviewing for. If you want a junior to implement specs he's given your point might apply. It's not an appropriate question for someone with basically any real experience, though. Especially not someone who you expect to do anything more complex, like engineering.

So now I ask this:

Given that google probably does more software interviews than you do, why do you think they ask such questions, even to experienced candidates?

Rarely have to? For a professional programmer, writing their own binary search for actual use at work is nearly a firing offense (with a very few exceptions).

Use the library. Don't write your own.

(Yes, I exaggerate. Train such programmers, don't fire them... the first time. But they're wasting your time, and probably introducing bugs in the process. It's deeply unprofessional.)

> Rarely have to? For a professional programmer, writing their own binary search for actual use at work is nearly a firing offense (with a very few exceptions).

You really don't sound like you do much coding. I've lost count of the number of times I've had to write my own binary search simply because the existing ones were painfully inadequate.

Pretty much every standard library implementation, for example, expects the data to be in an array in memory. There's no provision for the data to be dynamically obtained (e.g. from disk or generated on the fly) or in any other form in memory (e.g. unsafe/native int pointers in C#). And have fun running your standard library's binary search, whether Python or C++ or Java or whatever, on something more abstract like the numeric interval [0.5, 1.0]. There's just no way to specify alternate termination conditions like tolerances.

Oh, and this is completely ignoring more mundane shortcomings in a significant fraction of implementations, like how in C# there is (or at least was, last I checked) no way to directly obtain both the lower and upper bounds of an equal range via binary search. At least C++ has equal_range!

I could say the same for practically any classical CS 101 algorithm like depth-first search or Dijkstra or whatever you want, too, except those don't even exist in most standard libraries in the first place... and I suspect their lack of existence is not unrelated to their likely practical inadequacy.

When I had to implement a binary search, it wasn't exactly the version you'd find in a textbook or library. I'm not sure I recall the details now, but I think it needed to return the two closest values if the search key wasn't present. And maybe there was something special about handling duplicate keys, but you get the idea. Sure, it's always good not to re-implement the wheel, but as a professional there are a million mundane reasons you get stuck doing it anyway.

Ex Amazon here. We started asking algorithm optimization question after realizing how important it is.

You don't get to tweak binary searches every day, but if you optimize an algorithm to speed up your product by 1% only once a month and your teammates do the same the difference becomes huge year after year.

Either I've been in only mediocre to average roles(for any of the reasons, including my inability) or you're a very small minority not aware of the fact. I'd like to believe in the latter, for peace of mind, but better to believe in former for driving personal growth. hmm.

I also forgot to mention another case: where the needle you're searching for is of a different type than the items in your haystack. If you're searching for an integer in an array of strings that you know are integers... good luck convincing the type system to let you even call the binary search method, let alone figuring out which argument to the comparator is what type (if they can even be of different types).

> You really don't sound like you do much coding.

Perhaps not. I've been a professional software engineer for 32 years, though...

> Use the library. Don't write your own.

Things are not so simple.

Dependencies on 3rd party libs also imply maintenance costs (generally related to the integration of this lib into your build system). They are moderate, however, they don't go away with time.

Binary search is a small algorithm, which is easy to understand, and whose correctness is easy to check. It's not a good example of a "good" dependency on a 3rd party lib.

> correctness is easy to check

This binary search bug took two decades to be discovered: https://research.googleblog.com/2006/06/extra-extra-read-all...

Seems like a good a place as any to note that I actually discovered this bug in high school programming class circa 1999. If only blogging was popular back then I could have been internet famous! (Surely this bug has been rediscovered many times, just predates the self-aggrandizing blog-post-for-everything era)

I agree with your sentiment but being over dramatic here.

If 100% of applicants are failing a particular question at interview, either the question is inappropriate or the recruitment process has attracted inappropriate applicants.

Either way, this is a failing of the business, not the applicants.

The recruitment process must be sensitive to the needs of the business. These are never entirely bound up in the response given to a single technical question. A good interviewer draws the best from the interviewee, and understands that technical excellence may be necessary but is never sufficient for employees.

> Either way, this is a failing of the business, not the applicants.

I've worked at places that couldn't get someone that passed FizzBuzz level tests but out of desperation hired them anyway. I've not seen people fail but turn out to be decent (or even half decent) coders in real world projects either, at best they can slap something semi-functional together.

It's a failing of the business in that the aren't getting the caliber of applicants they want, but it's also a failure of the candidates when the can't program at all. It's a failure of the industry that those candidates manage to be employed at all.

All of this is true about FizzBuzz, but at the same time, I've seen official interview question sheets that had questions with wrong answers, questions that were too ambitious for 45 minutes, and others that were just way too open ended and asked without any hints to be completely useless.

Those question aren't successfully answered, because the interviewer failed.

Perhaps you shouldn't be expecting candidates to whiteboard a perfect algorithm library function in 1 hr?

"Getting it (exactly) right" isn't the goal of a good interview, unless you are in the business of launching software in 1hr sprints.

Most standard library implementers couldn't write a correct binay search.

https://research.googleblog.com/2006/06/extra-extra-read-all...

> Most standard library implementers couldn't write a correct binay search.

I think that issue with binary sort is not really relevant to interviews. Having a bug with integer overflow is not what an algorithmic question is trying to test.

If you want to test knowledge of undefined behavior show them code with a bug in it and ask them to find it.

Well, if the intent of the interview is just to test algorithms, maybe you don't want to test null pointer checks and off-by-1 errors too?

So much time is wasted in trying to accommodate off-by-one errors (which are a sin in production...just like integer overflows)

> So much time is wasted in trying to accommodate off-by-one errors (which are a sin in production...just like integer overflows)

Off by one is (generally) a much bigger issue. Take for example a buggy binary search which runs infinitely on even length arrays because it gets stuck with the length 2 case. This is a much more likely (in terms of runtime) bug to hit than integer overflow.

Though I generally agree that it isn't too big a deal. I would just mention that there was a bug and only if they couldn't find it would it possibly be an issue. I wouldn't penalize anyone for missing null-pointer checks unless given a valid input (non-null pointers) their algorithm failed because it hit a null pointer.

I think your measure of what is ok and what isn't is just on the basis of what you are comfortable with. Doesn't mean every other programmer is comfortable with the same.

To tell you the truth, I am ok with coding questions. In fact, I demand it. What I'm not ok with is demanding inch-perfect code in 20 mins. The only people who can be perfect are the ones who are doing the exact same problems everyday....not the ones who are doing production work.

I think it depends on the language(s) your team(s) work with or would like to use.

Have all of the reference docs and a dev environment setup on an offline laptop.

Have an obviously toy problem inspired by real problems, yet clearly unrelated to anything your company plausibility needs solved. If it is common public knowledge that you already have a solution it might be fine to use a simplified version of that.

Define solution criteria.

Providing an interface and expecting an object that implements it correctly might be a good test for a go programmer.

When people say/quote things like “can’t even write a correct binary search”, I’m always reminded of this old java bug

https://research.googleblog.com/2006/06/extra-extra-read-all...

Apparently it is not that easy :)

Anyway my personal takeaway from that, is that it is really easy to assume that things you know are easy. And you should be careful about doing so when interviewing.

GP probably used "correct" incorrectly. From my experience interviewing, they probably meant "works for any non-trivial input at all".

Perhaps we need new vocabulary, it seems there exists people who can effectively program computers, but for whom binary search and fizz buzz are to be considered too difficult to understand and get reasonably right. Plenty of HN comments seem to insist on it, whenever the topic of interviewing comes up. Yet, I am absolutely certain that evere single person I've ever worked with in programming would be able to "correctly" implement both binary search and fizz buzz, despite many of them not having been interviewed for them specifically. Indeed, the insistence on those questions comes from an overwhelming consensus in the companies that ask them that the ability to answer them is a reasonable lower bound for the skill these companies understand programming to comprise of.

So, perhaps this group of para-fizzbuzz programmers should be called something else, to avoid embarrassing and time-wasting confusion? (Or we should call fizzbuzz-able-programmers something else? I don't want to appropriate the term, I don't have strong feelings about it.). What are typical tasks that such programmers typically undertake, what sort of companies do they work for?

Note: in the above, for binary search and fizz buzz, I don't mean those literal problems, I mean general problems of similar complexity, ie. that can be fully stated in a few sentences of simple language, and have straight forward implementations in 5-10 lines, using only simple, built-in programming language features and data types, available in any mainstream programming language - if, loop, arithmetic, array, integer.

As someone with much more experience developing software than experience interviewing for positions, I find the whole fizz buzz interview style perplexing. Internally I am thinking 'why the hell are you asking me these questions when you could be asking me far more interesting ones?' The answer is likely that they didn't read my resume, so maybe what the best interviewers have in common is that they read candidates' resumes before the interview.

I think the implication of the OP is that all resumes are presumed to be composed entirely of lies, unless proven otherwise.

To be frank, if an interviewer began asking me questions with that assumption, I would not be offended and would be able to back up any part of my resume with deep answers (or else I wouldn't put it on there), but I would think less of the company and think less of the interviewer.

If no benefit of the doubt is offered to me, I will most likely reciprocate and would assume the company doesn't trust employees to do their job. I'd probably be correct too.

I bet a higher percentage of people would have been able to do things like that in the days of batch processing. I'm getting middle aged, and I grew up with interactive microcomputers. So from the very beginning I was used to typing something into the computer and getting instant feedback. I'm even a bit superstitious when a program compiles/executes with no syntax errors, because I feel like it bodes ill for deeper bugs. So while it seems like very simple coding problems should be a good way to weed out useless programmers in interviews, the fact is, people like me are not very good at programming on a whiteboard, and don't have to do it, because there are employers who don't use such tests. I will say that implementing a binary search is something I have found useful in "real life" - in a SQL database I dealt with a table that had an index on a synthetic key while I wanted to look it up by a non-indexed date. For a simple query, the optimizer couldn't do that efficiently because it didn't know the columns were in the same order. But an explicit binary search could exploit the index to find a date. I didn't do it correctly the first time, nor could I do it quickly enough for an interview. But I got the job done.

I find it's even better to bring things into a practical example that excludes terminology, even if in reality it maps directly back to it. "Imagine I give you an alphabetized list of n book titles. n could be realllly big. I have another book to add to the collection. How should I do this?" By removing the terminology, I think it lets people look at the problem as a problem instead of a terminology test.

This also helps when developers are self-taught and have a professional background rather than an academic one.

How hard is it to get right, seriously?

I mean you just check a bunch of edge cases. Recursion is not even necessary!

If you're just sorting ASCII English it's pretty trivial, as long as you assume ASCII ordering throughout.

But for all possible data types, in all (okay - most) written languages, with full unicode support, dealing successfully with all possible localised edge cases defining postal/delivery address and date/time formats - very hard indeed.

Well that's up to the writer of that class to implement a comparator function to define a total order correctly. I am not even sure there an be a meaningful total order on postal addresses.

The binary sort algorithm shouldn't care about how that's implemented.

Separation of concerns baby :)

I wonder if this quote is out of context. Consider the Java bug that was discovered around 2006.

But surely this just means that binary search is not relevant?