\nI’ve interviewed dozens of software engineers, mostly to fill positions involving C++. I’ve also interviewed for<\/b> 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<\/b> for C++ positions.\n<\/p>\n
\nBefore you read this, you shoud know that my interviewing technique is mostly inspired by Joel Spolsky’s Guerilla Guide to Interviewing<\/a>, which is a great read, though a little extreme for hiring programmers.\n<\/p>\n \nI also very much enjoy Steve Y’s writing on hiring and interviewing, particularly his article on phone interviews<\/a>.\n<\/p>\n \nThese 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!\n<\/p>\n \nRemoving Duplicates from a List<\/b>\n<\/p>\n \nThe 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.\n<\/p>\n \nThe 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:\n<\/p>\n \nAnswer 1: The dumb way (N2<\/sup>)<\/b>\n<\/p>\n \nFor each element in the list, scan the rest of the entire list and remove matching elements.\n<\/p>\n \nAdvantages: Easy to implement. No extra memory required.\n<\/p>\n \nDisadvantages: It’s O(N2<\/sup>) slow, and on large lists it’ll take a long<\/b> time.\n<\/p>\n \nIf they skip this one, and go straight to answer #2, that’s just fine (even preferable).\n<\/p>\n \nAnswer 2: The adequate way (N log(N))<\/b>\n<\/p>\n \nSort the list first. For each element in the list, look for duplicate neighbors only<\/b> and remove them.\n<\/p>\n \nAdvantages: 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.\n<\/p>\n \nDisadvantages: It’s pretty good in most cases, but still not the (theoretical) fastest way.\n<\/p>\n \nAnswer 3: Hash the elements<\/b>\n<\/p>\n \nFor 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.\n<\/p>\n \nAdvantages: Very fast (theoretically), on the order of O(N).\n<\/p>\n \nDisadvantages: 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<\/b> 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).\n<\/p>\n \nAs you can see, this question is not about “right or wrong”, it’s about how many<\/b> 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.\n<\/p>\n \nCounting the Bits in a Byte that are One<\/b>\n<\/p>\n \nIn 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.\n<\/p>\n \nAnswer 1: Mask, compare, shift, mask, compare, shift, repeat<\/i><\/b>\n<\/p>\n \nIn 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:<\/p>\n Of course, they could just use a loop like this:<\/p>\n 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:<\/p>\n 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). :)\n<\/p>\n \nAnswer 2: Short-circuited version of the above<\/b>\n<\/p>\n \nYou can modify the above to not iterate all 8 times, if not necessary, by changing the “for” loop to a “while” loop, like this:<\/p>\n 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).\n<\/p>\n \nAnswer 3: Lookup Table<\/b>\n<\/p>\n \nThis is the fastest implementation to count bits, but it requires a pre-initialized array with 256 entries in it. It goes like this:<\/p>\n 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.\n<\/p>\n \nAfter 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.\n<\/p>\n \nObject Oriented<\/b>\n<\/p>\n \nTo 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).\n<\/p>\n \nI 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.\n<\/p>\n \nWhen a candidate is really<\/b> 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.\n<\/p>\n \nUnderstanding Networking<\/b>\n<\/p>\n \nFirst 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.\n<\/p>\n \nThreading<\/b>\n<\/p>\n \nFirst let me just say that I am astounded how few<\/b> 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.\n<\/p>\n \nI 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.\n<\/p>\n \nGUIs<\/b>\n<\/p>\n \nIf 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.\n<\/p>\n \nIf 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<\/b> on the job), but I do<\/b> want to know if they have done anything beyond your basic CRUD<\/a> application. I seriously don’t care if someone has developed GUIs that even a computer could create<\/a>. Show me something cool!\n<\/p>\n \nI 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. :)\n<\/p>\n \nEmbedded<\/b>\n<\/p>\n \nIf 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<\/b> some embedded programming.\n<\/p>\n \nWell, 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.\n<\/p>\n \nI hope you find this information useful!<\/p>\n","protected":false},"excerpt":{"rendered":" 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 […]<\/p>\n","protected":false},"author":2,"featured_media":0,"comment_status":"closed","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[2],"tags":[],"class_list":["post-78","post","type-post","status-publish","format-standard","hentry","category-code-and-cruft"],"_links":{"self":[{"href":"https:\/\/thesmithfam.org\/blog\/wp-json\/wp\/v2\/posts\/78","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/thesmithfam.org\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/thesmithfam.org\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/thesmithfam.org\/blog\/wp-json\/wp\/v2\/users\/2"}],"replies":[{"embeddable":true,"href":"https:\/\/thesmithfam.org\/blog\/wp-json\/wp\/v2\/comments?post=78"}],"version-history":[{"count":3,"href":"https:\/\/thesmithfam.org\/blog\/wp-json\/wp\/v2\/posts\/78\/revisions"}],"predecessor-version":[{"id":1573,"href":"https:\/\/thesmithfam.org\/blog\/wp-json\/wp\/v2\/posts\/78\/revisions\/1573"}],"wp:attachment":[{"href":"https:\/\/thesmithfam.org\/blog\/wp-json\/wp\/v2\/media?parent=78"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/thesmithfam.org\/blog\/wp-json\/wp\/v2\/categories?post=78"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/thesmithfam.org\/blog\/wp-json\/wp\/v2\/tags?post=78"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}\r\n unsigned char input = (some value);\r\n int count = 0;\r\n if (input & 1) count++;\r\n input >>= 1;\r\n if (input & 1) count++;\r\n input >>= 1;\r\n if (input & 1) count++;\r\n input >>= 1;\r\n ...\r\n<\/pre>\n
\r\n unsigned char input = (some value);\r\n int count = 0;\r\n for (int i=0; i<8; i++) {\r\n if (input & 1) count++;\r\n input >>= 1;\r\n }\r\n<\/pre>\n\r\n unsigned char input = (some value);\r\n int count = 0;\r\n for (int i=0; i<8; i++) {\r\n if (input % 2 == 1) count++;\r\n input \/= 2;\r\n }\r\n<\/pre>\n\r\n while (input) {\r\n ...\r\n<\/pre>\n\r\nunsigned char input = (some value);\r\nstatic int table[256] = { 0, 1, 1, 2, 1, 2, 2, 3, 1, ..., 6, 6, 7, 7, 8 };\r\nint count = table[(int)input];\r\n<\/pre>\n