My #1 Piece of Interviewing Advice

My own interviewing advice stems from the mistakes made during my own past, as a whiz-kid programmer who had trained for programming contests, but was very unsavvy. In fact, I have a few stories where I failed the interview by virtue of knowing more than the interviewer:

• (With Palantir, Fall 2011) Asked the complexity of a solution that uses hash tables, I put in a casual line "if you assume hash tables are constant time." My interviewer reassured me "hash tables are constant." I didn't pick up that he thought that I wasn't sure about the complexity of hash tables. In fact, I knew that hash tables are actually log time, but they're nonetheless called constant for practical reasons. (Or, as I later learned, in a weird theoretical model where "multiplying n-bit integers takes O(n) time, but multiplying log(n)-bit integers takes O(1) time.")

• (With Microsoft, Fall 2010) An interviewer asked me for an efficient binary encoding of tic-tac-toe positions. After rejecting my initial proposal to use a lookup table, I proposed a 9-digit base 3 number. He asked me how many bits it took to store a cell, and I said "log base 2 of 3." We went in circles around this for a while as he asked me question after question about my solution but never seemed to like my answer. Looking back, I'm pretty sure the interviewer did not understand my solution and was looking for a 2 bits per cell encoding. Also that he had not studied information theory and therefore didn't know what it meant to be a fractional number of bits. But, in his questions, he tried to hide that he didn't understand.

In both these cases, it was not enough to solve the problem. It was not even enough to explain my solution clearly. I had to do both of those while also detecting that I was going in a different direction than my interviewer expected and they were reacting negatively, even though I was correct.

And while only a fraction of people reading this are contest programmers who spend 10 hours a week training on problems that are similar to LeetCode but harder, it is very common to approach a problem in a way that is not what your interviewer wants.

And so, my #1 piece of interview advice:

You cannot spend all your brainpower solving the problem. You must reserve some brainpower to detect what the interviewer is looking for.

To do this well, the questions must be beneath you, so that you can solve them while still being able to detect the interviewer's desires.

The Four Problems

There are at least four ways by which you may diverge from the interviewer's desires. I've already given examples above of the first one, interviewer not understanding. The others are honest difference of problem intention, hidden difference of problem intention, and reviewer bias.

Honest Intention

For an example of an honest difference of intention, here's an all-too-common story: An interviewer gives a very easy problem, and someone struggles with it for 10 minutes and says they can't figure it out. But it turns out the interviewer actually only wanted the very inefficient brute-force solution, and the interviewee assumed they wanted something more clever. Interviewers often say "Please keep talking so I can see how you think." The more effective version of this is to not share your every thought, but rather your high-level plans. E.g.: "So I'm thinking about an efficient way to do this" — "No, just give me any approach."

But suppose the interviewer doesn't pipe in and stays silent. Is that because you're doing what they want? Or are they just taciturn or unsavvy themselves, and you should directly ask them that whether they want the clever way or the dumb way? Determining which takes strong perception on your part.

Hidden Intention

And that brings us to hidden differences of intention. In some cases, the interviewer may want to hide what they're looking for, rightly or wrongly. They ask you to explain a graphics routine in a game you wrote. Are they asking to assess its technical complexity, to check that it was actually done by you, to check whether you know about some tangentially-related concept in computer graphics that they really like, or to check how good you are at explaining code to a coworker? Or maybe they want you to assume that they've suddenly morphed into the receptionist and they want to see how good you'll be at explaining your job to someone like that? A good interviewer can switch between questions designed to test different skills very quickly, and a cocky interviewer may think that telling you what they're looking for makes it too easy. You don't control your interviewer. And so you must be thinking about the asker, not just the question.

(As an aside: If you cannot do this, then you should not judge yourself "I have poor communication skills." A more accurate assessment would be "I am lacking in specific skills for dealing with someone who has poor communication skills themselves, or is deceitful in their intentions.")

Interviewer Bias

Finally, we have interviewer bias. I don't mean whether they like you because you're from the same town or dislike you because you went to a rival school, or other immutable attributes like that. I am referring to something much more controllable: whether you advocate something that they like or dislike.

For example: it seems that all Microsoft interviewers are required to ask at least once "how would you test this." Now suppose the problem is one where automated testing would be very hard, but manual inspection very easy. There's the dogmatic answer: maybe they don't give you strong evidence of correctness, but here are some unit tests. Then there's the more contrarian answer: make a checklist of things to manually check in the code. Will your interviewer love or hate that answer? Again, it takes strong perception.

Or, as another example: a lot of interviewers will say "use whatever language you think is right for the problem." I once took this too literally and used Common Lisp. But if the interviewer is a language geek, that could be a great idea.

Unleashing Your Full Power

Now, for the final part of this advice: Suppose a problem comes, and you realize you aren't so good that you can crush it while studying your interviewer's pupil dilation. What do you do if you want your full brainpower?

Here's what I suggest:

State your high level plan. "I need to think really hard about how to solve this question in at worst cubic time while still tracking all actions." And then tell them what you're about to do.

Set a 2-minute timer.

And close your eyes.

There is nary a software interviewer in the world who won't appreciate an extra 2 minutes to check their E-mail.

And you'll be able to think as hard as you can.

I tried it one of my last times interviewing. I came out: "I have the solution; I'm just thinking of how to explain it."

Magic.