little problem (google hiring puzzle)

E

ex

Hi guys, I wonder if someone can find a pure ruby solution instead of
mine (I still can get out of my *loop* mind):

################################################################################
# There is an array A[N] of N integers. You have to compose an array
# Output[N] such that Output will be equal to the product of all
# the elements of A[] except A.
#
# Example:
# INPUT:[4, 3, 2, 1, 2]
# OUTPUT:[12, 16, 24, 48, 24]
#
# Note: Solve it without the division operator and in O(n).
#===============================================================================

vals = [4, 3, 2, 1, 2]

front = []
back = []
mf = 1
mb = 1
for k in 0...vals.length
front.push(mf)
back.unshift(mb)
mf *= vals[k]
mb *= vals[vals.length - 1 - k]
end

ans = []
front.each_index{|k| ans.push(front[k]*back[k]) }

p vals
p ans
 
D

Dave Thomas

How about a little cheat...

vals = [4, 3, 2, 1, 2]
sum_logs = vals.map {|v| Math.log(v)}.inject {|a,b| a+b}
p vals.map {|v| Integer(Math.exp(sum_logs - Math.log(v))) }

Dave
 
T

Tor Erik Linnerud

vals = [4, 3, 2, 1, 2]
product = integers.reduce(&:*)
p vals.map{|n| product.quo(n).to_i}

I don't see a division operator in there, do you? :)

Tor Erik
 
R

Rick DeNatale

[Note: parts of this message were removed to make it a legal post.]

How about a little cheat...

vals = [4, 3, 2, 1, 2]
sum_logs = vals.map {|v| Math.log(v)}.inject {|a,b| a+b}
p vals.map {|v| Integer(Math.exp(sum_logs - Math.log(v))) }


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.
 
E

Eric I.

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 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.
 
R

Robert Dober

vals = ARGV.map{|x| Integer x}

class Array
def accumulate init, op
# something like this will be in 1.9 :)
inject([init]){ |a,e| a << a.last.send( op, e ) }
end
end

ans = vals[0..-2].accumulate(1, :*).
zip( vals[1..-1].reverse.accumulate(1, :*).reverse ).
map{|x,y| x * y }

p vals
p ans

I feel that one can rely on map, reverse, zip and inject to be O(N)
anyway nobody asked you for O(N) performance IIRC.
 
D

Dave Thomas

vals = [4, 3, 2, 1, 2]
sum_logs = vals.map {|v| Math.log(v)}.inject {|a,b| a+b}
p vals.map {|v| Integer(Math.exp(sum_logs - Math.log(v))) }


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.

Adding one extra element to vals adds:

- one more iteration to the sum loop,
- one extra call to Math.log in that loop,
- one extra iteration to the inject loop
- one extra iteration around the second map loop
- one extra call to Math.log
- one extra call to Math.exp
- one extra call to Integer

I'm guessing it's linear, but I may well be wrong.

We could memoize Math.log(v), but that would only affect running time,
and not the order or the algorithm.
 
R

Rick DeNatale

[Note: parts of this message were removed to make it a legal post.]

I feel that one can rely on map, reverse, zip and inject to be O(N)
anyway nobody asked you for O(N) performance IIRC.

From the original post:

# Note: Solve it without the division operator and in O(n).
 
T

ThoML

I'm guessing it's linear, but I may well be wrong.

There appears to be another minor complication. If one increases the
size of vals

vals *= 200

one gets an error: `Integer': Infinity (FloatDomainError)
 
D

Dave Thomas

There appears to be another minor complication. If one increases the
size of vals

vals *= 200

one gets an error: `Integer': Infinity (FloatDomainError)

Well, to be fair,

1771117911399122021943501576570463920868438730355453249145726540660962310694485994703406981661443989507309617613625154922865835810313868152815318277751521931338734019325348671637367964185869331777657562542031550576686039535823298586722498517733604903356381988668531963257069336339415675144908390480164171374292523565379769479171592421376

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...


Dave
 
R

Robert Dober

# Note: Solve it without the division operator and in O(n).
Right Rick but the array did not have n elements but N :).
Maybe I am a little bit autistic :(
Robert
 
E

ex

I wasn't aware of the unshift overload, here I think I got O(n),
however this looks more like C++ than ruby imho:


vals = [4, 3, 2, 1, 2]

ans = Array.new(vals.size)
mp = 1

for k in 0...vals.length
ans[k] = mp
mp *= vals[k]
end

mp = 1
for k in 0...vals.length
ans[vals.length - 1 - k] *= mp
mp *= vals[vals.length - 1 - k]
end

p vals
p ans
 
V

vsv

I wasn't aware of the unshift overload, here I think I got O(n),
however this looks more like C++ than ruby imho:

# How this looks?

def prod_all_but_me(a)
na = a.size
v = 1
ea = Array.new(na){ |i| [v,v*=a[na-i-1]][0] }
v = 1
Array.new(na){ |i| [v*ea[na-i-1],v*=a][0] }
end

# array size
n = (ARGV[0]||5).to_i
# INPUT (random array)
a = (1..n).to_a.sort_by{ rand }
p a
# OUTPUT
p prod_all_but_me(a)
 
E

Eric I.

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
end

backward_prods = [1]
(vals.size - 1).downto(1) do |i|
backward_prods << backward_prods.last * vals
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.
 
S

simon jenkins

[Note: parts of this message were removed to make it a legal post.]

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



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
end

backward_prods = [1]
(vals.size - 1).downto(1) do |i|
backward_prods << backward_prods.last * vals
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.
 
C

Christoffer Lernö

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 = x * y }
p o
 
R

Ragunathan Pattabiraman

################################################################################
# There is an array A[N] of N integers. You have to compose an array
# Output[N] such that Output will be equal to the product of all
# the elements of A[] except A.
#
# Example:
# INPUT:[4, 3, 2, 1, 2]
# OUTPUT:[12, 16, 24, 48, 24]
#
# Note: Solve it without the division operator and in O(n).
#===============================================================================


Here is my attempt:

input = [4,3,2,1,2]
output = []

input.each_index do |index|
odd_man_out = input[0...index] + input[index+1..-1]
starry_night = odd_man_out.join('*')
output << eval(starry_night)
end

puts output

Cheers,
Ragu
 
R

Ray Baxter

################################################################################
# There is an array A[N] of N integers. You have to compose an array
# Output[N] such that Output will be equal to the product of all
# the elements of A[] except A.
#
# Example:
# INPUT:[4, 3, 2, 1, 2]
# OUTPUT:[12, 16, 24, 48, 24]
#
# Note: Solve it without the division operator and in O(n).
#=
=
=
=
=
=
=
=
=
=
=====================================================================


Here is my attempt:

input = [4,3,2,1,2]
output = []

input.each_index do |index|
odd_man_out = input[0...index] + input[index+1..-1]
starry_night = odd_man_out.join('*')
output << eval(starry_night)
end

puts output



This is O(n^2).

Each eval is O(n-1). You do n of them.

Ray
 
R

Ray Baxter

################################################################################
# There is an array A[N] of N integers. You have to compose an array
# Output[N] such that Output will be equal to the product of all
# the elements of A[] except A.
#
# Example:
# INPUT:[4, 3, 2, 1, 2]
# OUTPUT:[12, 16, 24, 48, 24]
#
# Note: Solve it without the division operator and in O(n).
#=
=
=
=
=
=
=
=
=
=
=====================================================================


Here is my attempt:

input = [4,3,2,1,2]
output = []

input.each_index do |index|
odd_man_out = input[0...index] + input[index+1..-1]
starry_night = odd_man_out.join('*')
output << eval(starry_night)
end

puts output


This is O(n^2).

Each eval is O(n-1). You do n of them.

Ray
 

Ask a Question

Want to reply to this thread or ask your own question?

You'll need to choose a username for the site, which only take a couple of moments. After that, you can post your question and our members will help you out.

Ask a Question

Members online

Forum statistics

Threads
473,733
Messages
2,569,439
Members
44,829
Latest member
PIXThurman

Latest Threads

Top