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;
        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 saying 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: That wasn't even the only time I got static for using this textbook algorithm. At some point I shared it in an online forum in response to a question -- and then I had someone claiming they were a producer who wouldn't permit it in the code base, because it was too opaque for normal programmers to understand and maintain.

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


  1. Just came across an old paper that leads me to believe the interviewer was a certain producer at that company.

  2. Note that the algorithm here is an application of Horner's Method for polynomials.

    1. That being provably optimal in terms of minimal operations used. Also seen in: Rosen, Discrete Mathematics, 7th Edition, Sec. 3.3, Exercise 14.