Little problem (google hiring puzzle)

ruby-talk
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

···

On Jun 15, 2008, at 11:59 AM, 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):

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

3

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

···

On Jun 15, 12:59 pm, ex <exeQ...@gmail.com> wrote:

====

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.

4

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.

···

On Sun, Jun 15, 2008 at 6:59 PM, ex <exeQtor@gmail.com> wrote:

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

---
As simple as possible, but not simpler.
Albert Einstein

5

See also:


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

6

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

···

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

8

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

···

From: ex [mailto:exeQtor@gmail.com]
#
# Example:
# INPUT:[4, 3, 2, 1, 2]
# OUTPUT:[12, 16, 24, 48, 24]
#
# Note: Solve it without the division operator and in O(n).
# =============================================================

it's friday here, so i guess i'll just join the fun :slight_smile:

how about,

prod= lambda{|a| a.inject(1){|p,x| p*x}}
=> #<Proc:0xb7d708e0@(irb):1>

a=[4,3,2,1,2]
=> [4, 3, 2, 1, 2]

pa=[]
=> []

s=a.size
=> 5

s2=s-1
=> 4

# here is the meat:
# i just concat orig array so i don't need to rotate
# then get subarrays in groups of s2 (a.size-1)

a2=a+a
=> [4, 3, 2, 1, 2, 4, 3, 2, 1, 2]

1.upto(s) do |i|
  pa << prod.call(a2[i,s2])
end
=> 1

p pa
[12, 16, 24, 48, 24]
=> nil

can i pass google? =)

kind regards -botp

9

ex <exeQtor@gmail.com> writes:

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

def google(a)
  r=Array.new(a.length,1)
  m=1; i=0; while (i<a.length) do r[i]*=m; m*=a[i]; i+=1 end
  m=1; i=a.length-1; while (0<=i) do r[i]*=m; m*=a[i]; i-=1 end
  return r
end

irb(main):060:0> google([4,3,2,1,2])
[12, 16, 24, 48, 24]

···

--
__Pascal Bourguignon__

10

Hi, I'm new to this list, here is an implementation that uses just
array index (and pop). With ugly intrumentation.

def resolve(i)
  front, back, o = [1], [1],

  0.upto i.length - 1 do |n|
    front << i[n] * front[n]
    back << i[i.length - 1 - n] * back[n]
    @cost[@r]+=1
  end
  front.pop
  back.pop

  0.upto front.length - 1 do |n|
    o[n] = front[n] * back[ back.length - 1 - n]
    @cost[@r]+=1
  end
  p o
end

@cost =
1.upto 10 do |@r|
  @cost[@r] = 1
  resolve([4, 3, 2, 1, 2]*@r)
end

p @cost

Lucas.

···

On Jun 15, 1:59 pm, ex <exeQ...@gmail.com> wrote:

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

11

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

···

--
Posted via http://www.ruby-forum.com/.

12

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.

···

On Sun, Jun 15, 2008 at 1:26 PM, Dave Thomas <dave@pragprog.com> 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))) }

--
Rick DeNatale

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

13

From the original post:

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

···

On Sun, Jun 15, 2008 at 2:48 PM, Robert Dober <robert.dober@gmail.com> 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.

--
Rick DeNatale

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

14

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

15

This is O(n^2).

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

Ray

···

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

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

# 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

16

This is O(n^2).

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

Ray

···

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

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

# 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

17

prod= lambda{|a| a.inject(1){|p,x| p*x}}

This inject still iterates over n-1 elements for n iterations. That is
still bound to n^2.

=> #<Proc:0xb7d708e0@(irb):1>

a=[4,3,2,1,2]
=> [4, 3, 2, 1, 2]

pa=
=>

s=a.size
=> 5

s2=s-1
=> 4

# here is the meat:
# i just concat orig array so i don't need to rotate
# then get subarrays in groups of s2 (a.size-1)

a2=a+a
=> [4, 3, 2, 1, 2, 4, 3, 2, 1, 2]

1.upto(s) do |i|
pa << prod.call(a2[i,s2])
end
=> 1

J

18

Eyeballing this looks to me like it's O(n^2). You're iterating over the
list (1.upto(s)) and on each iteration you're iterating over the list
(inject).

I have a humble suggestion to make for people who think they've solved
this problem in O(n) time: test it. Time it with 10 entries, 100
entries and 1000 entries in an array and see what happens. If the time
used doesn't increase roughly by an order of magnitude each time through
and instead shoots through the roof, you're not doing O(n).

···

On Fri, 2008-06-20 at 16:59 +0900, Peña, Botp wrote:

From: ex [mailto:exeQtor@gmail.com]
# ##################
# 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).
# =============================================================

it's friday here, so i guess i'll just join the fun :slight_smile:

how about,

prod= lambda{|a| a.inject(1){|p,x| p*x}}
=> #<Proc:0xb7d708e0@(irb):1>

a=[4,3,2,1,2]
=> [4, 3, 2, 1, 2]

pa=
=>

s=a.size
=> 5

s2=s-1
=> 4

# here is the meat:
# i just concat orig array so i don't need to rotate
# then get subarrays in groups of s2 (a.size-1)

a2=a+a
=> [4, 3, 2, 1, 2, 4, 3, 2, 1, 2]

1.upto(s) do |i|
  pa << prod.call(a2[i,s2])
end
=> 1

p pa
[12, 16, 24, 48, 24]
=> nil

can i pass google? =)

kind regards -botp

--
Michael T. Richter <ttmrichter@gmail.com> (GoogleTalk:
ttmrichter@gmail.com)
I have to wonder why people think that when they can't manage local
personnel within easy strangling and shooting distance, then they can
manage personnel thousands of miles away that have different languages,
cultures, and business rules. (Joe Celko)

19

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.

···

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

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.

20

Right Rick but the array did not have n elements but N :).
Maybe I am a little bit autistic :frowning:
Robert

···

On Sun, Jun 15, 2008 at 9:59 PM, Rick DeNatale <rick.denatale@gmail.com> wrote:

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