Little problem (google hiring puzzle)

#1

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[i] will be equal to the product of all

the elements of A[] except A[i].

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

#2

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

#3

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? :slight_smile:

Tor Erik

#4

On Jun 15, 12:59 pm, ex removed_email_address@domain.invalid wrote:

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

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.

#5

On Sun, Jun 15, 2008 at 6:59 PM, ex removed_email_address@domain.invalid wrote:

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

class Array
def accumulate init, op

something like this will be in 1.9 :slight_smile:

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.

http://ruby-smalltalk.blogspot.com/


As simple as possible, but not simpler.
Albert Einstein

#6

See also:

http://www.reddit.com/goto?id=6ngfy
http://rant.blackapache.net/2008/06/14/an-interesting-little-problem/
http://www.fsharp.it/2008/06/10/google-interview-question-product-of-other-elements-in-an-array-in-on/
Haskell: http://pastie.textmate.org/215440

#7

On Jun 15, 2008, at 12:44 PM, Rick DeNatale wrote:

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.

#8

On Sun, Jun 15, 2008 at 2:48 PM, Robert D. removed_email_address@domain.invalid
wrote:

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


Rick DeNatale

My blog on Ruby
http://talklikeaduck.denhaven2.com/

#9

On Sun, Jun 15, 2008 at 1:26 PM, Dave T. removed_email_address@domain.invalid wrote:

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.


Rick DeNatale

My blog on Ruby
http://talklikeaduck.denhaven2.com/

#10

On Jun 15, 2008, at 3:29 PM, ThoML wrote:

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

#11

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)

#12

On Sun, Jun 15, 2008 at 9:59 PM, Rick DeNatale removed_email_address@domain.invalid
wrote:

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 :frowning:
Robert

#13

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

#14

On Jun 16, 10:25 pm, ex removed_email_address@domain.invalid 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:

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| [vea[na-i-1],v=a[i]][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)

#15

On Jun 16, 10:25 pm, ex removed_email_address@domain.invalid 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 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.

#16

On 15 Jun 2008, at 18:59, ex wrote:

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

#17

################################################################################

There is an array A[N] of N integers. You have to compose an array

Output[N] such that Output[i] will be equal to the product of all

the elements of A[] except A[i].

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

#18

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

#19

On Jun 18, 2008, at 11:41 AM, Ragunathan P. wrote:

#=

puts output

This is O(n^2).

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

Ray

#20

On Jun 18, 2008, at 11:41 AM, Ragunathan P. wrote:

#=

puts output

This is O(n^2).

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

Ray