A Google Interview Question

When I was working at Google I had to interview a lot of candidates. Most often the interview was general in nature. I wasn't evaluating a candidate for a particular position, I was determining whether a candidate was all around "Google material".

Although Google is known for its challenging interview questions, I found the simple questions gave me the most information about a candidate. One of my favorite interview questions was this: “Given the state of a tic-tac-toe game (naughts and crosses), determine if someone has won the game. Code this up however you'd like.”

This isn't a very hard problem. (Pause a moment and think how you'd do it, or even take a moment to write it up.) The straightforward solution is to check the rows, the columns, and the two diagonals. I was less interested in whether the candidate would come up with this solution or something more clever than I was in seeing exactly how the candidate worked his way from an informal word problem towards a formal solution in code. I wanted to see how the candidate organized his thoughts. I wanted to see how proficient the candidate was in programming when he was allowed to use the language he was most comfortable with.

I expected most candidates to whip off a solution in a few minutes and then we'd move on to the next interview question. To my surprise, fully half the candidates were unable to finish this simple task. A couple seemed unable to use a whiteboard to sketch out a solution. A large number dove right in and started coding up the obvious nested loop only to get confused at handling the flow control. (There is a hidden trap in this problem: if you choose the nested loop solution, you want to abort the inner loop early when you determine a solution is not possible on the current row or column you are checking, but you want to abort the outer loop early when you determine a solution is possible.) It was often that a candidate did not at first realize that a cell in the tic-tac-toe board has three possible states, not two. One candidate used 4x4 arrays to represent the board so he could use 1-based indexing. Not a single candidate tried to abstract over the low-level array manipulation.

Interviews are highly stressful for candidates, so I didn't judge them too harshly. If it looked like they were on the right track and they successfully noticed and repaired a bug or two in their solution I'd call it a win. If they got hopelessly lost, I'm afraid I couldn't recommend them. It was sad because many seemed very nice people and they were trying their best. Either they weren't cut out to be programmers or their education was not serving them well at all.

I do have to mention one candidate who knocked this question out of the park. He observed that there really aren't that many tic-tac-toe game positions, so you can just hash the game position and look up the winner in a table. I didn't even ask him to code this up.

Roll your own conditional

Sometimes you'd like to write your own conditionals. Perhaps you'd like to wrap something around one or both arms of the branch. Perhaps the predicate is tristate and you need three branches. Perhaps the predicate wants to share information with one or both arms. You want to abstract away how the predicate makes it decision from how the caller wants to handle the possible outcomes. The trick is to use continuation passing style:

sign = lambda n, if_positive, if_zero, if_negative: \
           if_positive() if n > 0 else \
           if_negative() if n < 0 else \
           if_zero()

# use it like this:
for i in range (-1, 1):
    print (i)
    print (sign (i,
            lambda: \
              "positive",
            lambda: (lambda first, second: second)(
              print ("Hooray!"),
              "zero"),
            lambda: \
              "negative"))

By making the branches be thunks, we delay evaluation. Once the conditional decides which branch to take, it forces the thunk and returns its value.

Some of Python's language constructs, like variable binding, exception handling, sequencing, and iteration, are provided only through language statements. You cannot use statements in an expression context, so it would seem we are up against a limitation. But Python has lambda expressions. Lambda expressions and function calls are all you need to implement variable binding, sequencing and recursion as ordinary Python expressions.

For example, suppose you wish to have a 'let' expression where you bind helper variables 'a' and 'b' to subexpressions. Simply use lambda and immediately call it:

    return (lambda a, b: h(a, b))(f(x), g(y))

Not pretty, but it gets the job done.

If you want to sequence two expressions, write them like this:

    return (lambda ignore: x + 7)(print (x))

The print expression runs first, its result is ignored and then x is added to 7 and returned. Again, this could use a lot of syntactic sugar, but it gets the job done. Alternatively, we could use left to right evaluation of arguments to do our sequencing:

    return (lambda first, second: second)(print(x), x + 7)

In order to implement iteration, we need to bind a name recursively. We'll use the Y operator.

Y = lambda f: (lambda d: d(d)) (lambda x: f (lambda: x (x)))

print (Y (lambda loop:  \
              lambda x: \
                  None if x == 0 else (lambda first, second: second)(
                                           print (x),
                                           loop()(x - 1)))
       (5))

5
4
3
2
1
0
None

Handling exceptions is easy if you use a helper function and some thunks:

def on_error (compute_value, handle_error):
    try:
        return compute_value()
    except:
        return handle_error()


def safe_divide (dividend, divisor):
    return on_error (
           lambda: dividend / divisor,
           lambda: (lambda first, second: second)(
                       print ('divide by zero, answer 1'),
                       1))

print (safe_divide (12, 3))
4
print (safe_divide (12, 0))
divide by zero, answer 1
1