Hi guys, I wonder if someone can find a pure ruby solution instead of
mine (I still can get out of my loop mind):
You can certainly do things in a more Rubyish way, but since you’re
constrained by the computational complexity, any method you use you
have to know the complexity of. And the Ruby docs don’t necessarily
tell you, forcing you to dig into the Ruby source, much of which is in
C.
For example, you use the code:
back.unshift(mb)
That line is in a loop of n iterations. Now if unshift is itself
O(n), you just went to O(n**2). Oops!
Here’s a snippet of your code:
ans = []
front.each_index{|k| ans.push(front[k]*back[k]) }
A more Rubyish way to do that would be:
ans = front.zip(back).map { |f, b| f * b }
But I can’t be certain of the computational complexity of the call to
zip. Now I suspect it is O(n), and if it is then you’re home free.
But if not you can kiss your Google dream job goodbye.
Eric
====
LearnRuby.com offers Rails & Ruby HANDS-ON public & ON-SITE
workshops.
Ruby Fundamentals Workshop June 16-18 Ann Arbor, Mich.
Ready for Rails R. 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.
Quite nice, and I’m more convinced that this is actually O(n) than the
original solution. I suspect that Array#unshift is O(n) itself in most
implementations which would make for O(m) where n < m <= n*2, since
it’s
used n times in a loop.
I think it might be O(n log n) but don’t have the time right now to
prove
that.
is probably outside the scope of the domain of integers considered by
Google when setting the problem, but it’s an interesting exercise to
see how to scale the log sum, do the work, then scale the answers
back. It’s still O(N) in that case…
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 R. 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.
Hi guys, I wonder if someone can find a pure ruby solution instead of
mine (I still can get out of my loop mind):
This works
a = [4, 3, 2, 1, 2]
x = a.inject([1]) { |sum, i | sum << sum.last * i }
x.pop
y = a.reverse.inject([1]) { |sum, i| sum << sum.last * i }
y.pop
y.reverse!
o = []
a.length.times { |i| o[i] = x[i] * y[i] }
p o
