Dijkstra observed that the majority of working programmers can't even write a correct binary search. I tried using it as an interview question and gave up because nobody got it right.
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.)
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.
This binary search bug took two decades to be discovered: https://research.googleblog.com/2006/06/extra-extra-read-all...
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.
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.
Perhaps not. I've been a professional software engineer for 32 years, though...
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?
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?
Given that google probably does more software interviews than you do, why do you think they ask such questions, even to experienced candidates?
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.
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 a pretty darn obvious thing to do when you're physically handling an ordered collection of records.
But I agree, plain vanilla binary search is easy.
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.
They already know how it is done elsewhere; it's how one finds a word in a (paper) dictionary or an book index.
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.
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.
Those question aren't successfully answered, because the interviewer failed.
"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...
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.
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.
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.
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.
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.
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.
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 mean you just check a bunch of edge cases. Recursion is not even necessary!
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.
The binary sort algorithm shouldn't care about how that's implemented.
Separation of concerns baby :)