Articles, Weblog postings, and forum discussions about hiring practices and interview techniques tend to draw a lot of attention and spawn lengthy, passionate debates. This is especially true of references to interview questions that people think should be asked in programmer interviews. As pointed out in How do you interview security experts?, though, I believe the sort of questions that should be asked are those for which there may be many “correct” answers, but the way an applicant answers them is the really important factor:

You need questions that invite explanations, not just simple answers. It’s harder to explain why an answer is right than to just give that right answer itself. If your candidate gives a “right answer”, your question should be phrased so that it requires more than just a few words to satisfy the answer. If the candidate gives a “wrong answer”, tell him or her what answer you were expecting and ask why the answer you got was different. Have a conversation about the difference between the given answer and the expected answer, and make your decision based on the quality of the explanation and the thought process behind it, rather than whether the answer was what you expected.

Coding challenges, where you ask a programmer applicant to whip up some quick code on the spot to demonstrate a minimal grasp of software development (and perhaps of the specific language(s) for which you’re hiring), may seem to require more objectively answerable questions. A popular subject of debate on the Internet a couple years ago was the FizzBuzz challenge, used to weed out the absolute worst coders applying for a job. Reginald Braithwaite (Internet-famous programmer) made the incredible claim that 199 out of 200 applicants for a programming job can’t write code worth a damn, and will probably never be competent programmers.

I agree with Mr. Braithwaite’s assessment of the FizzBuzz problem — that it (or an equivalent programming problem, preferably one that hasn’t been solved 600 different ways on the Internet) is useful to help weed out the 199 out of 200 applicants who aren’t really programmers, no matter what their resumes say. I agree that, sometimes, such a very basic approach to assessing the most minimal level of competency is necessary before you can move on to more challenging problems. I just think it is a crying shame that the scope of the way this question is asked is so limited.

Let us consider another FizzBuzz level problem that is often used to test minimal programming skill: Fibonacci numbers. The idea is that you write something like this on the whiteboard in the room where you are conducting your interview:

  F(n) = F(n-1) + F(n-2), where F(0) = 0 and F(1) = 1

(The following examples will use Scheme. If you want to follow along on your own computer, running each example and experimenting with it, Ypsilon is an excellent cross-platform compatible implementation of R6RS, the most current iteration of the Scheme standard.)

Then, you say something like “Write a function that solves this problem.” Let’s assume for argument’s sake that you let the applicant choose the implementation language, and he goes with Scheme (Justin James points out that this may be a good sign, in Write a resume that will land you a programming job). If the applicant has encountered this in college at all, he can probably dredge this from memory, as the “naive recursive implementation”:

  (define (fib n)

(cond ((= n 0) 0)


((= n 1) 1)


(else (+ (fib (- n 1)) (fib (- n 2))))))

This should get your candidate past the FizzBuzz gate, proving he knows how to implement a clearly specified requirement in code. This question could be so much more, though, with so little effort — and without eliminating its usefulness for weeding out the most worthless candidates. For instance, you could ask the applicant to write an implementation that is suitable for “real-world use”.

This is where the naiveté of that algorithm rears its ugly head, and where most people with any real-world experience would start thinking about efficiency and give you an implementation that doesn’t explode in your face when you start trying to calculate large Fibonacci numbers. For example, it calculates the Fibonacci number for an input of 20 pretty much instantaneously, but it hangs for a while for an input of 50, because that’s a tree-recursive algorithm that isn’t tail-call optimizable. In English, this algorithm increases the number of operations that must be performed at an exponential rate, which also tends to increase the time it takes to calculate an answer at an exponential rate.

If the applicant is asked to produce an algorithm that is suitable for “real world” use, there are a number of ways to improve the efficiency of the algorithm, including memoization, strictly iterative operation, or reordering the thing to take advantage of Scheme’s tail-call optimization. A tail-recursive version, with an essentially iterative form, might look like this:

  (define (fib a b count)

(if (= count 0)


b


(fib (+ a b) a (- count 1))))


(define (fibonacci n)


(fib 1 0 n))

Now you’re getting somewhere — right? This is about as far as most developers, and thus most technical interviewers, are likely to get. There’s another concern that is just as important, however; security. If you are a programmer, you might notice a potential for impressive failures in practical use of this code. The problem is that calculating Fibonacci numbers assumes you’re using positive integer values as inputs, and this code assumes it will only receive positive integer values as inputs too. If you receive input that looks like any of the following, your program is going to blow up in your face, if the above code is all there is for dealing with arbitrary inputs:

  • -3
  • 2.7
  • 10/9

Let us imagine that your applicant, upon hearing you say that this code might need to serve a real-world purpose, decides to implement input validation:

  (define (fib a b count)

(if (= count 0)


b


(fib (+ a b) a (- count 1)))))


(define (fibonacci n)


(fib 1 0 n))


(define (fib-validate n)


(if (and (integer? n) (>= n 0))


(fibonacci n)


#f))

All else being equal, this is the candidate for the job you want to hire. He not only thought about efficiency, but also about security. In fact, in many cases, I would be inclined to select a candidate whose code for “real world” use employed input validation but did not improve the efficiency of the core implementation over an applicant who improved efficiency but did not employ any input validation, like so:

  (define (fib n)

(cond ((= n 0) 0)


((= n 1) 1)


(else (+ (fib (- n 1)) (fib (- n 2))))))


(define (fib-validate n)


(if (and (integer? n) (>= n 0))


(fib n)


#f))

Any reasonably experienced programmer on your team should be able to recognize efficiency issues, and fix them, if needed. Considering how rare it is for coders today to think of security issues first, however, the candidate whose initial instinct is to validate input when you start talking about deploying code in the real world is worth his weight in gold.

(I owe thanks to Sterling Camden, TechRepublic’s own IT Consulting guru, for his input while I worked on the basis for this article.)