From: "Eric I." <rubytraining@...>
Date: 2008-06-17T14:44:11+09:00
Subject: Re: little problem (google hiring puzzle)

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.