Monday, December 7, 2015

That Time I Didn't Get the Job

Here's a story that I occasionally share with my students. Back around 2001, I had left my second computer gaming job in Boston, and was still interviewing for other jobs in the industry. I had an interview at a company based in Andover, and it was mostly an hour or two in a conference room with one other staff member. I have no recollection who it was now, or if they were in engineering or production. At any rate, part of it was some standard (at the time) "code this simple thing on the whiteboard" tests of basic programming ability.

One of the questions he gave me was "write a function that takes a numeric string and converts it to the equivalent positive integer". Well, it doesn't get much more straightforward than that. I didn't really even think about it, just immediately jotted down something like the following (my C's a bit rusty now, but it was what we were working in at the time; assumes a null-terminated C string):

    int parseNumber (char *s) {
        int digit, sum = 0;
        while (*s) {
            digit = *s - '0';
            sum = sum * 10 + digit;
            s++;
        }
        return sum;
    }


Well, the interviewer jumped on me, saying that's obviously wrong, because it's parsing the digits from left-to-right, whereas place values increase from right-to-left, and therefore the string must be parsed in reverse order. But that's not a problem, as I explained to him, with the way the multiples of 10 are being applied.

I stepped him through an example on the side: say the string is "1234". On the first pass, sum = 0*10+1 = 1; on the second pass, sum = 1*10+2 = 12; on the third pass, sum = 12*10+3 = 123; on the fourth pass, sum = 123*10 + 4 = 1234. Moreover, this is more efficient than the grade-school definition; in this example I've used only 4 multiplications; whereas the elementary expression of 1*10^3 + 2*10^2 + 3*10 + 4 would be using 8 multiplications (and increasingly more multiplications for larger place values; to say nothing of the expense in C of finding the back end of the string first, before knowing which place values are which).

But it was to no avail. No matter how I explained it or stepped through it, my interviewer seemed irreparably skeptical. I left and got no job offer after the fact. The thing is, part of the reason I was so confident and took zero time to think about it is because it's literally a textbook example that was given in my assembly language class in college. From George Markowsky, Real and Imaginary Machines: An Introduction to Assembly Language Programming (p. 105-106):


Postscript: Elsewhere, this can be looked at as an application of Horner's Method for evaluating polynomials, which is provably optimal in terms of minimal operations used (e.g.: see Rosen, Discrete Mathematics, 7th Edition, Sec. 3.3, Exercise 14).

However, that wasn't the only time I got static for using this textbook algorithm. As of 2019 I've shared this anecdote online at least a handful of times, and every single time, inevitably, someone argues that they wouldn't allow this solution in their codebase because it's too opaque for normal programmers to understand and maintain. (Ironically, I'm writing this postscript on the 200th anniversary of Horner's paper being presented to the Royal Society of London.)

As it turned out, I never worked in computer games or any kind of software engineering again.

No comments:

Post a Comment