Little problem (google hiring puzzle)

Ruby
41

On Fri, Jun 20, 2008 at 6:52 PM, botp [email protected] wrote:

Rehearsal ------------------------------------------
10_000 0.350000 0.090000 0.440000 ( 0.519152)
Your solution looks fine. But your benchmarking will yield some weird
results.

For starters, I would at least include a few more measuring points.
Now you have two significant ones as the first two are unmeasurably
small and thus useless. Through two points, you can fit pretty much
any type of curve, from sublinear to hypergeometric.

But you are likely to see widely varying results. The puzzle assumes
that multiplication is O(1). That’s true for Fixnums , but not for
Bignums. Bignum multiplication is O(n.log(n)) or O(n^2) depending on
Ruby’s implementation. So say your random array starts and ends with
0,then you will stay in the Fixnum range and you will measure O(n)
performance. If your random array happens to be full of numbers around
100 or so, your benchmark should show O(n^2.log(n)) or O(n^3)
behavior. To stay in the Fixnum range and get O(1) performance for
multiplication, use an array of all 0 or 1. Then you should see linear
performance. Using an array of all 100 should give predictable
results, but you should see O(n^2.log(n)) or O(n^3) behavior.

Peter

42

On Fri, Jun 20, 2008 at 9:18 PM, Michael T. Richter
[email protected] wrote:

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

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[i][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[i][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)

43

From: Calamitas [mailto:[email protected]]

But you are likely to see widely varying results. The puzzle assumes

that multiplication is O(1). That’s true for Fixnums , but not for

Bignums. Bignum multiplication is O(n.log(n)) or O(n^2) depending on

Ruby’s implementation. So say your random array starts and ends with

0,then you will stay in the Fixnum range and you will measure O(n)

performance. If your random array happens to be full of numbers around

100 or so, your benchmark should show O(n^2.log(n)) or O(n^3)

behavior. To stay in the Fixnum range and get O(1) performance for

multiplication, use an array of all 0 or 1. Then you should see linear

performance. Using an array of all 100 should give predictable

results, but you should see O(n^2.log(n)) or O(n^3) behavior.

totally.
i tested it again by using different array values, and using a simple
loop like,

Benchmark.bmbm do |x|
0.step(10_000,100) do |i|
x.report(i.to_s) { ohwan(array[0,i]) }
end
end

the difference is tremendous.

thank you for the enlightenment, Peter.
kind regards -botp