From: Calamitas Date: 2008-06-21T16:54:06+09:00 Subject: Re: little problem (google hiring puzzle) On Fri, Jun 20, 2008 at 6:52 PM, botp wrote: > 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) 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