How to Conduct a Good C++ Phone Interview

I’ve interviewed dozens of software engineers, mostly to fill positions involving C++. I’ve also interviewed for about a dozen positions involving C++ and lots of other technologies and languages. I thought I’d share some good on-the-phone interviewing techniques for the interviewer for C++ positions.

Before you read this, you shoud know that my interviewing technique is mostly inspired by Joel Spolsky’s Guerilla Guide to Interviewing, which is a great read, though a little extreme for hiring programmers.

I also very much enjoy Steve Y’s writing on hiring and interviewing, particularly his article on phone interviews.

These questions usually take between 30 and 45 minutes to ask. A great candidate will answer all these and more in less than 30 minutes. A poor candidate will only get through half of them in 45 minutes. I’ve divided each question into sections. Some questions are not a single question per se, but more of a discussion topic. Enjoy!

Removing Duplicates from a List

The first thing I ask candidates is how to remove duplicates from a list. There are basically three answers to this question, and I want the candidate to give me all three, with the advantages and trade-offs of each. If they can only get two of them, I might hint them along to the third. If they still can’t get the third answer, I almost never hire them.

The great candidate will ask me lots of questions up front, like what my data structure is. Is it a linked list or an array? What’s the penalty for removing an item from the structure? Does it have random access of elements? These are all great quesions. I usually let the candidate assume that indexing is O(1), and so is removing items from the list. Good candidates will ask if the list is sorted first or not. Are the elements hashable? Are the elements easy to compare to eachother? If the candidate dives right into the answer without asking any of these questions, I usually don’t hire them. Here are the three answers I want to get from the candidate:

Answer 1: The dumb way (N2)

For each element in the list, scan the rest of the entire list and remove matching elements.

Advantages: Easy to implement. No extra memory required.

Disadvantages: It’s O(N2) slow, and on large lists it’ll take a long time.

If they skip this one, and go straight to answer #2, that’s just fine (even preferable).

Answer 2: The adequate way (N log(N))

Sort the list first. For each element in the list, look for duplicate neighbors only and remove them.

Advantages: Faster than Answer 1 because you don’t have to iterate over the entire list for each element. No extra memory required. Pretty easy to implement.

Disadvantages: It’s pretty good in most cases, but still not the (theoretical) fastest way.

Answer 3: Hash the elements

For each element in the list, insert it into a set structure that uses a hashing algorithm. When done, just pull out the values, and that’s your unique list.

Advantages: Very fast (theoretically), on the order of O(N).

Disadvantages: You may choose a poor hashing algorithm and end up with a much worse speed. Implementing a reliable hashing algorithm can be hard, so you’ll have to find one (like the non-standard hash_set class). It also uses much more memory than the other two answers (bonus: What is the memory complexity of this implementation).

As you can see, this question is not about “right or wrong”, it’s about how many solutions they can come up with, and whether they are able to adequately weigh their chosen solutions. This tells you a lot about a candidate. Note also that this is not strictly a C++ question.

Counting the Bits in a Byte that are One

In this question we want to see if they understand the C/C++ bit-wise operators. This may not be important if your position doesn’t do a lot of bit twiddling, but it is for my job, so I always ask it. There are several ways to answer this question, again, so I’m seeing how far they’ll take it. Again, I want good questions, like how much memory is available to them and whether performance is important.

Answer 1: Mask, compare, shift, mask, compare, shift, repeat

In this answer, you “and” the byte with one, and compare the result with one, then shift right by one bit, and repeat it seven more times, like this:

    unsigned char input = (some value);
    int count = 0;
    if (input & 1) count++;
    input >>= 1;
    if (input & 1) count++;
    input >>= 1;
    if (input & 1) count++;
    input >>= 1;
    ...

Of course, they could just use a loop like this:

    unsigned char input = (some value);
    int count = 0;
    for (int i=0; i<8; i++) {
        if (input & 1) count++;
        input >>= 1;
    }

I’ve seen some fun variations on this, like using the modulus operator (%) and the divide operator (/) instead of shifting and masking. Basically, in this case you are checking for “oddness” of the input byte and dividing by 2 each time (which is the same as right-shifting), like this:

    unsigned char input = (some value);
    int count = 0;
    for (int i=0; i<8; i++) {
        if (input % 2 == 1) count++;
        input /= 2;
    }

That’s a fun one, and shows that, even though the candidate may not know the bit-wise operators well, at least he can improvise. We hired a candidate who gave this answer about a year ago. He told me on the phone that he didn’t know the bit-wise operators, so I thought for sure that he wouldn’t get the right answer, but he did! He turned out to be an awesome employee too (yes, Chris, I’m talking about you). :)

Answer 2: Short-circuited version of the above

You can modify the above to not iterate all 8 times, if not necessary, by changing the “for” loop to a “while” loop, like this:

    while (input) {
        ...

That way, it’ll bail out as soon as the input hits 0 (which it will eventually), and it may happen sooner than 8 iterations. Actually, it’ll happen that way more than half of the time. Ask the candidate in what cases would this save you a step (answer: it’ll iterate at most 7 times for inputs less than 128, 6 times for inputs less than 64, 5 times for inputs less than 32, and so on).

Answer 3: Lookup Table

This is the fastest implementation to count bits, but it requires a pre-initialized array with 256 entries in it. It goes like this:

unsigned char input = (some value);
static int table[256] = { 0, 1, 1, 2, 1, 2, 2, 3, 1, ..., 6, 6, 7, 7, 8 };
int count = table[(int)input];

The table takes byte values as inputs and returns the number of bits that are set in the byte. It must be pre-computed and statically-initialized to be fast. This works well because a byte can only have one of 256 values. If they can’t get this answer, I will often hint them to it by asking, first, “Can you think of a faster solution if you have some memory available to you?” If they can’t get it with that hint, I’ll ask, “Can you think of a table-driven approach?”. If they can’t get it with those hints, I usually don’t hire them. If they do really well on the rest of the questions, I may still hire them.

After they give this answer, you’ll want to ask them about statically initialized data. They should understand that it’s basically free to initialize. They should also know that if they don’t statically declare that table, there will be a significant performance penalty.

Object Oriented

To get a feel for the candidate’s understanding of object oriented programming, I like to ask them what polymorphism is. They usually come up with an example (the zoo, shapes, or cars usually). They talk about how having a common “Animal” base class is good because all Animal-derived classes can share data. This is a good answer, but the better answer is that a common ZooManager could treat all Animal-derived classes exactly the same, without having to know about each individual child class (Monkey, Elephant, etc).

I follow this question up with a question about C++’s “virtual” keyword, and what it means when a class member function is declared as virtual in, say, the Animal class previously mentioned. Candidates tend to get this one right about 50% of the time.

When a candidate is really good, we can get into a discussion about C++ multiple inheritance and the “unfavorable diamond” problem, and how to solve it with virtual inheritance. I’ve only had three candidates get that far with this question, and in all three cases, we hired them.

Understanding Networking

First I ask the candidate if they have any network programming experience. Bare in mind that most of our candidates have less than 5 years of experience. If they do have networking experience, I ask them the difference between TCP and UDP. I also ask them the difference between blocking and non-blocking network I/O.

Threading

First let me just say that I am astounded how few candidates have any multi-threaded programming experience. I am blown away by it. If the candidate has any threading experience, I ask them what a mutex is, what a semaphore is, and what deadlock is. I then ask them to give an example of a producer/consumer problem.

I also ask what the difference is between a thread and a process. If they come up short, I ask them follow-on questions like whether processes share memory, and whether threads share memory. Then I take it further, and ask if processes share heap or stack and if threads share heap or stack.

GUIs

If the candidate has any GUI-programming experience, I ask them why polymorphism is useful to GUIs. Usually they say something about how widgets (a.k.a. controls) can share common data like size and position. That is about 25% of the answer. That’s just data sharing. The real answer is that the GUI’s layout and event-dispatching code can treat all widgets identically. This means that widgets can re-implement specific functionality and the event-dispatcher (a.k.a, the event loop) can treat them all the same, even user-invented widgets. Widget-specific code, like painting, can be delegated to each widget without the rest of the toolkit having to know about it. The way Qt does this for example, is that there is a common QObject base-class, and a common QWidget class that inherits from it. QObjects can emit signals that can be connected to other QObject slots. QWidgets have an API for painting, sizing, etc., and can be sub-classed by users. Qt can treat these custom classes just like it does all the built-in QWidgets.

If they seem to have any significant GUI experience, I will ask them to send me screenshots of their work. I don’t require anything spectacular (we’ll teach them that on the job), but I do want to know if they have done anything beyond your basic CRUD application. I seriously don’t care if someone has developed GUIs that even a computer could create. Show me something cool!

I also ask them what an event loop is, and what it does. I have yet to get a good answer to this one. If they do have a good answer, that usually means they are a great GUI programmer. If they don’t, that just means they aren’t great yet. :)

Embedded

If the candidate has any embedded programming experience, I ask them what an interrupt is and what the “volatile” keyword does in C. If they have any idea about either of them, it usually means that they actually did some embedded programming.

Well, that’s pretty much it. Not too tricky and not too long. I can usually figure out whether to bring in a candidate for in-person interviews based on these questions alone. In some cases, I need to do some more work to get a better feel. For really excellent candidates, I can tell after their answer to the first question. About 90% of the time, when I bring in a candidate after passing this phone interview, they end up passing the rest of the in-person interviews.

I hope you find this information useful!

9 comments to “How to Conduct a Good C++ Phone Interview”

You can leave a reply or Trackback this post.
  1. You wouldn’t have hired me. I was in an interview where I was asked the bits problem (or one similar anyway, it may not have had to do with bits but with stuff in a datastructure). I did it several different ways. They asked for faster. So I optimized it several different ways. I discussed with them the tradeoffs in space and time of everything I was doing. But I missed the lookup table approach.

    Did I not know how to do lookup tables? No, of course I knew. Am I a boring fool that can’t think outside the box? I don’t think so, but who knows? Would I have come up with the lookup table in the real world? Probably. I would say *definitely*, if it was the least bit important. If the speed of my program in some inner loop depended on the speed of this bit counting, I could certainly find my way to the lookup table. But in the *real* world, programmer time is usually much more important.

    So, because I’m not focused on premature optimization, because I was in a stressful interview situation, because I was being led on with vague questions and non-hints (not how you interact with a customer in the real world), and because I just assumed that they wanted clever and not simple because they were asking me stupid pony trick questions in the first place, I didn’t pass their muster.

    I feel that I was the ideal candidate for the job I was interviewing, though in retrospect I’m very glad I didn’t end up tied down to it because I don’t think it would have been very good for me or my career. I feel like they lost out because they were fixated on their little test that nobody worth their salt could possibly get wrong. Alas, it’s not so cut and dry. I don’t even stress out in interviews – imagine a candidate that does stress out in interviews.

    All that said, I do like what you’ve said here. The bit about if the candidate is asking questions, seeing how they approach the problem, etc. You can learn a lot more about how good they are or can be by how they approach the problem, whether they ask the important questions, etc. than by whether they actually get to the answer in a short stressful non-real-world interview.

  2. Hans,

    Great comment. I’m not saying that I won’t hire someone on the sole grounds of them not being able to come up with the bit-counter table. I’m just saying that all the candidates who couldn’t come up with it, (even when asked “Could you implement a table-driven approach?”) did so poorly on the rest of the interview that I didn’t hire them.

    Seriously, if I say, “Could you come up with a table-driven approach?” and you give me a blank stare, I’m not going to hire you.

    I’m 100% sure that I *would* have hired you Hans. :)

    –Dave

  3. What about the planes? The planes! Is it that cold still in Utah?

  4. Yes, it is that cold. :( We have about a foot of snow outside my house right now.

    The real reason is that I had a new baby two months ago, and that has taken up all my time. I haven’t so much as shaken the dust off my Styker or Yak since her birth.

    I think March ought to be a good flying month. Fingers crossed!

  5. Dave, you might need to double check your understanding of what polymorphism is. It should be different objects responds to the same method differently.

  6. Steve, good clarification. That is a good, succinct definition, but in an interview, I want the candidate to explain why that is useful, and even better, how they have used that to solve their problems. The definition is only the beginning.

  7. http://Zach says: -#1

    What do you do when the interviewee responds to the bit counting question by mentioning that if youre on a CPU that supports SSE4 instructions, you can do it in a single assembly instruction, POPCNT.

    :)

  8. Zach, you’re hired!

  9. http://Herve says: -#1

    I had a phone interview, almost same questions and of course missed it despite of my 10+ years of experience in SW development. Was being asked about virtual inheritance and I forgot what that is about, since I haven’t used it (or needed to use it) in any of my recent projects. The 2nd point I missed was interrupts. Of course I know what interrupts are but I might have been fooled in the way the question was asked so I answered I haven’t used interrupts recently (actually I meant, I dropped interrupt usage in my recent embedded project as the performance was slower than a direct polling).
    Well, I’m tempted to think, too bad for the hiring manager as he might have missed a good candidate.
    To make a short story, I’ve always managed to stand out in interviews requiring little in-depth tech questions and got hired, and also got the employers really happy about my work performance.

Write a Reply or Comment

Your email address will not be published.