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. I was reading such a thread back around the time when FizzBuzz was all the rage.

One gentleman 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 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 programming C.

I got to wondering how hard this could be, and decided to give it a shot 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 sent that to the gentleman who had proposed the problem. In my head I was lightly yanking his chain by sending him short clear (imo) python code rather than 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 explicitly been part of the problem, but post hoc spec changes are par for the course. I was in geek mode and consequenty took the bait. I modified the code to use generators instead of lists. I sent the revised version 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 was a surprise, I had not realized we were playing that particular game. I was flattered, but I was happy with my job and did not want to relocate.

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 person who proposed the problem. But I think might have liked working with him.