Over the past three years, I’ve easily done over a thousand technical interviews, each of which involved having the candidate write code on a whiteboard, either in person or online. There are lots of people who will try to convince you that this is a bad approach – that you should focus on what candidates have accomplished, that you’ll miss lots of talented people, etc. – but while the problem of false negatives is real, it’s also a lot less expensive than false positives.

Anyway, watching someone code will tell you things you just can’t know from receiving a code sample, or seeing the results of a coding challenge done in private. Does the candidate write code fluently, or hesitate over every keyword? Do they think in words or phrases? Once they’ve chosen an approach, do they stick with it even after they’ve clearly realized it was a mistake, or do they have the mental flexibility to change course midstream? Every programmer has a mental model of how code actually works under the hood – how accurate, and complete, is a candidate’s model? Watching them write code in real time can reveal a lot about their internal process, as they go down paths and backtrack, make mistakes, catch bugs on their own (or not), cover (or miss) base cases, etc. Likewise, the choices a candidate makes can reveal preferences and potential holes in the mental model.

The Problem

Consider the following sample interview question:

Implement a linked list class that stores integers in sorted order. There are two requirements:

• When a new linked list object is initially instantiated, it should be empty
• There should be a method to insert an integer into the list at the appropriate location
  

This isn’t a difficult question, and that’s the point – the perfect interview question should be easy for a good candidate, impossible for a bad one. Even FizzBuzz will weed out a large percentage of candidates, and this is a little less insulting. (N.B. this is not my actual interview question)

One straightforward implementation would be the following (in Java, for no better reason than that it’s simple):

public class MyLinkedList {
    public final static class Node {
        private int value;
        private Node next;
        public Node(int v) {value = v;}
    }

    private Node head;

    public void insert(int value) {
        // base case: empty list, or first node
        if (head == null || value < head.value) {
            Node new_head = new Node(value);
            new_head.next = head;
            head = new_head;
            return;
        }
        Node n = head;
        while (n.next != null && n.next.value < value) {
            n = n.next;
        }
        Node tmp = new Node(value);
        tmp.next = n.next;
        n.next = tmp;
    }
}

(Note that Java automatically does the equivalent of a calloc() and sets all fields to zero/null when instantiating a new object – hence, there’s no need to have the default constructor for MyLinkedList)

This is a pretty straightforward implementation – first take care of a couple of base cases, then iterate through the list. A good candidate should be able to bang out something roughly along these lines in a couple of minutes.

There are many ways to skin this cat, however. One common way that people implement this is as follows:

public class MyLinkedList {
    int value;
    MyLinkedList next;
    boolean isEmpty;
    public MyLinkedList() {
        isEmpty = true;
    }
    public MyLinkedList(int v) {
        value = v;
        isEmpty = false;
    }
    ...
}

On the one hand, this is simpler – there’s no inner class, and you can specify an “empty” list by having a head node with isEmpty set to true. However, what if the problem changes to require appending to the end of the list? What if you want to store more meta-data for the list as a whole? Though a candidate can solve the problem with this solution, it’s a warning sign that they might have issues with object oriented programming techniques.

Here’s another common approach:

public class MyLinkedList {
    Integer value;
    MyLinkedList next;
    public MyLinkedList() {
        // value == null
    }
    public MyLinkedList(int v) {
        value = v;
    }
    ...
}

This has the same problem as the previous version, with the added issue that it unnecessarily allocates memory on the heap (i.e. by using an Integer object instead of an int). This doesn’t matter so much for small data sets, but it can easily become a problem in large-scale applications. Though some candidates understand that they’re doing something inefficient, a candidate with a deep understanding of memory management should have a natural distaste for the unnecessary allocation of memory. This approach is popular among programmers with experience in loosely-typed languages.

Some candidates more comfortable in functional languages prefer a recursive approach for the insert method:

    public void insert(int value) {
        // base case: empty list, or first node
        if (head == null || value < head.value) {
            Node new_head = new Node(value);
            new_head.next = head;
            head = new_head;
            return;
        }
        insert_helper(head,value);
    }

    private static void insert_helper(Node n, int value)
    {
        if (n.next == null || value <= n.next.value) {
            Node tmp = new Node(value);
            tmp.next = n.next;
            n.next = tmp;
        } else {
            insert_helper(n.next,value);
        }
    }
}

When asked, they may mention that it’s tail recursive and should be optimized out by the compiler. But this isn’t necessarily the case (in Java, for instance), and a candidate with more experience should understand why it’s unnecessary (and undesirable) to use recursion when there’s no need to maintain prior locations on the stack.

All in all, the above solutions have the advantage of working, and though they may provide additional information about a candidate, they aren’t disqualifying coding choices in and of themselves. Obviously, you should expect more optimal code from senior candidates, but even so, it’s important to remember that the interview is a stressful environment, and even top candidates can get flustered. Asking the candidate to recode something in a way they’re clearly trying to avoid is frequently quite telling (“OK, great! Now, can you do this with/without using recursion?”).

Next up: common coding errors that indicate deep flaws in the mental model.