A weblog by Will Fitzgerald

Monthly Archives: August 2011

On “Retiring a Great Interview Problem”

Daniel Tunkaleng wrote an interesting blog post, “Retiring a Great Interview Problem” on an interview problem that he has, in the past, posed to interviewees, but which he has now retired, because someone posted the problem, and a solution, to an interview problem website. The problem is the segmentation problem (which he calls the word-break problem): given a string, segment it into reasonable words, if possible (for example, breaking “applepie” into “apple pie”). He describes the various gradations of good answers to this problem, and I guess I would say that his reasoning is sound: candidates who give a better answer than a worse answer would probably make better programmers.

However, if I were asked this question in an interview, I am fairly confident that I would freeze up and not give a good answer. Partially, this is because of the stupidly artificial conversational model that occurs when one is participating in a white-board exercise–what, program without the resources of the internet, while someone watches me, and makes me elucidate my mental states? But the other reason I’d have a problem is that I would recognize this problem as one I have already coded and place on Github (https://github.com/willf/microsoft_ngram) which is in turn based on Peter Norvig’s section on segmentation in the book Beautiful Data (for which he posted Python code). This code does segmentation even better than the Tunkaleng’s formulation of the problem, in that it provides the most probable segmentation (Tunkaleng’s formulation asked for any reasonable segmentation). I also know (or at least believe) that Norvig’s code is based on similar code he wrote for his Artificial Intelligence textbook (here’s the code) and that using memoization as a lazy person’s method of doing dynamic programming is an old and efficient trick of Norvig’s. This knowledge would basically drain me of any interest in reinventing this particular wheel.

In other words, I would fail this interview, although I have publicly demonstrated my ability to implement a more generally useful version. Despite Tunkaleng being a vastly better programmer, he got it wrong on the first try (he had an “off-by-one” error, which he later corrected). Granted, interviewers (or interviewers in the Google style) are generally more concerned about precision (avoiding hiring bad programmers) than recall (avoiding missing out on good programmers). But I continue to think that the whiteboard method systematically discriminates against certain classes of programmers. I suspect, in particular, it discriminates against older candidates, which, prima facie would be illegal under US law.

[Update, added later the same day]. Take the “I suspect” literally in the last paragraph. I’m still trying to articulate what I think about interviewing techniques of this type and discrimination, particularly age discrimination (the only kind I’m potentially subject to). And take prima facie literally, too–I doubt that, in a court of law, age discrimination could be proved based solely on these interviews.