heyPanda

Originally posted January 30, 2008 at masonbrowne.info:

My friend recently received a technical interview for Google. One of the problems he was tasked to solve over the phone went something like this:

Given a list A with n elements, produce a list B with n elements such that the ith element of B is equal to the product of all elements except the ith in list A. Example: Given list A = [1, 2, 3], make a function f(x) such that f(A) = [6, 3, 2].

He came up with two solutions, one O(n) which used division, and one O(n^2) which did not. Apparently the Google interviewer said, "Assume division is slow" and asked him to find another solution. Given that this was a phone interview with the Almighty Google, it's understandable that he was unable to produce another solution on the spot. When I was interviewed at Lucky Oliver, I had several interviews, one of which was slightly technical. As someone who hates phones and riddles, being asked to solve a riddles over the phone is something I'm just not good at. I am, however, often able to come up with a solution in a few seconds if I'm sitting by myself. So that's what I did when my friend posed his interview question to me.

Since division was slow and we wanted to keep this thing O(n), I thought for a second, and asked if he had come up with a DP-based solution. After a few refinements, this is what I had:

                    def weird_sum(l)
                      the_start = 0; the_end = l.length-1; n_l = []; storage = {}
                      the_start.upto(the_end) do |n|
                        forward_end = n-1; forward_record = n; reverse_end = ((n - the_end) * -1) + 1;reverse_record = reverse_end - 1
                        storage[(the_start..forward_record)] = (storage[(the_start..forward_end)] ||= 1) * l[forward_record]
                        storage[(the_end..reverse_record)] = (storage[(the_end..reverse_end)] ||= 1) * l[reverse_record]
                      end and the_start.upto(the_end) do |n|
                        n_l[n] = storage[(the_start..(n-1))] * storage[(the_end..(n+1))]
                      end and n_l
                    end
                    require 'pp'
                    pp weird_sum([1, 2, 3])
                  

As near as I can tell, this has a spatial complexity of 3n+4 (space for the solution, stored products from the left and right, plus high and low boundaries of 1 for each left and right) and a time complexity of 2n. Technically, I could replace the elements in the original list and shrink the space down to 2n+4. But I won't. Because I'm not the one interviewing for Google. And if I was, I'm guessing this still isn't Google-grade. Oh well.

Anyhow... the only thing clever about my solution is that it incrementally pre-calculates the products from the left and right. So given the list [1, 2, 3], it stores the following:

                  {2..2=>3, 2..3=>1, 0..0=>1, 0..1=>2, 0..-1=>1, 0..2=>6, 2..0=>6, 2..1=>6}
                  

2..3 and 0..-1 are used in the place of conditional multiplies, since multiplying by 1 doesn't hurt nothin'. Anyhow. Thanks for the brain-teaser, friend.