Wednesday, May 25, 2011

A Taxonomy of Coding Interview Questions

As I noted previously, I think of myself as a talented developer, but I haven't done well at coding tests at recent job interviews. My ego demands I believe that doing well in coding interviews is a learnable skill. I have set out to master it.

I'm actually developing a methodology for passing coding interviews. The first step, as in all sciences, is taxonomy. Philosophers of old sought (magical) power over a problem by saying it's true name. Today we break the problem down into classes that share common properties we can exploit. To this end, I have encountered the following types of coding tests.
  • Basic Skills Test: These questions are meant to test your familiarity with the basics of programming. Common problems in this class include reversing a string, tokenizing a string, and the recently popular fizzbuzz. I can't count the number of times I've coded atoi() or strtok() over 30 years of interviews.

    Unless you're a poser, these tests are supposed to be easy. The trick for senior devs is not to feel insulted that you are being asked to solve such a simple problem. When I was younger and less humble, I would bring a printed copy of atoi() with me to prove how smart I was. Nobody was impressed. They just asked a different question.

    I understand the need to test a candidate's ability to do basic coding. I might be a poser who cannot write any code at all. It's shocking but true that there exist people who make a living by fabricating resumes, then briefly take high-paying jobs as engineers, until somebody figures out they are frauds. However, when I get five basic-skills questions in a row at an interview, it definitely lowers my opinion of a prospective employer. Such an employer is looking for a code monkey, not a senior software engineer, or they'd ask some design or methodology questions.
  • Data Structures Test: These questions are designed to gauge the depth of your familiarity with well-known data structures. Code I've been asked to write recently includes inorder binary tree traversal (recursive and iterative), heap insert, and breadth-first tree traversal. A lot of non-coding questions also test how comprehensive your data structure knowledge is.

    Most data structure questions are not too hard if, indeed, you went to college and paid attention in Algorithms & Data Structures class. These questions pose a problem for the self-taught, no matter how gifted they are on workaday coding tasks.

    If you're applying for a senior position, the questions will be more challenging, and may involve obscure data structure tricks. Maybe these trick questions are supposed to be lateral-thinking tests; the coding test descendents of those "Why are manhole covers round?" tests for which Microsoft was once famous. My experience is if you don't know the trick, you will be frustrated and out of time before the interviewer offers a key hint.

    For instance, heap insert is simple enough to code, if you happen to know the trick of implementing the heap in an array so that there are formulas to compute the index of the parent and children of any node. You may have seen heap insert described briefly, using a tree diagram to show the state of the heap. This memory takes you down the wrong path. Try to work it out from first principles using the heap property and a linked tree-node data structure with no parent link (like I did, ouch), and you're toast; it's too hard to do in one interview session.

    Another question I was asked recently was “find the inorder successor of a node iteratively”, which can be coded in a few minutes if nodes have an extra link to the parent node. For senior developers, the more comfortable you are with tree data structures, the less likely it is that you will consider this unusual extra pointer.
  • Algorithm Test: The basic questions in this category include all manner of “iterate over an array where the entries have global property X” questions.

    The algorithm test is the most challenging class of questions for me, because these problems require the most concentration, and some original thought, not just recall. Standing at the whiteboard, solving an unfamiliar problem, trying to talk about what I'm thinking, while the interviewer watches the clock, is not my preferred way to concentrate.

    In applying for senior positions, I have been given problems of significant complexity; finding the longest palindrome, two-dimensional divide and conquer, dynamic programming chores that look like they should have a simple inductive recurrence relation but don't. indeed, I have been asked questions so difficult that the interviewer did not actually understand the problem or its solution, and offered incorrect hints. I gotta say, they could as well have not wasted their time and mine by inviting me to such an interview. It's outrageous.


  1. Dang, Kurt, you sure are an interview veteran -- you make me feel guilty for giving you that interview. :-)

    I've given several dozen, and FWIW, I don't think it's useful to give "hard" questions for the reasons you've mentioned. Thinking under pressure isn't easy, and I've seen absolutely no correlation between interview performance and job performance. How to find a good candidate, though?

  2. Coding tests are probably best for candidates 0-5 years out of school. Experience based questions are probably relevant for more, um, senior candidates; "Think of a time when you had a really difficult design problem to solve. Describe the problem and the steps you took in solving it."

    I was asked a wonderful Agile question. "I'm assisting a high school teacher lead a robot design class that is going to participate in the 'Robot Challenge' in 3 months. They've already been working with motors and controllers, but will get the actual problem to solve next week. With what you know about development, advise me how you would organize these raw beginners and keep them on track?"

    OO design problems, optimization questions, experience questions, "When would you disable a constructor?" They don't teach this stuff in school. You have to learn it. If you care about the work you do, you probably did learn it.