I just completed my 183rd technical screen for the last 2 years. 2 years ago I joined Facebook. We hire a lot. We grew from 250 engineers when I joined to 800 engineers. A number of interns every summer is about 60% of number of engineers. So, every Engineer at Facebook has to interview. A lot. On average, there are 2 interviews per week. Most engineers volunteer to go on a campus hiring. I went more than three times. I went to Waterloo, Brown and Wisconsin. 0.5 time was one day at UW in Seattle. Usually, we do two days of interviews. You have to interview 12 people per day.
With a rare exception, I ask the same question every time. Campus hires usually crack it much faster than industry hires. That taking into the account that they have only 30 minutes.
I used to be pretty impressed by some interviewers before (as an interviewee). I know their secret now. The secret is to ask the same question over and over again. Once you asked it a dozen of times, you pretty much know all possible ways to solve it and potential complications. I know inns and outs of my question. I know within the first 30 seconds of the interview, how candidate is going to solve it.
My question is binary search.
If you're Brown student, you re more likely to use Python. If you're Badger, you'll use Java or C. If you use Python, your solution will be recursive and you'll be splitting the array without realizing the performance overhead of this. You will not add the offset of the upper half to the index which is returned from recursion. If you do, there is a 50% chance that you won't check the return value for -1.
If you're Java customer, most likely you'll use recursion. There is a 60% chance that you'll create a temporarily subarray for the recursion call. If you're from UW at Madison, you'll write a for loop to do this with probability 50%.
C-people will use recursion or iteration equally often. Some people will use exclusive upper bound, some will use inclusive. Most people (80%) will screw up the termination condition on their first attempt (they'll use < instead of <=).
There is a 10% chance that a candidate will use a single variable to track where they are in the array.
I haven't seen anybody doing something like lower_bound in STL (ie return the index where this number could be inserted if it is not there). I still yet to see somebody doing a generic algorithm which would use STL-style iterators.
Ok, you've been warned. If you're going to interview with me, better get your binary search straighten out. I want to have time for more interesting question. On the other hand, I'll probably switch to a different question now. I'm bored with this one.