drcabana.org
Computational divertissements


The case of the unexpected job interview

Posted on

I like to check out the news and gossip on lobste.rs and ycombinator. One recurring theme is the sad state of practices around the interview and hiring of programmers. Some years ago I was reading such a thread, it was back around the time when FizzBuzz was all the rage.

One person mentioned that he liked to ask candidates to implement long addition. No tricks mind you, it was not about parsing dubious strings into integers and handling the error cases. Just take valid-by-assumption string representations of two integers and add them. He talked a bit about the sort of errors candidates would make, and some of the hints he would offer. His code examples were in C. The code seemed more complex than I would have expected, but I'm the sort who takes every opportunity to avoid C.

I got to wondering how hard this could be. I decided to give it a shot, but in python. I'm going from memory, but below is pretty much what I came up with. The way long addition works has a more or less natural representation.

"Long addition of non-negative base 10 ints represented by strings of digits."
from random import randint

def left_pad(string, required_len):
    "Pad on the left with 0 to meet required length."
    padding_len = required_len - len(string)
    if padding_len > 0:
        return "0" * padding_len + string
    return string

def columns(a, b):
    """
    Set up numeric strings a and b for addition by left padding the
    shorter with zeros to match length of longer. Return list of
    columns, ie list of pairs of corresponding digits.
    """
    maxlen = max(len(a), len(b))
    digits_a = [int(d) for d in left_pad(a, maxlen)]
    digits_b = [int(d) for d in left_pad(b, maxlen)]
    return list(zip(digits_a, digits_b))

def add(a, b):
    """
    Add two numeric strings via standard base 10 long addition,
    return the sum as a string.
    """
    carry = 0
    digits = []
    for x, y in reversed(columns(a, b)):
        carry, digit = divmod(x + y + carry, 10)
        digits.append(str(digit))
    if carry > 0:
        digits.append(str(carry))
    return "".join(reversed(digits))

def test():
    "Returns True when all randomized tests pass."
    result = True
    for _ in range(100000):
        a = randint(1, 999999999)
        b = randint(1, 999999999)
        result = result and str(a + b) == add(str(a), str(b))
    return result

print(test())

For grins I fired that over to the gentleman who had proposed the problem. I even made sure to throw in a test and comments. In my head I was lightly yanking his chain by sending him short clear (imo) python code instead of long obscure (imo) C. To my surprise he replied. He was vaguely complimentary, and mentioned that he had not known about the divmod function. He went on to say that while my approach did indeed implement long addition, I was creating lists willy-nilly, and so burning through memory.

Space efficiency had not been part of the spec, but post hoc criticism is par for the course. I was still in geek mode, so I took the bait. I modified the code to use generators instead of lists. I sent it on over, feeling pretty pleased with myself. I was enjoying the game.

def right_pad(numeric_string):
    """Pad digits on the right with 0, forever!"""
    for digit in numeric_string:
        yield int(digit)
    while True:
        yield 0

def columns(a, b):
    """
    Set up numeric strings a and b for addition by padding the
    shorter with zeros to match length of longer. Return generator
    of columns (corresponding digit pairs) in reverse order.
    """
    digits_a = right_pad(reversed(a))
    digits_b = right_pad(reversed(b))
    while True:
        yield next(digits_a), next(digits_b)

def add(a, b):
    """
    Add two numeric strings via standard base 10 long addition,
    return the sum as a string.
    """
    carry = 0
    digits = []
    cols = columns(a, b)
    for _ in range(max(len(a), len(b))):
        x, y = next(cols)
        carry, digit = divmod(x + y + carry, 10)
        digits.append(str(digit))
    if carry > 0:
        digits.append(str(carry))
    return "".join(reversed(digits))

Later that afternoon I got a reply asking whether I would be interested in a job. That came as a complete surprise, it had not occurred to me that we were playing that particular game. I was flattered, but I was happy with my job and did not want to relocate. I politely declined.

Years later I look back and think that was the best job interview I ever took part in, on either side, for various reasons.

I no longer recall anything about the job in question, and I lost touch with the gentleman who proposed the problem. But I think might have liked working with him.