A request I’ve gotten from a couple of readers (unrelated to the recent charity thing) is to talk about engineering interviews at tech companies. I’ve been at Google, Foursquare, Twitter, and now Dropbox, so I’ve spent some time inside multiple companies that put a lot of effort into recruiting.
Tech interviews get a lot of bad press. Only some of it is deserved.
What you frequently hear in criticism is stuff about “gotcha” questions, or “brain teasers”. Those do happen, and when they do, they deserve condemnation. For example, I have seriously had an interviewer for a software job ask me “Why are manholes round?” That’s stupid. People who like it claim that it’s a test of lateral thinking; I think it’s garbage. But these days, that kind of rubbish seems pretty rare.
Instead, what’s become very common is for interviewers to present a programming problem, and ask the candidate to solve it by writing some code. A lot of people really hate these kinds of interviews, and describe them as just brain-teasers. I disagree, and I’m going to try to explain why.
The underlying problem for tech job interviews is that hiring the right people is really, really hard.
When someone applies for a job as a software engineer with your company, you start off with just their resume. Resumes are not particularly informative. All they give you is a brief, possibly partial history of the candidates work experience. From a resume, can’t tell how much they really contributed to the projects they worked on. You can’t tell how much their work added (or subtracted) from the team they were part of. You can’t tell if they get work done in a reasonable amount of time, or if they’re slower than a snail. You can’t even tell if they can write a simple program at all.
So you start by screening resumes, doing your best to infer as much as you can from them. Next, you often get recommendations. Recommendations can be useful, but let’s be honest: All recommendation letters are positive. You’re not going to ask for a recommendation from someone who isn’t going to say great things about you. So no matter how terrible a candidate is, the recommendations are going to say nice things about them. At best, you can sometimes infer a problem by reading between the lines – but that’s a very subjective process.
So you end up interviewing someone who’s resume looks good on paper, and who got a couple of people to write letters for them. How do you determine whether or not they’re going to be a valuable addition to your team?
You need to do something to decide whether or not to hire a particular person. What can you do?
That’s what the interview is for. It’s a way to try to get more information. Sure, this person has a college degree. Sure, they’ve got N years of experience. But can they program? Can they communicate well with their coworkers? Do they actually know what they’re doing?
A tech interview is generally an attempt to get information about a candidate by watching them work on a problem. The interview isn’t about knowing the right answer. It’s not even about getting the correct solution to the problem. It’s about watching a candidate work.
When I ask a job candidate a technical question, there’s three main things I’m looking for.
- What’s their process for solving the problem? On this level, I’m trying to figure out: Do they think about it, or do they jump in and start programming? Do they make sure they understand the problem? Do they clearly state their assumptions?
- Can they write a simple program? Here I’m trying to see if they’ve got any ability to write
code. No one writes great code in an interview setting. But I want to know if they’re
able to sit down with an unfamiliar problem, and work out a solution in code. I want to see if they start coding immediately, or take time to think through their solution before they start writing. - How well can they communicate ideas about programming? Can they grasp the problem from my description? If not, can they figure out what questions they need to ask to understand it? Once they start solving the problem, how well can they explain what they’re doing? Can they describe the algorithm that they’ve chosen? Can they explain why it works?
To try to clarify this, I’m going to walk through a problem that I used to use in interviews. I haven’t used this question in about 3 years, and as far as I know, no one is using the question anymore. The problem involves something called Gray code. Gray code is an alternative representation of numbers in binary form that’s useful for a range of applications involving things like switching systems.
Here’s a quick run through one of the reasons to use gray code. Imagine a system that uses physical switches. You’ve got an array of 8 switches representing a number. It’s currently presenting the number 7 in standard binary – so the first 5 switches are off, and last 3 are on. You want to increment the number. To do that, you need to change the position of four switches at exactly the same time. The odds of your being able to do that without even a transient state that appeared to be a number other than 7 or 8 are vanishingly small.
Gray code solves that by changing the representation. In Gray code, the representation of every number N+1 is only different from the representation of N by exacly one bit. That’s a nice property which makes it useful, even nowadays when we’re not using physical switches for much of anything anymore.
The easiest way that you get the gray code of numbers is by writing a table. You start off by writing 0 and 1, which are the same in both gray code and standard binary:
| Decimal | Standard Binary | Gray |
|---|---|---|
| 0 | 0 | 0 |
| 1 | 1 | 1 |
There’s the one-bit gray codes. To get the two bit, make two copies of the rows in that table.
To the first copy, prepend a 0. To the second copy, reverse the order of the rows, prepend a 1:
| Decimal | Standard Binary | Gray |
|---|---|---|
| 0 | 00 | 00 |
| 1 | 01 | 01 |
| 2 | 10 | 11 |
| 3 | 11 | 10 |
To get to the three bit gray codes, you repeat the process. Copy the rows, prepend 0s to
the first copy; reverse the order of the second, and prepend 1s.
| Decimal | Standard Binary | Gray |
|---|---|---|
| 0 | 000 | 000 |
| 1 | 001 | 001 |
| 2 | 010 | 011 |
| 3 | 011 | 010 |
| 4 | 100 | 110 |
| 5 | 101 | 111 |
| 6 | 110 | 101 |
| 7 | 111 | 100 |
So, the gray code of 6 is 101, and the gray code of 7 is 100.
What I would ask an interview candidate to do is: implement a recursive function that given an integer 
I can understand how some people look at this question, and say, “Yeah, that’s just a stupid puzzle.” On one level, yeah. It’s obvious an artifical question. In fact, in practice, no one ever uses a recursive algorithm for something like this. Even if you have a problem where gray code is part of a practical solution, there’s a better way of converting numbers to gray code than this silly recursive nonsense.
So I agree that it’s artificial. But interview questions have to be artificial. In a typical interview, you’ve got an hour with a candidate. You’re not going to be able to explain a real problem to them in that amount of time, much less have them solve it!
But it’s artificial in a useful way that allowed me, as an interviewer, to learn about the candidate. I wasn’t trying to see if the candidate was number-puzzle wizard who could instantly see the recursion pattern in a problem like this. Most people have never heard of gray code, and to most people (including me, the first time I saw this problem!), the recursion pattern isn’t obvious. But that’s not the point: there’s a lot more to the interview that just the initial problem statement.
I don’t present the problem, and then sit back and watch silently as they try to solve it. If I did, all I’d be learning is whether or not they’re a number-puzzle wizard. I don’t care about that. So I didn’t just leave them floundering trying to somehow come up with a solution. In the beginning, after describing the problem, I set an initial direction. I usually have them start by extending the table themselves, to make sure they understand the process. Then I take their extended table, and add a new column:
| Decimal | Standard Binary | Gray | Rec |
|---|---|---|---|
| 0 | 0000 | 0000 | |
| 1 | 0001 | 0001 | |
| 2 | 0010 | 0011 | “1” + gray(1) |
| 3 | 0011 | 0010 | “1” + gray(0) |
| 4 | 0100 | 0110 | |
| 5 | 0101 | 0111 | |
| 6 | 0110 | 0101 | |
| 7 | 0111 | 0100 | |
| 8 | 1000 | 1100 | “1” + gray(7) |
| 9 | 1001 | 1101 | “1” + gray(6) |
| 10 | 1010 | 1111 | “1” + gray(5) |
| 11 | 1011 | 1110 | |
| 12 | 1100 | 1010 | |
| 13 | 1101 | 1011 | |
| 14 | 1110 | 1001 | |
| 15 | 1111 | 1000 | “1” + gray(0) |
With that on the board/screen, I’d ask them to try to take what I just gave them, and rewrite it a bit. For example, in row 8, instead of “1” + gray(7), come up with an expression using the numeric value “8” of the row, which will produce 7. They should be able to come up with “15 – 8” – and to see that in every row 
For most people, that’s enough of a clue to be able to start writing the function. If they can’t get there, it shows me that they’ve got some trouble wrapping their head around this abstraction. I’ve got a few more hints up my sleeve to help, but if without all of the help I can give, they still can’t come up with that, that’s one mark against them.
But even if they can’t come up with the relation at all, it’s not the end of the interview. I have, sometimes, ended up recommending hiring someone who had trouble this far! If they can’t come up with that basic relation, it’s just one piece of information about the candidate. I’d file that away, and move on, by giving them the recurrence relation, and then I would ask them to code it.
There’s one problem that comes up in coding, which is interesting and important. The most naive code for gray is something like:
def gray(n):
print("gray(%s)" % n)
if n == 0:
return "0"
if n == 1:
return "1"
num_digits = math.floor(math.log(n, 2)) + 1
return "1" + gray(int(2**num_digits - 1 - n))
That’s very close, but not right. If you call gray(10), you get the right answer.
If you call gray(4), you get “110”, which is correct. But if you call gray(8), you’d get “110”, when you should have gotten 1010.
Most candidates make this mistake. And then I ask them to trace it through on 8 as an example. They usually see what the problem is. If they don’t, then that’s another red flag.
If they’re really struggling to put together a recursive function, then I’d ask them to just write a function to convert an integer into standard binary. If they can do that, then I start making suggestions about how to convert that to do gray code.
The big indicator here is whether or not they can write a simple recursive function at all. The systems I was working on at the time made heavy use of recursion – if a candidate couldn’t write recursive code, there was simply no way that they’d be able to do the job. (It was depressing to see just how many qualified-looking candidates came in, but who couldn’t write a simple recursive function.)
Through this whole process, how well they were able to talk about what they were doing was as important as the solution they came up with. If they heard the question, and immediately wrote down perfect, beautiful code, but they couldn’t explain how they got it, or how it worked? They’d get a mediocre rating, which wouldn’t get them a job offer. If they made a lot of mistakes in their code, but they were crystal clear about explaining how they worked out a solution, and how it worked? They’d probably get a better rating than the perfect code candidate.
I hope this shines a bit of light on this kind of interview question. While it’s necessarily artificial, it’s artifical in a way that we hope can help us learn more about the candidate. It’s not a trick question that’s irrelevant to the job, like “Why are manholes round?”: this is an attempt to probe at an area of knowledge that any candidate for a software engineering job should have. It’s not an all or nothing problem: even if you start off with no clue of how to approach it, I’m guiding you through. If you can’t solve it without help, this problem gives me some insight into what it is that you don’t understand, and hopefully whether or not that’s going to be a problem if we hire you.
Is it a great way of doing interviews? Honestly, no. But it’s the best way we know of doing it.
As an interview system, it doesn’t do a good job of identifying the very best people to hire. There’s no correlation between outstanding interview performance and outstanding on-the-job performance. But there’s a strong correlation between poor performance on this kind of interview question and poor performance on the job. Great performers on the job show the same distribution of interview performance as average ones; but poor performers on interviews show a significantly negative-shifted job performance distribution.
We haven’t found a way of interviewing people that does a better job than this. It’s the best we have. Statistically, it works far better at selecting people than “open-ended” interviews that don’t involve any kind of practical programming exercise. So for all of its faults, it’s better that the alternatives.
I’m sure there are pedants out there who are asking “So what’s the correct implementation of gray code?” It’s totally not the point of talking about it, but here’s one sloppy but correct implementation. This isn’t the quality of code I would ever use for anything serious at work, but it’s perfectly adequate for an interview.
import math
def gray(n):
def required_digits(n):
"""Compute the number of digits required to
represent a number in binary
"""
return int(math.floor(math.log(n, 2))) + 1
def pad_digits(gray, num_digits):
if len(gray) < num_digits:
return "0"*(num_digits - len(gray)) + gray
return gray
if n == 0:
return "0"
if n == 1:
return "1"
num_digits = int(math.floor(math.log(n, 2)) + 1)
return "1" + pad_digits(gray(int(2**num_digits - 1 - n)), num_digits - 1)
I’m getting a bunch of “latex path not specified.” in the part that cut and pastes as: “They should be able to come up with “15 – 8” – and to see that in every row n , where n \ge 8 and n < 16, the gray code of n is “1” + gray(15 – n)"
I do a lot of coding interviews for potential candidates, and I think this strategy is one of the worst. You are forcing a particular solution to a very specific problem which allows almost no variation and almost zero demonstration of programming capability. It’s like interviewing a Taxi driver and test if they can reverse through a maze by using only the wing mirror opposite the driver. If they have difficulty, you can “feed” them a way of doing it….. but really, you’ve learnt very little about that persons ability.
I think coding interviews need to leave a lot of choice in approach to the the programmer. Especially important that the problem allows them to partition a problem into a number of functions. In my experience, the better programmers quickly build themselves a set of functions that solve a problem effortlessly, the not so good ones get lots in a mess of blurry ideas poorly implemented.
It depends on exactly what you’re looking for. A good interview isn’t one person asking one question; it’s a bunch of different interviewers, asking different questions, trying to discover different things about the candidate.
In this one, I was interviewing people for very junior engineering candidates, and I was targeting a specific skill area. It does a good job of focusing on what I wanted to discover.
It’s not a problem that I’d use to explore a developers deep programming ability. It’s a problem I’d use to see if a candidate can write basic recursive code – which is an important skill that’s all-too-often lacking in fresh college grads.
Extending part of Mark’s response to Keith’s comment even further…
I think one awkward issue with modern computing/software engineering in general is that the field has grown so much that it’s almost laughable to think of programming/software engineering as a single body of knowledge. If a company posted a job for a “physical engineer” no one would know what they were looking for. Do they want someone who knows about nuclear physics? Transportation systems? the design of everyday things?
Computing is still young enough that its sub-disciplines aren’t that well segregated yet. But I believe that within a (work) generation or two we’ll see much more agreement about what these sub-disciplines are. Then if an organization is looking for someone who can design novel algorithms, there is no need to probe their sys admin skills; if they’re looking for someone who can design effective user interfaces, there’s no need to ask about how to build large-scale distributed systems.
Of course this is already starting to happen to some extent, but I think there’s a lot further to go in the Great Segregation. Part of me is sad about this, because I like knowing as much as I can about all the sub-disciplines in computing. But I think it’s inevitable.
One more additional thing I’d like to mention.
One of the big problems in interviews is that you’ve got very limited time to learn about the candidate. The questions you ask and the approaches you take to those questions have to be carefully matched to the role that you’re interviewing for, to the amount of time that you have to evaluate them, and to the qualifications of the candidates you’re evaluating.
Asking an advanced question to a candidate who can’t write a simple function is a waste of time for everyone involved.
For example, in my days at Google, most of the resume screening was being done by contractors who were paid by the number of resumes that they screened. Even with very cursory screening, they were able to discard more than 9 out of every 10 candidates. But even with that, the vast majority of people that I got to interview were not remotely qualified for an engineering job at Google.
The question I used in this example is, all things considered, extremely easy. It’s five or so lines of code, and in the course of the interview, I’d practically give you most of the answer. But still, more than 4 out of every 5 candidates that I interviewed failed the question.
More than that, even with a great candidate: you’ve got an hour or less to talk to them, and you’re dealing with people who might have a very different way of thinking than you do.
In interview stories, I keep going back to google, because I did something like 120 interviews over three years when I was there – more than 10x more than I’ve done in a similar period of time anywhere else. Because I’d done so many, I was considered a “senior” interviewer, so I got to shadow a lot of new interviewers and critique them. Doing that, I saw way too many interviews go off the rails because the interviewer thought that they had a clever question, and then judged the candidate on how well their performance matched what the interviewer would have done.
I don’t want to defend the gray code question that much; it’s a silly question. The reason that I chose it as an example is that of all of the interview questions I’ve used, it’s the one that most resembles the stereotypical “brain teaser”; so I wanted to show how even something that looks that way can actually be a way of probing specific traits in a candidate.
For all of its silliness, the Gray code question produces one very clear bit of signal: it tells me whether or not a candidate can wrap their head around simple recursion. It’s shocking how many candidates couldn’t do it. Seriously, 4 out of 5 people that I interviewed with that question failed, even with every hint I could provide. I don’t pretend that that tells me that they’re bad programmers, or incompetent engineers. But it does tell me that they can’t deal with simple recursive code. When I was interviewing people to work on a project that’s chock full of recursion everywhere you look, that’s critical information.
Recently I was having a conversation about interviewing with some acquaintances. We got around to complaining about how little information interviews give you. This made me wonder about explicit apprenticeship programs at companies that hire lots of programmers, for candidates with little to no work experience.
The basic idea is that the company would hire a candidate for an explicitly short period of time (6 months, a year, 2 years, whatever). At the end of that time, the apprentice would be welcome to apply for a long-term position, with the assumption that some, but not all apprentices would be hired by that company.
The company gets effectively a hugely extended interview to decide if they want to hire a person long-term. The candidate gets experience at a (presumably) reputable company. Since the company wouldn’t be making long-term commitments to apprentices, they could hire many more than they would hire new programmers, giving them more tickets in the hiring lottery.
Interestingly, I think the current state of the industry resembles this scheme to a certain degree. My understanding is that it’s pretty common for new grads to work at a big company like Google, Microsoft or Amazon for a couple of years, then jump to something else.
Mark, I’m curious if with all your hiring experience this sounds even vaguely plausible. Are you aware of any discussion within Google (or elsewhere) about starting a program like this?
Wait, was this a phone screen question? The way you’d talked about it made me think it was an in-person question.
(Background for people who don’t know Google’s internal procedures: after resumes were screened at Google, there was an interview-by-phone of the candidate by an engineer, not a contractor, to see whether Google should spend the money to bring the candidate onsite for an in-person interview.)
I did most of my Google interviewing doing phone screens, (because most interviewers hated doing phone screens, but I actually preferred them) and there the goal is different – I’m just trying to assess whether they had a chance if brought onsite, and leaned towards bringing them in. Because of that, I wouldn’t do one large question with lots of back-and-forth, but tended to ask four or five shorter questions. Some of those were typical interview questions – “tell me about this thing here on your résumé” – others were short answer technical knowledge-types questions, where I am actually looking for the right answer quickly and don’t care too much what process was behind it. (Since unlike gray code, it’d be something the interviewee was our should have been familiar with) And although I’d also then have a programming question, it was an even shorter one any candidate should be able to write the code out for within 5 minutes. (Using a shared Google Doc) E.g.: “write a function that takes an integer and returns whether that integer is a power of three”.
(This interview style is only really appropriate in an environment where it’s backed by multiple watch-the-candidate-think questions of the kind Mark described)
For those at home, I had most candidates fail the phone screen too. There are people with legitimate résumés indistinguishable from those of good candidates who from what I can tell have no business being in this industry. Then there are plenty more who might be decent in some environments, but had somehow missed the entirety of the web world, and others who just didn’t make the cut for some other reason. (Something I wrote at the time: http://dtm.livejournal.com/38138.html )
Unfortunately in our maze-navigation business our taxis only go in reverse and have one mirror, a wing mirror, that happens to be opposite the driver.
Maybe what I need is a taxi driver that can reverse through a maze using only the wing mirror opposite the driver?
In the table you have grey(8) = 1100. However, in the text later you say “if you call gray(8), you’d get “110”, when you should have gotten 1010.” Seems like you wanted to use gray(12) to trigger the bug, which would be “1” + grey(3), resulting in 1010?
This pedant is more curious about the answer to “Why are manhole covers round?” Ease of installation? Self centering? Aesthetics? Much more puzzling than grey code.
Ah, google reveals its to prevent covers from accidentally dropping through the hole. That makes sense.
It’s a rubbish question because there is no single reason. Plus, not all manhole covers are round, and it’s possible to build a manhole with a non-round cover that can’t fall in. There’s lots of good reasons to make a round cover, but also lots of good reasons to not make a round cover.
It’s a rubbish question for a lot of reasons, including the ones you mentioned.
In my opinion, the biggest one is simply that it’s irrelevant. Unless you’re interviewing civil engineers for a job designing sewers, their knowledge, intuition, or reasoning ability about manhole covers has nothing to do with the job they’re interviewing for.
I mostly interview for “Sysadmin / DevOps / SRE”-like roles (that is, I want at least some, ideally lots, of coding ability, a fairly sound approach to troubleshooting balky production systems and a decent knowledge of Unix systems), which alas is an even wider (although perhaps less deep) field of technical knowledge.
I try to interview candidates to their strengths. That is, unless a candidate says they have good knowledge of assorted internals, I’ll probably skip probing that and focus on what the say they know.
Sometimes, I am delighted to see that a candidate claims to have “good knowledge of bash” and ask them a somewhat artificial question, that nonetheless exposes a fair bit of knowledge and attitude.
The question is “you type the following at a unix prompt, tell me what the output of the last command is:
mkdir foo
cd foo
touch ./-a
touch ./-l
touch ./foo
ls *
”
A candidate with rather good knowledge gives me the right answer (this is OK, but, well, you know…). A good candidate either knows what’ll happen, gives me the answer and why it is that way. Or, equally good, says “I don’t know…” and starts reasoning aloud towards the right answer. A less than stellar candidate will give me the wrong answer and show no willingness to work though what happens. I typically budget 3-5 minutes of interview time for this question (it’s not critical knowledge, but if there’s time and the candidate is a good match for the question…)
And, of course, I may now have to stop using this question, but that’s life.
I have never excelled at technical interviews. For me it has been a lack of comfort more than anything.
The premise (much like gray code) is like an extra credit question on a CS exam only in the interview you have someone in an alien environment (compared to the desk they usually code at while avoiding human contact), they have no compiler, nor have they been studying for a week just for this exam.
If I need to interview a programmer my plan is to emulate CS projects, not exam questions. I’m thinking about putting someone in a quite room with a laptop and a language they claim proficiency with. Then I hand them a simplified CS project and let them code for an hour. I don’t even care if they just google for a solution because they have to defend it in a code review I’m about to have with them. (okay I might care because I don’t want to hire a cheater…)
If they can communicate well with me during the review, then I can work with them. This best emulates my normal work day and most simulates what a day working with me is like.
Am I way off here or is anyone else interviewing like this?