Skip to content

A Question from Google Interview

October 15, 2011

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"
Advertisements

From → Uncategorized

3 Comments
  1. A colleague and friend pointed at two beautifications that eventually allowed the solution to acquire the elegant finishing:

    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"
    

    Thank you, Dmitry!

  2. cfj permalink
    let outputArr arr = Array.init (arr |> Array.length) (fun i -> 
        let allProduct = Array.fold (fun s t -> s*t) 1 arr
        allProduct/arr.[i])
    
    • @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)

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: