Now Offering Interview Coaching for Technical Interviews

I’d like to introduce myself as the newest member of the Seattle Interview Coach team. I’ve been brought on to provide some expert advice to those of you facing the prospect of going through a technical interview. I’ve been in the software field for the last 7 years and am currently an engineering manager at Amazon.com. More importantly, however, throughout my career I’ve been continuously interested in technical interviews and have had a wide variety of experience sitting on both sides of the table. I currently conduct about 100 technical interviews a year and know what interviewers are really looking for when conducting a screening.

The majority of candidates I interview end up not receiving job offers because they mess up some technical portion of the interview. In the majority of these cases, however, it has nothing to do with the intelligence or ability of the candidates, but rather their lack of appropriate preparation for a technical interview. Invariably, people forget details about basic data structures or forget how to tackle problem solving questions – this leads to a downward spiral during the interview.

For example, image how you’d deal with this question: Given an input stream of integers of an unknown length (the stream, not the length of the integers), derive an algorithm that can return one of the numbers already seen in the stream at random and with a normal distribution when a client asks for it – you only have 1MB of memory to work with. So, for example, if your algorithm was running along and has processed 100 numbers already and a client asks for a random number, your algorithm should return one of the 100 numbers that you’ve already processed with equal 1/100 probability.

This question usually proves to be a stumper, but if proper problem solving techniques are used it becomes a lot more manageable – certainly not easy, but manageable. First off, you need to recognize that the 1MB requirement is simply a made up number. For problems like this that have large data sets, it’s tempting to start by looking at the big picture, but that’s not really the way you want to solve them. I suggest looking at the problem from the absolute simplest case and building from there. If you’ve processed one integer and then are asked to return a number at random, what do you need to do? Well, that’s simple, you need to return the one number that you’ve seen with 100% probability. What if you’ve seen two numbers? Then you’ll return the first number with 50% probability or the second with 50% probability. At 3? 33.3…% for each of the numbers you’ve seen. Now a pattern is emerging. For each number you process, you need to be ready to return one of them with a probability of 1/n. Great, now we’re getting somewhere, but how do we implement this? You’re dealing with a, possibly, infinite stream of numbers so it doesn’t matter if you have 1MB of space or 1TB or space, you can’t “remember” all of the numbers you’ve seen. So, since you have limited space let’s see if we can solve the problem by only remembering one number at a time, the one that you’d return if you were asked to at any given moment. For each number that you read from the stream you’ll need to roll an N sided die to decide whether that becomes your new return number or not, if it is then you can forget whatever the old return number was and store the new one in its place. For the first number you see you’ll have a 1/1 probability of making that your return number. When you see the second you have a ½ chance of replacing the first number with the second number as your return number, with the third it’s a 1/3 chance that you’ll replace the return number. I’ll leave it as an exercise to the reader to write out the inductive proof to show that this actually works, but that’s the answer. Note that this isn’t a particularly good interview question as it requires some specific probability knowledge to solve. But I’ve seen it asked before, and it helps illustrate that having a good approach to problem solving can mean the difference between floundering on a question and at least making reasonable progress.