I attended a Google interview workshop. They told us to communicate, ask questions, write sensible code, test it. In other words, I wasted one hour of my life.

However, they had an example of the kind of programming problem they would ask people to solve. The problem itself is not that interesting, nor was their fake walk-through, but I really liked their final solution. Since I’m procrastinating real work again and need to learn OCaml anyways, I implemented it. Let’s start at the beginning:

Given a list of numbers, produce a list of numbers where every element is the product of all the elements in the input list excluding the element at the current index.

That’s not the exact wording, but close enough.

A naive, nested loops implementation is left as an exercise to the reader. It seemed to me like half the audience would have struggled with that already. Insert some lame comment about the state of the software industry here. My idea was to go through the list once and calculate the product of all the numbers. Then map across the input list, dividing the product of all the input elements by one input element at a time to produce the output list. There are some problems with that, but first a couple of examples to clarify, including my interpretation of boundary conditions.

foo [] = []

foo [42] = [1] (* The fake interviewee used 0 for the empty product.
                  I wouldn't have hired him... ;-) *)

foo [1; 2; 3; 4] = [24; 12; 8; 6]

foo [3; 0; 2] = [0; 6; 0] (* If there is exactly one zero at position p
                             in the input, every element in the output
                             is zero, except the one at position p. *)

foo [3; 4; 0; 1; 2] = [0; 0; 24; 0; 0]

foo [3; 4; 0; 0; 2] = [0; 0; 0; 0; 0] (* Two or more zeroes in the input
                                         => output is all zeroes. *)

So, my idea of doing it in linear time was calculate the product, then divide it by each element to produce the output. Sounds easy enough. I actually thought about being careful to not divide by zero, but actually writing it up turned out to be trickier than expected. This is my working version, after more iterations than I care to admit.

let foo l =
  let p = ref 1 in
  let z = ref 0 in
  List.iter (fun x -> if x = 0 then z := !z+1 else p := !p*x) l;
  List.map  (fun x -> if x = 0 then (if !z >= 2 then 0 else !p)
                      else (if !z >= 1 then 0 else !p/x)) l;;

We iterate through the input once to calculate the product p (excluding zeroes) and counting zeroes. We then map over the input, to divide the product by each element. This requires some care. If the input at the current position is zero, we either return the product p, in case there is only one zero, or 0 in case there are were more than two zeroes in the input. If the input is not zero we can safely divide by it, but if there is at least one zero in the input, we need to return p. Remember calculated the product of all the nonzero inputs.

It works, but I’m unhappy with it. The nested conditionals are unwieldy. Calculating the product without zeroes is needed for the case where there’s only one zero, but for the case with more than one zero, it would be better to have included zeroes. It’s just not nice. That’s why I like their solution so much, because it is uniform. Here’s the idea: map over the input twice. The first time, go from the left and produce an output list that has the partial product of all the input elements to the left. The second time, go from the right and produce an output list that has the partial product of all the input elements to the right. Zip together the lists with ( * ).

let foo2 l =
  let makeMult = fun () -> let p = ref 1 in
                           let f = fun x -> let r = !p
                                            in p := r*x; r in
                           f in
  let fromLeft =  List.map     (makeMult ())           l  in
  let fromRight = List.rev_map (makeMult ()) (List.rev l) in
  List.map2 ( * ) fromLeft fromRight;;

The makeMult business is a bit ugly. However, OCaml does not seem to provide reductions (from Clojure) or scanl/scanr (from Haskell). Anyways, for the input [3; 4; 0; 1; 2] we produce [1; 3; 12; 0; 0] and [0; 0; 2; 2; 1] and then multiply these two together (element-wise) to produce [0; 0; 24; 0; 0]. No conditionals! In the workshop, the fake-interview was done in Java, and the interviewee switched to arrays for the final solution. It clouds the intent a bit, going through an array from the end is probably faster than reversing a list. There are arrays in OCaml, so without further ado, here’s my implementation.

let foo3 a =
  let r = Array.make (Array.length a) 0 in
  let rec loopFromLeft i p =
    if i = Array.length a then ()
    else (r.(i) <- p;
          loopFromLeft (i+1) (p * a.(i))) in
  let rec loopFromRight i p =
    if i < 0 then r
    else (r.(i) <- r.(i) * p;
          loopFromRight (i-1) (p*a.(i))) in
  loopFromLeft 0 1;
  loopFromRight ((Array.length a)-1) 1;;

Note that we only allocate one array for the output, no additional intermediary arrays to store the from left and from right results. It just goes into the output array directly. I really like the algorithm, but OCaml makes it a bit noisy to implement, by not having for loops. It is actually prettier in Java.

This can not stand. So here’s a Common Lisp version with heavy use of loop.

(defun foo (a)
  (let ((r (make-array (length a))))
    (loop for p = 1 then (* p (aref a i))
          for i from 0 below (length a)
          do (setf (aref r i) p))
    (loop for p = 1 then (* p (aref a i))
          for i from (1- (length a)) downto 0
          do (setf (aref r i) (* p (aref r i))))
    r))

I dislike the below vs. downto thing and the (1- (length a)). If we have different loop clauses for incluse and exclusive end, why not for inclusive and exclusive start? I also dislike the duplication of the location in the last setf. Clojure has these functions that update an atom. They take the atom and a function and replace the value of the atom with the function applied to the value that was in the atom. Why can’t we write something like this instead of the last setf: (updatef (aref r i) (lambda (v) (* p v))). It’s not shorter, but prettier. Note sure it’s as pretty as Java. On the other hand, multiplying values quickly overflows 32 bit ints and I certainly prefer the Common Lisp version to a bignum version in Java.

The code is on github.