From: simon jenkins <simojenki@...>
Date: 2008-06-17T15:54:41+09:00
Subject: Re: little problem (google hiring puzzle)

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

its ugly, could be written in any language, but it works and should be
O(n).

def products input
  li, ri, prod_left, prod_right = 0, input.length - 1, 1, 1
  res = Array.new(input.length, 1)
  while (li < input.length)
    prod_left = prod_left * (li != 0 ? input[li - 1] : 1)
    prod_right = prod_right * (ri != (input.length - 1) ? input[ri + 1] : 1)
    res[li] *= prod_left
    res[ri] *= prod_right
    li += 1
    ri -= 1
  end
  res
end

cheers

simon



On Tue, Jun 17, 2008 at 6:44 AM, Eric I. <rubytraining@gmail.com> wrote:

> On Jun 16, 10:25 pm, ex <exeQ...@gmail.com> wrote:
> > I wasn't aware of the unshift overload, here I think I got O(n),
> > however this looks more like C++ than ruby imho.
>
> Yeah, the challenge is that to insure O(n) you have to use just the
> basic Array operations removing some of the Ruby tricks from your
> toolbox.  Sometimes other constraints dominate, and there's not a
> whole lot you can do.  But I agree with you that your second solution
> is O(n).
>
> By the way, in case it wasn't clear, the problem with Array#unshift is
> that by inserting at the beginning of the array, it likely requires
> that all other elements to need to shift up by one, making it O(n).
> Pushing onto the end of the array is likely O(1).  And, Array#reverse
> (and Array#reverse!) are likely O(n).  So one way around the problem
> is to create the array in the "wrong" direction and the reverse it.
>
> I don't think that this solution has all the Ruby niceness, but I'm
> pretty sure it's O(n):
>
> ====
>
> vals = [4, 3, 2, 1, 2]
>
> forward_prods = [1]
> 0.upto(vals.size - 2) do |i|
>  forward_prods << forward_prods.last * vals[i]
> end
>
> backward_prods = [1]
> (vals.size - 1).downto(1) do |i|
>  backward_prods << backward_prods.last * vals[i]
> end
> backward_prods.reverse!
>
> answer = forward_prods.zip(backward_prods).map { |f, b| f * b }
>
> p answer
>
> ====
>
> Best,
>
> Eric
>
> ====
>
> LearnRuby.com offers Rails & Ruby HANDS-ON public & ON-SITE
> workshops.
>    Ready for Rails Ruby Workshop     June 23-24    Ann Arbor, Mich.
>   Ruby on Rails Workshop            June 25-27    Ann Arbor, Mich.
>   Ruby Plus Rails Combo Workshop    June 23-27    Ann Arbor, Mich.
> Please visit http://LearnRuby.com for all the details.
>
>

------=_Part_411_197159.1213685744710--