> if I forgot how to write binary search
The binary search algorithm isn't something you can "forget". For a literate programmer it's like forgetting how to write the letter 'A' or forgetting which pedal is the gas and which is the brakes.
The binary search algorithm isn't something you can "forget". For a literate programmer it's like forgetting how to write the letter 'A' or forgetting which pedal is the gas and which is the brakes.
Well, I thought, yes, I think it is, actually? So I tried implementing a hash table in C—without testing it, as if I were writing it in an interview without programming tools. It took me 15 minutes and had a significant bug: https://news.ycombinator.com/item?id=26593250
I concluded that implementing a hash table in C in 30 minutes is a reasonable thing to ask someone to try during an interview, and how people work on it will probably tell you a lot about their programming abilities. I wouldn't hire them for a C programming job if they said "school was years ago, I've forgotten", but you shouldn't necessarily expect them to succeed flawlessly.
Binary search in particular is notoriously tricky. It's easy to explain the idea in a lot less than 10 minutes, and it's easy to write a version of the code that sometimes works in less than 10 minutes, something like
bs(k, a, i, j)
{
int m = (i+j)/2;
return a[m] == k ? m :
a[m] < k ? bs(k, a, m, j) :
bs(k, a, i, m);
}
Also, though, there are lots of kinds of programmers. You can spend a lot of time writing screen-scrapers or CRUD or machine learning models in Python without ever needing to implement binary search. In Python you should probably just use the bisect module in practice, most of the time, rather than reimplementing it.
For sure, but I guarantee you the interviewer from the grandparent comment wasn't looking for correctness and safety when they asked to implement a binary search.
They ask the binary search question to check if the applicant knows what an algorithm is and if they ever had to implement one. (Any algorithm.)
Sadly, 90% of programmers these days don't and haven't.
> In Python you should probably just use the bisect module in practice, most of the time, rather than reimplementing it.
Well, yes, most developers ship software without ever having to actually program.
What, the company that interviewed James Hush about binary search was your company? Have you thought about the possibility that maybe he also interviewed at at least one other company which used different evaluation criteria? Maybe you should put a little bit more effort into correctness yourself!
> They ask the binary search question to check if the applicant knows what an algorithm is and if they ever had to implement one. (Any algorithm.)
> Sadly, 90% of programmers these days don't and haven't.
That makes no sense. Every program or subroutine implements an algorithm. If you haven't written any programs or subroutines you aren't a programmer.
> Well, yes, most developers ship software without ever having to actually program.
This reminds me of when I was a kid and we thought it wasn't "actually programming" when we programmed in BASIC or Pascal because actual programs were written in assembly. We were wrong about that.
I think writing an if-statement would be closer to your analogies.
Probably.
Point is, you don't really need to know how to program to ship software.
I've still never had a professional use for a Trei structure. I tried really hard to make a case for it on a project at Google, but it just didn't make sense vs. slapping down std::map and then drinking a beer.
Because most pragmatic to me would be to google for a solution on Stack overflow, see what is upvoted and seems reasonably vetted, then potentially go over the code yourself to see if there's any issues and maybe write few tests to be extra sure.
Maybe your use case is too niche though to be able to copy paste though, I'm not sure.
But in an interview situation, they cannot give you a three week task. Like FizzBuzz, a binary search is a simple task that can be done during an interview. They are not testing your ability to write a binary search. They are testing you on your ability to implement a function, given specific requirements.
You don't use all 10000 words of your native language every day. You don't ride a bike every day. Nevertheless, that's part of you and you don't need to make a conscious effort to remember which way the pedals spin when you ride a bike after a long hiatus.
Programming is already pretty unnatural and implementing binary searches and other basic algorithms is really only something you do constantly in the beginning. Over time that "muscle memory" will fade. It's also something that's easy enough to look up and understand in a couple minutes.
If you cannot write a binary search routine from scratch, how can you be expected to solve much bigger problems?
void
dumbsort(int *p, int n)
{
for (int tmp, i = 1; i < n; i++) {
if (p[i] < p[i-1]) tmp = p[i], p[i] = p[i-1], p[i-1] = tmp, i = 0;
}
}
void
isort(int *a, size_t n)
{
for (size_t i = 1; i < n; i++) {
for (size_t j = i; j > 0; j--) {
if (a[j-1] <= a[j]) break;
int tmp = a[j];
a[j] = a[j-1];
a[j-1] = tmp;
}
}
}
It took me about five minutes to write that, and it worked the first time I tested it. But that's in part because I find sort routines fascinating and I've been studying them, and programming in C, for almost 30 years. Even if it took you an hour or four hours and required a lot of debugging, you still might be a decent programmer. Especially for jobs where things are less well defined and you have to do a lot of debugging anyway!
(By contrast, I've actually spent most of the last hour trying to write a properly working quicksort, the variant that finishes up with a single call to insertion sort, using both notes and a compiler. Of course it produces correct results because of the final insertion sort but it's not as efficient as it should be and I can't figure out why. Apparently I can't brain today... good thing I'm not in a job interview!)