A Question from Google Interview
Today I came across the following challenge supposedly offered during a Google technical interview:
There is an array INPUT[N] of N integers. You have to compose an array Output[N] such that Output[i] will be equal to the product of all the elements of INPUT[] except INPUT[i]. Example: INPUT:[4, 3, 2, 1, 2] OUTPUT:[12, 16, 24, 48, 24] Solve it without division operator and in O(n).
Seems a good stuff to sharpen knowledge of F# core collection libraries, so I got hooked.
My first solution was:
// naive brute force functional solution in O(n*n) let googleProdv1 a = let idxA = [|0 .. Array.length a - 1|] let prodSkippingSelf i = Array.fold2 (fun acc x idxX -> if idxX <> i then acc * x else acc) 1 a idxA Array.mapi (fun i x -> prodSkippingSelf i) a googleProdv1 [|4;3;2;1;2|] |> printfn "%A"
It has a neat trick of mixing indexes with array elements in order to perform exclusion with the help of Array.fold2. However, the essential problem with this solution is that it has O(n**2) complexity instead of required O(n). I got back to the drawing board and began playing with a small data sample looking for clues:
N0 | N1 | N2 | |
Prefix product | 1 | N0 | N0*N1 |
Suffix product | N1*N2 | N2 | 1 |
From examining an array of 3 elements it gets apparent that the sought product is a product of corresponding elements of the following two arrays: prefix product array of partial products of 0 elements that is equal to 1, first element, first element and second element, and suffix product reversed array of similar partial sums of reversed original array:
for N0 it is 1*N1*N2, for N1 it is N0*N2, and for N2 it is N0*N1*1. Now a beautiful purely functional solution of complexity O(n) surfaces from generalization to arrays of any length:
// functional solution in O(n) let googleProd a = let partialProducts (arr: int []) = Seq.unfold (fun (acc,i) -> if i >= arr.Length then None else Some(acc, (arr.[i] * acc, i+1))) (1,0) |> Seq.toArray let prefix = partialProducts a let suffix = Array.rev a |> partialProducts |> Array.rev Array.map2 (fun x rx -> x * rx) prefix suffix googleProd [|4;3;2;1;2|] |> printfn "%A"
Very neat!
And after final beautifications it begins looking really elegant:
let googleProd a = let partialProducts xs = xs |> Array.scan (*) 1 |> Seq.take xs.Length |> Seq.toArray let prefix = partialProducts a let suffix = Array.rev a |> partialProducts |> Array.rev Array.map2 (*) prefix suffix googleProd [|4;3;2;1;2|] |> printfn "%A"
A colleague and friend pointed at two beautifications that eventually allowed the solution to acquire the elegant finishing:
Thank you, Dmitry!
@cfj: Joel, while your solution is very succinct and straightforward it is not good for the task, because it violates both original conditions:
– “without division”, as yours has division in line 3
– “in O(n) complexity”, as yours has complexity O(n*n)