# Google Interview Question: Product of other Elements in an Array in O(n)

Tags: , | Posted by Admin on 11/3/2008 2:12 PM | Comments (8)

Last time I was interviewed for a software development engineer position, the recruiter asked me some of the classical Microsoft interview questions, such as “How Would You Move Mount Fuji?” or “How many gas station are there in your country?“.

It was the first time for me to be asked such questions but having obtained the job I think my answers were good enough.

After that day, I looked for other well-known interview questions and I discovered that Google has a totally different approach, focusing on algorithms, data structures and complexity.

For instance, one of Google interview questions says:

There is an array A[N] of N integers. You have to compose an array Output[N+1] such that Output[i] will be equal to the product of all the elements of A[] except A[i].

Example:
INPUT:[4, 3, 2, 1, 2]
OUTPUT:[12, 16, 24, 48, 24]

Solve it without division operator and in O(n).

Without the two constraints at the end of the puzzle it would have been straightforward, but now we have to be smart.

Actually, the product of all elements of A[] except A[i] is equal to the product of all elements before A[i] and those after A[i].

We can traverse A[] twice, once from left to right and once in the opposite way and multiply all the elements we find before A[i].

We’ll pretend to have a new array called Output[] to store the output of the first pass, assigning Output[i] the product of all elements preceding A[i]:

1. let rec firstpass product input =
2.     match input with
3.     | [] -> []
4.     | x::xs -> product :: firstpass (product * x) xs

For the second pass we need to move from right to left, but this can be done by reversing the input arrays and moving as usual:

1. let secondpass product input arr =
2.     let rev_input = List.rev input
3.     let rev_arr = List.rev arr
4.     let rec rev_secondpass product (input:list<int>) arr =
5.       match arr with
6.       | [] -> []
7.       | x::xs -> rev_secondpass (product * input.Head) input.Tail xs @ [(x * product)]
8.
9.     rev_secondpass product rev_input rev_arr

Both firstpass and secondpass expect an integer argument called product, which will be always be 1 at the beginning and will be used to store the intermediate products during the recursive calls.

With these functions we can just define an input array and apply them to get the result.

The following is the complete F# code:

1. #light
2.
3. let input = [ 4; 3; 2; 1; 2 ]
4.
6.
7.   let rec firstpass product input =
8.     match input with
9.     | [] -> []
10.     | x::xs -> product :: firstpass (product * x) xs
11.
12.   let secondpass product input arr =
13.     let rev_input = List.rev input
14.     let rev_arr = List.rev arr
15.     let rec rev_secondpass product (input:list<int>) arr =
16.       match arr with
17.       | [] -> []
18.       | x::xs -> rev_secondpass (product * input.Head) input.Tail xs @ [(x * product)]
19.
20.     rev_secondpass product rev_input rev_arr
21.
22.   values |> firstpass 1 |> secondpass 1 values

on 11/2/2008 9:48 PM 2008 at 2:18 am #

[...] fsharp.it posted the above simple Google interview question on their site a few weeks ago and subsequently the problem was referenced by OJ’s rants and later posted to the programming subreddit on reddit.com. Like everyone else, I sat down and wrote some quick code to solve the problem. After looking a the solution, it seemed to me that this was a rather poorly conceived problem- if not contrived at heart. It doen’t ring to the tune of scalability, performance and quality that one thinks of when the word Google is thrown into the mix. [...]
on 11/3/2008 12:06 AM Hi Pavel,
we should check how the concatenation operator @ is implemented, I’m not sure its complexity is O(n).
BTW, your solution is very good!
on 11/3/2008 2:24 AM Hi claudio,

Perhaps I’m wrong, but, IMHO, your solution has O(n^2) or O(n*log(n)) complexity because you use @ operator into recursive function.
@ operator has O(n) complexity itself.

BTW my solution fsharpere.blogspot.com/.../...erview-question.html
on 11/3/2008 4:42 AM Only 4 lines instead of my 22, that’s a great solution!
on 11/3/2008 7:00 AM As a dynamic programming problem you can solve this for small arrays using naive recursion wrapped in a memoize combinator:
view plaincopy to clipboardprint?

1.
let product (a : _ array) =
2.
let rec f = memoize(fun (i, di) ->
3.
if i = a.Length then 1 else f(i+di, di) * a.[i])
4.
Array.init a.Length (fun i -> f(i-1, -1) * f(i+1, 1))
on 11/3/2008 9:18 AM [...] post was inspired by a recent interview question that was posted over at fsharp.it. It’s one of those neat little questions which looks really simple on the surface but is [...]
on 11/3/2008 11:36 AM I’m glad to hear that, in my opinion a good mix of problem solving and coding questions is the best way to interview people for software development positions.
on 11/3/2008 1:54 PM Microsoft focus on the same thing, they have problem solving and coding questions. But they start with the logical ones on phone interviews.