Interview by under-constrained programming

David over on Exold mocks stupid interview questions that ask some basic programming problem (in that case about file copying). As his mockery shows us, these simple sounding questions have a huge amount of baggage in terms of unstated assumptions¹ [1As Jeff Atwood points out, the best answer is probably why would any competent programmer ever write a file copy routine?].

In the comments on Reddit was this code fragment for an alternative interview question, the classic reverse a string problem:

std::string& reverseString( std::string &str ) {
    int strLen = str.length();for ( int i = 0; i < strLen / 2; ++i ) {
        std::swap( str[ i ], str[ strLen - i - 1 ] );
    }
    return str;
}

The fact that the person did it from scratch and straight off the top of their head is an amazing feat (and for sure one that I couldn't replicate). The issue is though that the problem domain is under-constrained. We don't actually know enough to write the code yet! It's one of those things that just looks so blindingly obvious that we forget to ask the right question: what format is the string in?

If the question sounds daft—you're thinking that it's just a string—then I guess you're supposing that it's an ASCII string. Now take a moment to think about what happens when you run this on a UTF-8 sequence. The same problem is going to manifest itself for any multibyte encoding. And if you're using something really complex like Shift_JIS then you're really in a lot of trouble.

Now, let's look for more complexity: what happens if the text happens to be in a language which uses a complex script like Thai? I'm not even sure that the reverse operation is possible for a Thai word. Even if the script is in TIS-620² [2The TIS-620 standard is written in Thai and the official web page fails to specify its character encoding. There is some information on Wikipedia though.] (which at least guarantees that each char is an individual glyph) you'll probably end up with something that can't be displayed due to the very complex rendering rules the writing system has.

Of course reversing a string is actually a fairly odd thing to do in a bit of software. We may want to render something backwards (mirrored), but that's just drawing along an inverted axis isn't it? So, let's put this problem aside as too complex and look at something easy.

An easier problem

How about we just go for something really simple like counting how many characters there are in a string? We can even use some library code to do this for us. std::strlen() would seem to be our friend here, but what encoding is it assuming? Of course it isn't assuming anything and merely returns the number of bytes long the string is (less one of course as it doesn't count the final zero). Is this the length? There's a raft of other library functions that answer the same question in all sorts of different ways.

It doesn't get any better if we decide to make use of wchar_t and start to use std::wstring. For most platforms where wchar_t is 16 bits and strings are in Unicode we still need to know which Unicode version (assuming of course it's in Unicode at all) so that we can work out how to deal with it (are the characters constrained to 16 bits as they are in Unicode 2 or can we get surrogate pairs because it's Unicode 4?).

A quick look at std::basic_string<> shows us that we're likely to have a real hoot using that part of the standard library as the accessors are all based around wchar_t. Use these on Windows™ and you have to be responsible for all of the Unicode decoding yourself. Not a fun task—especially as conformance is going to be so hard to validate. The higher Unicode planes are pretty rare and your software will probably work fine for most users most of the time. When it breaks though you're sure to be introducing all sorts of interesting behavior that'll be of interest to system crackers.

More reasonable questions

Ole Eichhorn over at Critical Section has a different take on the sorts of questions to ask³ [3I don't mean to pick on Ole. I think he says a lot of very interesting and useful things. I just don't happen to like his interview questions. Maybe he's changed his technique since he wrote the review of Moving Mount Fuji]. On the face of it the sorts of logic problems he uses are better, but again, there are problems with them. Let's look at a couple.

You have five jars of pills and one scale. All the pills in one jar only are “contaminated”, they weigh 9 grams instead of 10. How do you tell which jar is contaminated with just one weighing?

On first reading this I wondered what one weighing actually meant in practice, but putting that aside the solution is very clever. Given some time to think about it I'm fairly sure that I'd come up with it, but I'd have one big problem: it involves taking the pills out of the jars. My thought process would tell me that this is a very bad idea. The answer I'd have to give is:

It's impossible to do without contaminating all of the jars.

If I was posing the question I'd be impressed that a candidate could handle the logic, but they'd have to show a deeper understanding of the context of the problem for me to be really interested in hiring them:

I can't do it without contaminating all of the jars. We really need to be looking at why the process only allows one weighing and then how the contamination occurred.

A candidate looking at the problem domain in this way is much more valuable⁴ [4As an aside the order of the two checks is also telling me something important. You correct the conformance checking, i.e. the error handling, before you debug the process.].

Going back to Ole's list, his favourite question is:

Consider a pool table with the balls setup for a break. You must write a program which models the table, so you can predict where all the balls will end up. How do you approach this?

His answer though misses the biggest gotcha in the problem. First though some other ideas…

I'm not 100% convinced that an object-oriented solution for storing the state is most appropriate. His solution goes on to describe a procedural loop and I think that structured data types may do us just as well in this context. More interestingly he then says:

Ideally they'll come up with some sort of discrete time simulation, where they have an outer loop that cycles through units of time, and computes the new position of each object.

Again, hmmm… What about storing the balls in an ordered list keyed on the time to the next collision? It makes the collision determination a bit harder (and now we'd almost certainly want to delegate that to ball objects) but you can get rid of the clock. Which is better? That depends on what you want the simulation for which is not part of the problem domain as stated ⁵ [5The question of what software is for rather than what it is expected to do is the most valuable question you can get answered when building any bit of software.].

And what is the gotcha? It has to do with the physics of the system. Newtonian mechanics has no solution for three (or more) balls hitting each other at the same time. What does this mean? It means that the problem which at first glance looks like a load of simple mechanical physics calculations isn't even deterministic and even worse it turns out to be non-computable! Any time you have a triple (or more balls) collision you have a real problem to solve (and it'll be the answer to how to deal with this question that would probably be most illuminating about the candidate)⁶ [6This nondeterminancy and non-computability makes the break awkward at best as the “obvious” thing to do is to place the balls perfectly laid out and touching, an idealisation of what happens on a real pool table (it is a computer simulation after all).One solution to this is to “salt” their starting positions so that the likelihood of three or more touching at the same time is greatly reduced. Another solution might be to work out the alternatives based on calculating two-way collisions in every possible order and then either taking the mean resultant vectors or randomising within this range (if you can even work out what range means here).It is of course this property that makes the break so different from game to game and so interesting.]⁷ [7This is a surprisingly contentious stance (from private emails). It clearly warrants a much deeper discussion which this article isn't the place to go in to. At the moment it isn't clear to me where the difference of opinion comes from and I haven't found any proper proofs to back up either stance. It may well be that different ways of modelling the problem will lead to different answers, but I'm not sure.].

Interviewing

When you're interviewing you want a candidate that is going to think about the business context of the system and the utility that the software users are going to require—this is what makes David's answers to the copy file problem so good.

Programmers do spend some of their time putting together complex algorithms, but for most of us, most of the time, we're looking at building systems that deal with the much more general and far more woolly problems that involve people.

• What does the user want to achieve?
• How are they likely to go about it?
• Where are holes in the process?
• What are the exploits?
• Where is the return on investment going to come from?

These are harder to frame in an interview, but much more valuable to hear the answers to. And what do we do when we need a complex algorithm? We look it up, because I can guarantee that better answers are easily available on the Internet than anything any of us can think up in even a two hour interview.

And just as a postscript, what about the moving mount Fuji problem?

It's a volcano: anybody trying to move it is up against what's going to be a losing fight with the planet. The mountain has a proper “self-correcting” error handling procedure for use against anybody who tries it.

There's been a discussion going on over at Reddit that you may also find interesting (if you haven't already seen it).