From: Kevin Compton <klcompt@...>
Date: 2008-06-20T11:01:06+09:00
Subject: Re: little problem (google hiring puzzle)

------=_Part_6171_8399859.1213927350530
Content-Type: text/plain; charset=ISO-8859-1
Content-Transfer-Encoding: 7bit
Content-Disposition: inline

how bad is this?

inp = [4, 3, 2, 1, 2]
outp = []
inp.each_with_index {|val, idx| inp[idx] = 1; outp << inp.inject(1) { |prod,
val2| prod * val2 }; inp[idx] = val}


On Thu, Jun 19, 2008 at 5:56 PM, Martin DeMello <martindemello@gmail.com>
wrote:

> On Thu, Jun 19, 2008 at 10:23 AM, Ragunathan Pattabiraman
> <ragunathan.pattabiraman@gmail.com> wrote:
> >
> > But simplicity is the virtue that is missing IMHO. I thought I would
> > attempt at simplicity. But as you pointed out it is not efficient at
> > all. ("It's another Ruby virtue" says Ruby critic!)
>
> There's a very simple solution (which I think someone has posted
> upthread). The idea is this: you calculate the partial products from
> each end of the array. Then, e.g.  product(all except x_10) =
> product(x0..x9) * product(x11..x20). The code is straightforward, too
> (but untested):
>
> pre = []
> post = []
> prod = 1
> n = ary.length - 1
>
> 0.upto(n) {|i|
>  prod *= ary[i]
>  pre[i] = prod
> }
>
> prod = 1
> n.downto(0) {|i|
>  prod *= ary[i]
>  post[i] = prod
> }
>
> product_except = lambda {|i| pre[i-1] * post[i+1]}
>
> Time complexity = O(n) to calculate pre, O(n) to calculate post and
> O(1) to calculate product_except(i) for any i, O(n) to calculate them
> all for a total of O(n).
>
> martin
>
>

------=_Part_6171_8399859.1213927350530--