Hacker News Reader

Comment by sidlls | Hacker News Reader

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.

View on HN

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.

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.

Exactly

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.

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.

> 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.)

I agree with your sentiment but being over dramatic here.

> 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)

> 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.

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).

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.

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

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

Reply on news.ycombinator.com