Last week I shared some thoughts about interviewing software engineers and some basic do’s and don’t’s for the interviewer. In this post I will concentrate on one of the more recently controversial aspects of the process: the whiteboard interview.
As I said last week, a lot of people really hate whiteboard interviews, and they have some valid reasons for not liking them. (My thoughts are kind of like the Winston Churchill quote: “Democracy is the worst form of government except for all those others that have been tried from time to time.”) These reasons include, but are not limited to:
- Nobody writes code on a whiteboard so why should we evaluate people on a skill that they never do?
- Writing code on a whiteboard makes people nervous and more likely to make mistakes, so it’s a terrible way to evaluate people.
- Whiteboard interviews favor confident people with good presentation skills, not necessarily good coders.
- There are all sorts of posts, and even entire books, written about how to do well on whiteboard interview questions.
- Whiteboard interviews are prone to bias, rewarding candidates who resemble the interviewer instead of candidates who would perform well in the job.
Okay, so I don’t necessarily disagree with any of those points, but the thing is, a lot of those statements are also true for just about any type of interview. If you are interacting with the candidate in any way, candidates who are confident and poised will tend to do better than other candidates. That has nothing to do with a whiteboard. Interviewers are prone to bias regardless of whether they are reading a resume, or reviewing an application, or having a one-on-one conversation, or conducting a whiteboard interview. To be sure, interviewers need to guard against all those things, but I don’t think they are more or less associated with whiteboard exercises.
I should also say that I myself have had some really embarrassing experiences with whiteboard interviews as a candidate. I have completely bombed some interviews. It can happen to anyone, or at least anyone only as skilled as myself. This isn’t a case of me thinking, well, I am good at this thing so I’m looking for other people who are good at this thing. But I think that experience has given me some insight as to what to look for and a little bit of empathy.
The strongest argument against whiteboards would be that nobody writes code on a whiteboard, and this is absolutely true. Some companies prefer to give candidates a problem to be worked on at home; some have candidates do a joint coding exercise with potential teammates. Blizzard Entertainment has candidates do a joint coding project with other candidates, which I feel is just crazy, but you can’t argue with their results, I guess. My concern with take-home exercises or joint coding exercises is that you’re kind of putting all your eggs in one basket. When I give a whiteboard exercise, I’m not the only one doing so. We have several people giving them. It’s possible that someone could bomb my portion and do well enough in another session to get an offer. With a coding project, you’re probably getting one (larger, yes, but still solitary) piece of data to make a judgement on.
At Carbine we did sort of a pseudo-whiteboard exercise. Instead of a whiteboard, we had candidates type into a plain text editor (Notepad++) that was projected onto a screen that everyone could see. That solved the problem of bad penmanship but I think it had other drawbacks. For one, I can’t do my awesomely terrible curly brace squiggles in a text editor, and that’s actually something I want to do to try to make the candidate more comfortable. More importantly, the presence of an actual text editor seems to make candidates pay even more attention to things I don’t care about like making sure their brackets line up or semi-colons. Also, you can’t draw in a text editor.
The great thing about whiteboards is that if you want to draw a Venn diagram, you just… draw a Venn diagram. If you want to outline a tree structure, draw a tree structure. Finally, and this might just be my perception, people who are typing don’t seem as talkative as people who are using a whiteboard. Something about typing seems to focus more attention on that task, whereas drawing on a whiteboard seems to allow people to still talk. And I am mostly interested in what they are saying as they draw diagrams and write sloppy code on the whiteboard. So, yeah, I use the whiteboard.
One other reason for continuing to use whiteboards will sound really terrible, an appeal to authority or perhaps a bit of cargo cult logic: Google and Amazon still use them. Now, doing something just because someone else does it is not a great reason, but I know a couple things about Google: one, they are obsessive about measuring things. And two, they used to ask “lateral thinking” type questions and they stopped because their metrics showed that there was no correlation between those types of questions and whether someone was a good employee or not.
(An example of a lateral thinking question: “A man rides an elevator down from his 10th floor apartment every day. When he comes home from work, he rides up to the 5th floor and walks the remaining five stories to his apartment, unless it has been raining or there are other people in the elevator, in which case he rides all the way. Explain why.” Don’t ask that question; it won’t help you hire good engineers.)
So Google’s continued use of whiteboards suggest to me that they still have some value, but the real reason I use them is because my own experience has led me to trust them. I find value in them, because I’ve had good results. If they don’t work for you, then don’t use them on my account. The important thing is that you have a set of questions you want to answer about the candidate and a method of getting those answers. Whether that is whiteboard questions, take home projects, joint coding exercises, or whatever works for you, as long as you are comfortable with that process and you are getting good results, that’s what you should use.
So those are my basic thoughts about whiteboards and why I still use them, despite the legitimate concerns that people have about them. As I said in Part I, if you design the very best possible interview process, you will still be left with incomplete information. Whiteboard questions might be the worst way to evaluate engineers, except for all the others.
Okay, so that’s about a thousand words and I still haven’t given an example of an actual whiteboard question yet. I have several questions that I use in interviews, but I’m not going to tell you what they are because… I still use them. Also, at least three of them are whiteboard questions that I myself have been given by other companies at one time, and it would be rude of me to post answers here. So I’m going to share one that I made up, and I think is pretty good, but I don’t ever plan on actually asking a candidate.
Imagine you are given some number of integer arrays, each with some number of integers in them. I need a function that will return all the integers, in order, that appear in one, and only one, of these arrays.
I will then draw a Venn diagram that looks something like this:
And I will draw (after apologizing for my horrible curly braces!) an example of the data that might be passed to this function:
{2, 4, 6, 10, 30}
{3, 6, 9, 15, 30}
{5, 10, 15, 25, 30}
And my expected result: {2, 3, 4, 5, 9, 25}
Then I hand them the marker and say, “go.” Usually what happens next is that they stand at the whiteboard and stare at it. After about 2 seconds I’ll say, “Oh, and by the way, if you stare silently at the whiteboard for 10 minutes and then write out a perfect solution, that would be really impressive but I would much rather you think out loud so I can get a feel for how you’re thinking about this problem.”
So, if you are thinking to yourself, “wait, wait, that’s not enough information” then you are exactly right. I have been deliberately vague in defining this problem because I want to get an answer to one of my questions about this candidate: “Did she ask clarifying questions?” There are several questions that could be asked about this problem as I have defined it. First, are the input arrays always sorted? (Yes.) Are there ever duplicate values in any of the input arrays? (Nope.) Are the sizes of the input arrays always the same? (No.) Can I modify the input arrays? (Hmm, let’s say no.) What language should I use? (Your choice.) How about Haskell? (Um… no.) So hopefully the candidate will ask at least one of these questions or possibly some other questions.
(Note that while I will often be deliberately vague in defining a whiteboard question, I won’t mislead the candidate. I don’t do trick questions. I’m not trying to stump anyone.)
If the candidate asks one of those questions, I will respond with “good question!” and give them the answer. I really want to reward them for asking a good question and hope they will continue to do so. You’re doing great, keep it up. Also, I get to make a little plus in my notebook.
So if they don’t ask any of these questions and just start writing code I’ll observe for a bit to see if they are operating under the correct assumptions. If they are, then I’ll let them go, but if I think they might not be, I’ll interrupt and say, “oh, I should have said that the input arrays are sorted,” or whatever. I phrase that deliberately to make it my fault that I didn’t give them all the information. Hey, we’re all human here; relax, you’re doing fine.
So if they don’t ask a clarifying question is that a deal breaker? No, not even close. It’s definitely a plus if they do, but it’s just one piece of information, especially if the assumptions they have made all turn out to be correct. (The way I’ve written out the problem implies the answer to those questions, but it’s better to confirm them.)
As soon as they start writing code I get an opportunity to answer another one of my questions, “Did he ‘define the contract’ (API)”? Basically I’m looking for the function signature for the code about to be written. This is really important because it defines what the customer (in this case, me) wants from the program and what the engineer is promising to deliver. Nailing this down is really important. I’ve had candidates just start writing code with some variable definitions and a for loop. When this happens I will stop them and say, “let’s write the function declaration first.”
Depending on the problem this can lead to some interesting questions and discussions. Should the output be a return value or a pointer/reference parameter? Should any of the parameters be constant and why/why not? You can sometimes get a feel for a candidate’s experience level how this API is defined. Again, be cautious; it’s one data point, not a deal breaker if they screw this up. They could be trying something clever to impress you or they could just have a brain freeze; it happens.
For this particular problem, let’s assume that they come up with a function declaration that looks like this:
void UMI(const vector<int> *arrays, int arrayCount, vector<int> &out)
This is C++ of course, using the standard template library. UMI stands for Union Minus Intersection, which is kind of clumsy but okay. We’re going to accept a pointer to an array of constant int arrays, the number of arrays, and a reference to an out array parameter. Is this the best possible function declaration? Probably not, but I’m using it because it is convenient for showing different approaches to solving the problem.
Okay, so let’s assume that your candidate starts drawing and talking and after 10 minutes or so comes up with something like this:
void UMI(const vector<int> *arrays, int arrayCount, vector<int> &out)
{
out.clear();
for(int i = 0; i < arrayCount; i++)
{
const vector<int> &a = arrays[i];
for(auto ai = a.begin(); ai != a.end(); ai++)
{
bool duplicate = false;
for(int k = 0; k < arrayCount; k++)
{
if(k == i)
continue;
const vector<int> &a2 = arrays[k];
for(auto ki = a2.begin(); ki != a2.end(); ki++)
{
if(*ai == *ki)
{
duplicate = true;
}
}
}
if(!duplicate)
{
out.push_back(*ai);
}
}
}
std::sort(out.begin(), out.end());
}
Okay, so good news is that we’ve answered one question, “Did she get a valid solution?” affirmatively here. This code will run and it will get the right answer. That’s not insignificant. Sadly, many candidates you interview will not get a valid solution to the problem you are presenting, so something like this isn’t the worst thing you’ll see. That said, it’s not great.
This is an n2 solution, where n is the total number of items in all the arrays. Now, for the small data set that I’ve given in my example, this will run in 0.0 milliseconds. No problem. But as n grows…. yeah, things get messy.
So now we can start to answer some of our other questions, “could he have a discussion about complexity?” Ask the candidate what the runtime complexity in big-O notation of this solution is. Can he tell you it is n2? Does he understand that is not desirable? I’ve had candidates tell me they don’t know all the big-O notations for common algorithms by heart, and I’m like, that’s fine, that’s easily found. But I’ve also had candidates tell me that they don’t really care about big-O notation, and that’s… not as fine. I mean, it’s a weird thing to say to an interviewer because obviously I asked about it so I probably care.
So I often get n2 or similar type answers to whiteboard problems, and I will ask, “how can we improve this answer?” We’ll talk about it some more and I will often give them enough hints to get to a better answer. Sometimes they will offer improvements on the solution they’ve already provided. For example, in the solution above, the candidate might suggest breaking out of the innermost for loop when the inner value being tested exceeds the outer value. That’s a pretty good improvement, but it’s only an incremental change. It doesn’t fundamentally change the runtime complexity of the solution; it will still be n2. Do they understand that? There’s a lot of room for discussion here and a lot of information about the candidate that can be discerned.
So would this solution be a deal breaker? Again, no. A lot of candidates will go right to the naive solution because they want to get a working, valid solution on the board. I’ve had really good engineers say they always start with the naive solution and use it as a test case to confirm their trickier, more optimal solutions. The important thing is that they should be able to understand why the complexity matters.
Okay, now let’s look at another possible solution to this problem, this time using an ordered map.
void UMI(const vector<int> *arrays, int arrayCount, vector<int> &out)
{
map<int, int> counts;
out.clear();
for(int a = 0; a < arrayCount; a++)
{
for(auto i = arrays[a].begin(); i != arrays[a].end(); i++)
{
auto mitr = counts.find(*i);
if(mitr == counts.end())
counts[*i] = 1;
else
mitr->second++;
}
}
for(auto mitr = counts.begin(); mitr != counts.end(); mitr++)
{
if(mitr->second == 1)
out.push_back(mitr->first);
}
}
Okay, so this code is much better. It dumps all the values from all the arrays into a map and keeps track of all their counts. Afterwards, it adds any value with a count of one to the out array. The runtime complexity of this solution is n log n, which is a major improvement.
Again, if someone comes up with this solution, we can answer all those questions that we answered before. Does she understand why the complexity is n log n? Can she have a discussion about it?
So if I got this solution I’d still ask the candidate, can we make this solution better? This is going to be harder to do; it’s not as low-hanging fruit as the naive solution. The key to getting a better solution here is to point out that the arrays are already sorted, so putting them all into a map is duplicating effort. We don’t need to do that. Instead we can look at the “frontier” (the first element) of all our arrays and look for the lowest value. If that lowest value is unique, then we can add it to the out array and increment the iterator on that array. If it is not unique, we increment all the iterators for that value and look at the next lowest value. We do this until we have looked at all elements in all arrays.
This is the kind of problem where I think the whiteboard is a help. The way to implement what I described is to have a heap (or priority queue) of all the arrays. With a whiteboard a candidate can just say, “I’m going to make a heap of all these arrays, sorted such that the lowest value pops to the top” and I’ll say, “yep, sure.” I don’t need them to write that heap. If someone describes a weird data structure that I’m not familiar with, I might ask them to sketch out how it works, but I’m good with just hand-waving a heap. I don’t care if they don’t get the exact syntax right for defining their templates or the exact function calls (is it pop() or pop_front() or…?) for using them.
Here’s the code to implement that algorithm.
class BookmarkedArray
{
const vector<int> *m_array;
vector<int>::const_iterator m_itr;
public:
BookmarkedArray(const vector<int> *ar) : m_array(ar)
{
m_itr = m_array->begin();
}
bool operator < (const BookmarkedArray &other) const
{
return (*m_itr < *other.m_itr);
}
bool operator > (const BookmarkedArray &other) const
{
return (*m_itr > *other.m_itr);
}
const BookmarkedArray &operator =(const BookmarkedArray &other)
{
m_array = other.m_array;
m_itr = other.m_itr;
return *this;
}
bool AtEnd() const
{
return m_itr == m_array->end();
}
int Value() const
{
return *m_itr;
}
void Next()
{
m_itr++;
}
};
void UMI(const vector<int> *arrays, int arrayCount, vector<int> &out)
{
priority_queue<BookmarkedArray, vector<BookmarkedArray>, std::greater<BookmarkedArray>> q;
for(int i = 0; i < arrayCount; i++)
{
q.push(BookmarkedArray(arrays + i));
}
out.clear();
int currentValue = 0;
int currentCount = 0;
while(!q.empty())
{
if(currentCount == 0)
{
BookmarkedArray ba = q.top();
q.pop();
currentValue = ba.Value();
currentCount = 1;
ba.Next();
if(!ba.AtEnd())
q.push(ba);
}
else
{
BookmarkedArray ba = q.top();
q.pop();
int value = ba.Value();
ba.Next();
if(!ba.AtEnd())
q.push(ba);
if(value == currentValue)
{
currentCount++;
}
else
{
if(currentCount == 1)
{
out.push_back(currentValue);
}
currentCount = 1;
currentValue = value;
}
}
}
if(currentCount == 1)
{
out.push_back(currentValue);
}
}
On a whiteboard, I don’t care about the BookmarkedArray class. Saying you have a heap of arrays is fine. But in a full IDE, I have to define it, and it’s wasting time. I want to talk about this algorithm, not waste time getting the syntax exactly right.
So the time-complexity of this function is n log q, where q is the count of arrays instead of the number of items in the data set, or n. That can be a pretty significant savings. So running all these different approaches to the same problem on a data set of 421,021 items in 15 arrays leads to some eye-opening results. (Source code here.) All three of these approaches produce the exact same output, but the time is significantly different:
UMI naive (15 arrays) = {19999 multiples of 5}
Array sizes = {28033, 28081, 28150, 28065, 28074, 28094, 28037, 28111, 28035, 28
071, 28103, 28038, 27978, 28071, 28080, } = 421021 total elements.
Elapsed ticks = 110367
UMI using map (15 arrays) = {19999 multiples of 5}
Array sizes = {28033, 28081, 28150, 28065, 28074, 28094, 28037, 28111, 28035, 28
071, 28103, 28038, 27978, 28071, 28080, } = 421021 total elements.
Elapsed ticks = 319
UMI using heap (15 arrays) = {19999 multiples of 5}
Array sizes = {28033, 28081, 28150, 28065, 28074, 28094, 28037, 28111, 28035, 28
071, 28103, 28038, 27978, 28071, 28080, } = 421021 total elements.
Elapsed ticks = 10
Complexity matters! Now I’ve heard people in the game industry say that our datasets are usually small enough that understanding complexity isn’t crucial, but I completely disagree. I have seen, and the industry is full of similar stories, cases where a designer comes up with a feature request and an engineer codes it up and it works great. It sails through QA with no problems. Then it gets released out into the wild and the whole game blows up because the largest number of concurrent players it was tested with was like 2. And it’s an n2 or worse, n! solution. And 22 is only 4 and 2! is only 2, but 1,0002 is a million and 10! is even bigger. This stuff matters.
Okay, so I hope that has given you something to think about as you think of how to go about evaluating potential engineering candidates. As I’ve said, whiteboard exercises work for me, but they might not work for you, and that’s okay. The important thing is that you have a strategy for answering the questions about the candidate that you need answered to make the best decision you can.
Thanks for reading. I hope to post some thoughts about diversity soon.
Part I here.
Some Disagree 