Posted August 26, 2009
So you've wowed us with your cover letter and resume. Your kernel work on OpenBSD shows us that you are passionate and hardcore. Despite marginal grades in college, you've shown us how incredibly bright you are. And we know you care about the job, as your cover letter was witty, well-written, and clearly intended for us. Now it's time for a phone interview.
We generally do two phone interviews. The first will be a design question. While you won't be writing any actual code for this interview, you will be working with some core concepts like algorithms and data structures. Our intent is to test your problem solving abilities given a problem and a set of constraints. To that end, the most important thing to remember is to talk through your thought process. Sitting silently for minutes on end is a great way to convince us that you are currently Googling the answer.
Most interviewers will just have one big problem for you. The problem is always iterative; the intuitive solution will probably work, but it will have deficiencies, and you'll have to improve your answer. This is intentional, so don't get discouraged when the interviewer starts pointing out all the various problems. He is actually giving you hints about what to focus on to improve the solution. Even more importantly, don't get too stubborn about your ideas. It's a fine line. An interviewer might challenge a correct answer to make sure you can explain it well, and you should stick to your guns. But there's also a chance that you're wrong, and while there is no single correct answer to most of the questions, there are incorrect solutions, and more than likely, your interviewer has seen them before and is trying to help you see your mistake. In either case, review your answer with a critical eye. Work through the solution out loud, and see if you trip yourself up. Pay attention to the interviewer's reactions for a little extra help. If you get to the end and neither of you sees and problems, then you're probably on the right track.
So let's say your interviewer asks you a question about designing a data structure to hold passenger information for a train scheduling program. The interviewer wants to know the best way to store how many passengers get on each train (denoted by its number) at each station (denoted by which mile on the track it's at) along each line (denoted by number), and on which day of which year. (Creating good interview questions is actually quite difficult. Please excuse this softball question.)
Immediately, a multi-dimensional array jumps to mind. You put the train number on one axis, the stations' mileage on another, the line on another, and the date on the final axis, with the passenger count as the data. Piece of cake, all the data is in there, easily accessible by any metric in constant time. Done, right? Of course not. Your interviewer will probably ask you to find any problems with your design. If you're quick, in this very poor example (seriously, I don't want to get any comments about it), you'll realize that you've created a very sparse matrix, which gets very big very fast, without actually holding all that much data.
How can you improve upon it? Well, in your excitement about your brilliant solution you forgot to consider how the data is going to be used. Remember to ask questions and try to get all the details and specifications up front. In this case, you probably don't need to be able to access the data from every axis. That would allow you to use a hash table of hash tables of hash tables to keep constant time lookup while decreasing memory overhead.
Of course, most people would probably get to relational databases faster than this (extraordinarily bad) example, but it is the type of iteration that you should be going through. If you happen to know, or stumble upon, the correct answer early in the question, the interviewer will usually be prepared to extend the question by asking about more specifics, corner cases, and enhanced features. Just keep working through each new part, building on your solution.
If you keep the discussion alive, talking through the problem, and revisiting your solution trying to find any pitfalls, you'll help your interviewer understand your approach and increase the chances that you'll work your way to a good solution -- and another interview.
Stay tuned for part three, which will cover programming interviews.
Update: Part Three, Programming Interviews, is up!