little problem (google hiring puzzle)

[Ragunathan Pattabiraman]

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

I think eval I used in this case is constant time. Any other views?

 

[Srijayanth Sridhar]

Correct me if I am wrong, but it seems like when you use the range operator:

input[0...index] + input[index+1..-1]

Isn't it basically just iterating over the list and yielding? In which
case, your original loop:

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

will be interpreted as having a nested loop inside. So essentially
your running time is bound to n^2 - n, which is O(n^2)

My thoughts...

J

 

[Ragunathan Pattabiraman]

input[0...index] + input[index+1..-1]

Isn't it basically just iterating over the list and yielding? In which
case, your original loop:

will be interpreted as having a nested loop inside. So essentially
your running time is bound to n^2 - n, which is O(n^2)

each_index is iterating over and yielding, there we have the first loop.
But I am not sure how Ruby Array's [] is implemented when a range is
given. I will take a look when I get a chance (again there is JRuby,
IronRuby, and the native Ruby).

But isn't it safe to assume it would have optimized implementation done
by Ruby implementors than the ad hoc O(n) implementation?

Cheers,
Ragu

 

[Ragunathan Pattabiraman]

input[0...index] + input[index+1..-1]

Isn't it basically just iterating over the list and yielding? In which
case, your original loop:

will be interpreted as having a nested loop inside. So essentially
your running time is bound to n^2 - n, which is O(n^2)

each_index is iterating over and yielding, there we have the first loop.
But I am not sure how Ruby Array's [] is implemented when a range is
given. I will take a look when I get a chance (again there is JRuby,
IronRuby, and the native Ruby).

But isn't it safe to assume it would have optimized implementation done
by Ruby implementors than the ad hoc O(n) implementation?

I checked Ruby 1.8.7 source code and Array[range] is done at constant
time. Here is the link to array.c
http://svn.ruby-lang.org/cgi-bin/viewvc.cgi/branches/ruby_1_8_7/array.c?view=markup

 

[ThoML]

I checked Ruby 1.8.7 source code and Array[range] is done at constant

time.

IMHO you'd also look at join (iterates over the array) and eval
(parses the string). Eval is IMHO scary in this context because one
(most ruby users or I at least) usually doesn't really know what it
involves.

 

[Rick DeNatale]

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

On Thu, Jun 19, 2008 at 12:12 PM, Ragunathan Pattabiraman <

I checked Ruby 1.8.7 source code and Array[range] is done at constant
time. Here is the link to array.c

http://svn.ruby-lang.org/cgi-bin/viewvc.cgi/branches/ruby_1_8_7/array.c?view=markup

True enough, since Array uses copy on write, so it can take a slice which
points to the same elements.

BUT the culprit is:

input[0...index] + input[index+1..-1]

Look at input[0...index] + input[index+1..-1]

Those two MEMCPY macro calls are loops and add up to an O(n-1) operation.

 

[Ragunathan Pattabiraman]

IMHO you'd also look at join (iterates over the array) and eval
(parses the string). Eval is IMHO scary in this context because one
(most ruby users or I at least) usually doesn't really know what it
involves.

I saw the array#join source which seems to involve a loop. Apparantly
this is O(n^2). Not quite sure about eval though.

I believe Ruby is about elegance and simplicity. Many of the solutions I
saw here were cryptic, at least to me. Stuff from Ruby gurus. I learned
some new stuff studying them.

But simplicity is the virtue that is missing IMHO. I thought I would
attempt at simplicity. But as you pointed out it is not efficient at
all. ("It's another Ruby virtue" says Ruby critic!)

Thank you all for your inputs.

Just wondering... is there any tool which computes the time complexity
given the code? That would be cool as we wouldn't want to checkout ruby
impl everytime.

 

[yesteray]

I think eval I used in this case is constant time. Any other views?

You are evaluating a product of n-1 terms in each eval.

eval(3*2*1*2)
eval(4*2*1*2)
eval(4*3*1*2)
eval(4*3*2*2)
eval(4*3*2*1)

There is no way to optimize these multiplications away.

Ray

 

[Martin DeMello]

But simplicity is the virtue that is missing IMHO. I thought I would
attempt at simplicity. But as you pointed out it is not efficient at
all. ("It's another Ruby virtue" says Ruby critic!)

There's a very simple solution (which I think someone has posted
upthread). The idea is this: you calculate the partial products from
each end of the array. Then, e.g. product(all except x_10) =
product(x0..x9) * product(x11..x20). The code is straightforward, too
(but untested):

pre = []
post = []
prod = 1
n = ary.length - 1

0.upto(n) {|i|
prod *= ary
pre = prod
}

prod = 1
n.downto(0) {|i|
prod *= ary
post = prod
}

product_except = lambda {|i| pre[i-1] * post[i+1]}

Time complexity = O(n) to calculate pre, O(n) to calculate post and
O(1) to calculate product_except(i) for any i, O(n) to calculate them
all for a total of O(n).

martin

 

[Kevin Compton]

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

how bad is this?

inp = [4, 3, 2, 1, 2]
outp = []
inp.each_with_index {|val, idx| inp[idx] = 1; outp << inp.inject(1) { |prod,
val2| prod * val2 }; inp[idx] = val}

But simplicity is the virtue that is missing IMHO. I thought I would
attempt at simplicity. But as you pointed out it is not efficient at
all. ("It's another Ruby virtue" says Ruby critic!)

There's a very simple solution (which I think someone has posted
upthread). The idea is this: you calculate the partial products from
each end of the array. Then, e.g. product(all except x_10) =
product(x0..x9) * product(x11..x20). The code is straightforward, too
(but untested):

pre = []
post = []
prod = 1
n = ary.length - 1

0.upto(n) {|i|
prod *= ary
pre = prod
}

prod = 1
n.downto(0) {|i|
prod *= ary
post = prod
}

product_except = lambda {|i| pre[i-1] * post[i+1]}

Time complexity = O(n) to calculate pre, O(n) to calculate post and
O(1) to calculate product_except(i) for any i, O(n) to calculate them
all for a total of O(n).

martin

 

[Paul McMahon]

how bad is this?

inp = [4, 3, 2, 1, 2]
outp = []
inp.each_with_index {|val, idx| inp[idx] = 1; outp << inp.inject(1) { |prod,
val2| prod * val2 }; inp[idx] = val}

O(n^2). You are iterating through inp within inp (inject will iterate
through each element).

 

[Ragunathan Pattabiraman]

There's a very simple solution (which I think someone has posted
upthread). The idea is this: you calculate the partial products from
each end of the array. Then, e.g. product(all except x_10) =
product(x0..x9) * product(x11..x20). The code is straightforward, too

I agree. Pretty neat!

 

[Jab]

I believe this works in O(n). (I believe reverse, and zip are O(n)) It
is very similar to other solutions, but I like the each_with_index
method.

data=[4, 3, 2, 1, 2]
front=[1];
back=[1]
data.each_with_index{|val, index| front[index + 1] = front[index] * val}
data.reverse.each_with_index {|val, index| back[index+1] = back[index] * val}

front.pop
back.pop
data=[]
front.zip(back.reverse){|a, b| data.push a * b}

p data

-jacob

 

[Peña, Botp]

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


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

how about,

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

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

pa=3D[]
=3D> []

s=3Da.size
=3D> 5

s2=3Ds-1
=3D> 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=3Da+a
=3D> [4, 3, 2, 1, 2, 4, 3, 2, 1, 2]

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

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

can i pass google? =3D)

kind regards -botp

 

[Pascal J. Bourguignon]

Just wondering... is there any tool which computes the time complexity
given the code? That would be cool as we wouldn't want to checkout ruby
impl everytime.

Not in general (try to apply that tool to itself!). But for normal
programs, yes such a tool could be written.

 

[Pascal J. Bourguignon]

You are evaluating a product of n-1 terms in each eval.

eval(3*2*1*2)
eval(4*2*1*2)
eval(4*3*1*2)
eval(4*3*2*2)
eval(4*3*2*1)

There is no way to optimize these multiplications away.

Of course there is a way: factorize them!

eval( 3*2*1*2)
eval(4 * 2*1*2)
eval(4*3 * 1*2)
eval(4*3*2 * 2)
eval(4*3*2*1 )

You can see that there is only two multiplications going on.

 

[Pascal J. Bourguignon]

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

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


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

 

[Srijayanth Sridhar]

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

 

[krusty.ar]

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

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.

 

[botp]

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

ok, no more fun

how about,

001:0> a=[4,3,2,1,2]
=> [4, 3, 2, 1, 2]
002:0> s=a.size
=> 5
003:0> pr=Array.new(s){[1,1]}
=> [[1, 1], [1, 1], [1, 1], [1, 1], [1, 1]]

005:0> (1..s-1).each do |i|
007:1* pr[0] = pr[i-1][0] * a[i-1]
008:1> pr[s-i-1][1] = pr[s-i][1] * a[s-i]
009:1> end
=> 1..4

p pr.map{|x,y| x*y }

[12, 16, 24, 48, 24]


# benchmark test
botp@jedi-hopeful:~$ cat test4.rb

def ohwan(a)
s=a.size
pr=Array.new(s){[1,1]}
(1..s-1).each do |i|
pr[0] = pr[i-1][0] * a[i-1]
pr[s-i-1][1] = pr[s-i][1] * a[s-i]
end
end

array = (1..10_000).map{rand(10_000)}
require 'benchmark'
Benchmark.bmbm do |x|
x.report("10") { ohwan(array[0,10]) }
x.report("100") { ohwan(array[0,100]) }
x.report("1_000") { ohwan(array[0,1_000]) }
x.report("10_000") { ohwan(array[0,10_000]) }
end

botp@jedi-hopeful:~$ ruby test4.rb
Rehearsal ------------------------------------------
10 0.000000 0.000000 0.000000 ( 0.000100)
100 0.000000 0.000000 0.000000 ( 0.002109)
1_000 0.020000 0.000000 0.020000 ( 0.034063)
10_000 0.330000 0.090000 0.420000 ( 0.473850)
--------------------------------- total: 0.440000sec

user system total real
10 0.000000 0.000000 0.000000 ( 0.000103)
100 0.000000 0.000000 0.000000 ( 0.000614)
1_000 0.020000 0.000000 0.020000 ( 0.029036)
10_000 0.350000 0.090000 0.440000 ( 0.519152)