4 ms·

Binary search? I would never hire anyone who couldn’t implement it from scratch. There’s no complex idea or trick to remember, it’s the most basic algorithmic a

Binary search? I would never hire anyone who couldn’t implement it from scratch. There’s no complex idea or trick to remember, it’s the most basic algorithmic around.

trhway 5y ago
a guess - you're young and have short industry experience, just enough to make very sure of yourself, so probably the age is between 25-30 with the experience between 5-10 years?
- watwut 5y ago
  I am older then that and still don't fond that question extraordinary hard?
  - trhway 5y ago
    the point isn't about whether the question is hard. It is about understanding that other people are different and especially when the people stumble for whatever reason. The manifested "holier than thou" and lack of humility probabilistically suggest relative youth and inexperience.
    - watwut 5y ago
      Yes other people are different, but I have yet to meet good developer who struggle to understand binary search. Yes, people can randomly fail in interview due to stress or whatever. But that can happen on any question. This particular question really should weed out all that many otherwise good people.
      - Jochim 5y ago
        I learned the common search algorithms in school. I haven't had to touch them since, if you asked me to write psuedo-code for them on the spot I'd almost definitely fail to implement them properly. There's a huge difference between struggling to understand something and not being able to do it from memory on a whiteboard. Imo conversational questions are much better indicators in an interview of whether someone will be a good hire, the candidate knowing why you would use a binary tree over another data structure offers much more insight than asking them to write one. The more conversational approach also allows the interviewee to demonstrate their knowledge and gives you a better idea of how they approach a problem or whether they'd be a good fit on your team.
        kebman 5y ago
        As a teacher I'd say that depends. If it's relevant to the job, then you should obviously know it, and perhaps even be able to expand upon it. Though after reading the posts here I have a sneaking feeling that things like that usually aren't relevant. With that said, having a conversation with someone solving a problem right in front of you, gives you a very good insight into how the person thinks. To that end I've censored a lot of pupils where they have to "defend" (i.e. talk about or explain) a piece of code that they made, sometimes beforehand as a bigger project, or sometimes on the fly. I'd often give them extra problems and talk with them about it as they solved it if I was unsure about the grade. I find that this gives me far more insight in where the pupil is coming from, and hence his level of competence, rather than seeing the code on its own, or having him answer a multiple choice or SAT type test. I can see how an interviewer might make use of a similar technique if he's unsure about the candidate.
sgtnoodle 5y ago
I agree that it's not particularly challenging. As a counterpoint though, a linear search is more basic. It's also often faster than a binary search for small datasets, and it's easier to prove correct purely by inspection. Anecdotally, a coworker we hired a couple years ago (and has been doing an awesome job) dusted off her old coding challenge from when she applied, and ran it through a new test suite we've been working on. The suite failed, and it turns out her binary search was buggy...
- AnIdiotOnTheNet 5y ago
  > As a counterpoint though, a linear search is more basic. It's also often faster than a binary search for small datasets, and it's easier to prove correct purely by inspection. Also for sorted datasets where the most frequently referenced data is at the top.
dmurray 5y ago
I feel like I'm pretty good at these things, but I'd 100% have an off-by-one error in my first attempt at binary search. I can get it right quickly if I'm able to test the code, or very slowly if I have to work through several test cases by hand on the whiteboard. There's a lot of room in between "couldn't implement it" and "can do it in 5 seconds" and "wrote a buggy version of it".
- quietbritishjim 5y ago
  I agree it's very easy to make an off-by-one mistake in binary search. (Related article: [1]) But an interview candidate showing something that is almost right and then has enough self-awareness to say "but I'm sure there's an off by one error in there somewhere" has given a really good overall answer in my books. I think there's still value in asking the question because that sort of answer constrasts against candidates who flounder completely (which is more common than you'd imagine). A common counter argument is that a bad interviewer wouldn't accept an answer that has minor bugs in it like that. But I don't buy that counter argument, because a bad interviewer could misjudge candidates regardless of the interview format. [1] https://reprog.wordpress.com/2010/04/19/are-you-one-of-the-10-percent/ https://reprog.wordpress.com/2010/04/19/are-you-one-of-the-1...
- sgtnoodle 5y ago
  One of the best things you could do in a whiteboard interview is just start writing effective unit test cases without being prompted into it. When I joined my current company, it was still tiny and sketchy and I got shanghaied into a surprise full day interview by the promise of an informal two hour tour. A two hour tour... At one point I was given 1.5 hours to write an implementation of a very core library that most software engineers take for granted every day. Trying to have fun with it, I spent about 20 minutes writing a design document, about 30 minutes coding the implementation, and then the last 40 minutes writing a dozen or so unit test cases (as well as a simple standalone unit test framework). When I ran out of time, only maybe 2/3rds of my test cases passed, and I had just narrowed the problem down to a flaw in one of the assumptions I had enumerated in my design document. All the interviewers seemed pretty impressed by the documentation and test coverage, and didn't really care about the implementation, mostly because it was relatively boring by design.
vaylian 5y ago
StackOverflow disagrees: https://stackoverflow.com/questions/504335/what-are-the-pitfalls-in-implementing-binary-search https://stackoverflow.com/questions/504335/what-are-the-pitf... I quote from the thread: "binary search was first published in 1946 but the first published binary search without bugs was in 1962"
- nonameiguess 5y ago
  I wonder what the expectation of the interviewer is on this. Virtually every single piece of code I'll ever write is going to have a a few off-by-one errors and probably other common bugs. That's why you do some basic validation and QA to find those bugs and fix them. The first pass isn't likely to even compile, but who cares? The compiler will tell you exactly why and you can fix that, too. Perfect code on a first try is a useless skill. On the other hand, just understanding how the algorithm works is what matters. And binary search may have been "published" as an implementation on programmable electronic computers in the recent past, but it's a timeless and intuitive algorithm that I understood perfectly well when I was 4 years old and first learned to read and started looking up entries in the dictionary, encyclopedia, and phone book.
kebman 5y ago
Relax. It was just an example of the often menial 1-2-3 things that often aren't really relevant for the job in question, but are still used to fail even accomplished coders in interviews.
driverdan 5y ago
Has anyone who's worked for you had to write binary search from scratch on the job? It's pointless to ask candidates to write code that they'd never have to do in the real world. I've been writing code for 25+ years, 15 years professionally, and the only time I had to write any search algos from scratch was in school. I'm sure I could do a binary search given enough time but I'd probably just refuse and end the interview.
- sgtnoodle 5y ago
  I'll ask algorithmically interesting questions inspired by past problems I've solved within relevant domains. They're often solvable with some element of binary sorting. I don't care if someone uses a standard library or googles something, but I'll notice if they choose to use one and use it wrong. The classic example is assuming a dict in python is a tree rather than an unsorted hash map. Walking out of an interview like that is certainly a great way to not get hired. That's fine if you didn't want to work there anyway I guess, and nice for the interviewers because they learned enough to end the candidacy confidently knowing they dodged a bullet. Strong engineering teams solving worthwhile problems want to hire people that charge head first into difficult problems and get their hands dirty. If I were in a similar situation where I was asked to write an algorithm I was unfamiliar with, I would probably just say up front that I have no idea how to do that, and then start asking the interviewer questions about how it might work. I would also quickly try to identify a real world example of a problem they're hoping to solve with that algorithm, and then brainstorm alternative ways to solve that problem in ways I'm more familiar with.
david_allison 5y ago
The binary search algorithm listed on Wikipedia has a bug. It's addressed much later in the article.

Binary search? I would never hire anyone who couldn’t implement it from scratch. There’s no complex idea or trick to remember, it’s the most basic algorithmic around.

trhway 5y ago

a guess - you're young and have short industry experience, just enough to make very sure of yourself, so probably the age is between 25-30 with the experience between 5-10 years?

watwut 5y ago
I am older then that and still don't fond that question extraordinary hard?
- trhway 5y ago
  the point isn't about whether the question is hard. It is about understanding that other people are different and especially when the people stumble for whatever reason. The manifested "holier than thou" and lack of humility probabilistically suggest relative youth and inexperience.
  - watwut 5y ago
    Yes other people are different, but I have yet to meet good developer who struggle to understand binary search. Yes, people can randomly fail in interview due to stress or whatever. But that can happen on any question. This particular question really should weed out all that many otherwise good people.
    - Jochim 5y ago
      I learned the common search algorithms in school. I haven't had to touch them since, if you asked me to write psuedo-code for them on the spot I'd almost definitely fail to implement them properly. There's a huge difference between struggling to understand something and not being able to do it from memory on a whiteboard. Imo conversational questions are much better indicators in an interview of whether someone will be a good hire, the candidate knowing why you would use a binary tree over another data structure offers much more insight than asking them to write one. The more conversational approach also allows the interviewee to demonstrate their knowledge and gives you a better idea of how they approach a problem or whether they'd be a good fit on your team.
      - kebman 5y ago
        As a teacher I'd say that depends. If it's relevant to the job, then you should obviously know it, and perhaps even be able to expand upon it. Though after reading the posts here I have a sneaking feeling that things like that usually aren't relevant. With that said, having a conversation with someone solving a problem right in front of you, gives you a very good insight into how the person thinks. To that end I've censored a lot of pupils where they have to "defend" (i.e. talk about or explain) a piece of code that they made, sometimes beforehand as a bigger project, or sometimes on the fly. I'd often give them extra problems and talk with them about it as they solved it if I was unsure about the grade. I find that this gives me far more insight in where the pupil is coming from, and hence his level of competence, rather than seeing the code on its own, or having him answer a multiple choice or SAT type test. I can see how an interviewer might make use of a similar technique if he's unsure about the candidate.

sgtnoodle 5y ago

I agree that it's not particularly challenging. As a counterpoint though, a linear search is more basic. It's also often faster than a binary search for small datasets, and it's easier to prove correct purely by inspection. Anecdotally, a coworker we hired a couple years ago (and has been doing an awesome job) dusted off her old coding challenge from when she applied, and ran it through a new test suite we've been working on. The suite failed, and it turns out her binary search was buggy...

AnIdiotOnTheNet 5y ago
> As a counterpoint though, a linear search is more basic. It's also often faster than a binary search for small datasets, and it's easier to prove correct purely by inspection. Also for sorted datasets where the most frequently referenced data is at the top.

dmurray 5y ago

I feel like I'm pretty good at these things, but I'd 100% have an off-by-one error in my first attempt at binary search. I can get it right quickly if I'm able to test the code, or very slowly if I have to work through several test cases by hand on the whiteboard. There's a lot of room in between "couldn't implement it" and "can do it in 5 seconds" and "wrote a buggy version of it".

quietbritishjim 5y ago
I agree it's very easy to make an off-by-one mistake in binary search. (Related article: [1]) But an interview candidate showing something that is almost right and then has enough self-awareness to say "but I'm sure there's an off by one error in there somewhere" has given a really good overall answer in my books. I think there's still value in asking the question because that sort of answer constrasts against candidates who flounder completely (which is more common than you'd imagine). A common counter argument is that a bad interviewer wouldn't accept an answer that has minor bugs in it like that. But I don't buy that counter argument, because a bad interviewer could misjudge candidates regardless of the interview format. [1] https://reprog.wordpress.com/2010/04/19/are-you-one-of-the-10-percent/ https://reprog.wordpress.com/2010/04/19/are-you-one-of-the-1...
sgtnoodle 5y ago
One of the best things you could do in a whiteboard interview is just start writing effective unit test cases without being prompted into it. When I joined my current company, it was still tiny and sketchy and I got shanghaied into a surprise full day interview by the promise of an informal two hour tour. A two hour tour... At one point I was given 1.5 hours to write an implementation of a very core library that most software engineers take for granted every day. Trying to have fun with it, I spent about 20 minutes writing a design document, about 30 minutes coding the implementation, and then the last 40 minutes writing a dozen or so unit test cases (as well as a simple standalone unit test framework). When I ran out of time, only maybe 2/3rds of my test cases passed, and I had just narrowed the problem down to a flaw in one of the assumptions I had enumerated in my design document. All the interviewers seemed pretty impressed by the documentation and test coverage, and didn't really care about the implementation, mostly because it was relatively boring by design.

vaylian 5y ago

StackOverflow disagrees: https://stackoverflow.com/questions/504335/what-are-the-pitfalls-in-implementing-binary-search https://stackoverflow.com/questions/504335/what-are-the-pitf... I quote from the thread: "binary search was first published in 1946 but the first published binary search without bugs was in 1962"

nonameiguess 5y ago
I wonder what the expectation of the interviewer is on this. Virtually every single piece of code I'll ever write is going to have a a few off-by-one errors and probably other common bugs. That's why you do some basic validation and QA to find those bugs and fix them. The first pass isn't likely to even compile, but who cares? The compiler will tell you exactly why and you can fix that, too. Perfect code on a first try is a useless skill. On the other hand, just understanding how the algorithm works is what matters. And binary search may have been "published" as an implementation on programmable electronic computers in the recent past, but it's a timeless and intuitive algorithm that I understood perfectly well when I was 4 years old and first learned to read and started looking up entries in the dictionary, encyclopedia, and phone book.

kebman 5y ago

Relax. It was just an example of the often menial 1-2-3 things that often aren't really relevant for the job in question, but are still used to fail even accomplished coders in interviews.

driverdan 5y ago

Has anyone who's worked for you had to write binary search from scratch on the job? It's pointless to ask candidates to write code that they'd never have to do in the real world. I've been writing code for 25+ years, 15 years professionally, and the only time I had to write any search algos from scratch was in school. I'm sure I could do a binary search given enough time but I'd probably just refuse and end the interview.

sgtnoodle 5y ago
I'll ask algorithmically interesting questions inspired by past problems I've solved within relevant domains. They're often solvable with some element of binary sorting. I don't care if someone uses a standard library or googles something, but I'll notice if they choose to use one and use it wrong. The classic example is assuming a dict in python is a tree rather than an unsorted hash map. Walking out of an interview like that is certainly a great way to not get hired. That's fine if you didn't want to work there anyway I guess, and nice for the interviewers because they learned enough to end the candidacy confidently knowing they dodged a bullet. Strong engineering teams solving worthwhile problems want to hire people that charge head first into difficult problems and get their hands dirty. If I were in a similar situation where I was asked to write an algorithm I was unfamiliar with, I would probably just say up front that I have no idea how to do that, and then start asking the interviewer questions about how it might work. I would also quickly try to identify a real world example of a problem they're hoping to solve with that algorithm, and then brainstorm alternative ways to solve that problem in ways I'm more familiar with.

david_allison 5y ago

The binary search algorithm listed on Wikipedia has a bug. It's addressed much later in the article.