I read about this and started using binary search as my interview question. It worked well - about 2/3rds of highly credentialed applicants could not write a working implementation in 20 minutes. Most failures went into an infinite loop on simple cases! The ones who could write it usually did so quickly.
I think part of reason is that most people were taught a bad interface. Even the code on Wikipedia says “Set L to 0 and R to n-1”. That is, R is an inclusive bound. But we’ve learned that for most string algorithms, it is better when your upper bound is an exclusive bound, that is, n.
I’ve wanted to do an experiment testing that hypothesis. That is, ask a large number of people to write it with different function prototypes and initial calls and see how many buggy implementations I get with inclusive vs exclusive upperbound vs length.
Indeed, this is actually one reason why I like Python's closed-left, open-right syntax. It lets us sidestep the inclusive bound issue entirely, because, as noted in the post, for all 0 ≤ l ≤ r ≤ len(L) where L is a Python list,
I actually didn't like this syntax until I had to work this out. Now everyone else's approach seems silly to me.Don't most slice methods behave this way? Javascript's `Array.prototype.slice`, Java's `Arrays.copyOfRange`, Golang's slicing syntax is similar to Python's except the 3rd value is the max size of the resulting slice rather than the step value all behave this way.
Based on your description, it sounds like a bad interview question. When otherwise capable candidates can't answer your trivia, maybe it isn't a useful signal? More than anything, it just sounds like you're selecting for people who practiced leetcode vs those who didn't.
It's not whether you can solve it right away, it's how you approach the problem solving process to reach a viable solution. If "try to prove that this code is actually correct" is part of that process, that's the kind of "trivia" that can really be widely applicable even in a working environment, in a way that random leetcode algos often aren't.
I vote for making "how would you think about proving this correct?" a question in all algo-focused interviews.
To be precise, Zoz said
>about 2/3rds of highly credentialed applicants
Credentialed ≠ capable.
> I read about this and started using binary search as my interview question. It worked well - about 2/3rds of highly credentialed applicants could not write a working implementation in 20 minutes.
I'd be interested to know why you feel that this is a useful interview question.
Implementing a well-known and widely implemented algorithm under stressful interview conditions wouldn't seem to me to demonstrate much about a candidate. In that situation I'd much rather be given a printout of some code and asked to talk around the implementation - how the code maps to the abstract algorithm, implementation trade-offs, readability, etc.
It showcases they have done some leetcode. Or it showcases they can write code when someone is looking over your shoulder. There are company cultures where these skills are needed.
Companies that don't fall into a culture like this are indeed deluded.
I would do the following:
1. Write a tax calculator that reads in data from a CSV, or a similar question to showcase programming ability.
2. Do a small paid project. If it was good enough, hire them. If it wasn't, then give feedback and do another one in a week, tell them to learn as much about the topic as possible.
3. Do a small paid project a week later. If their learning agility is high, then hire them still.