# Little problem (google hiring puzzle)

**URL:** <https://www.ruby-forum.com/t/little-problem-google-hiring-puzzle/140527>\
**Category:** Ruby\
**Created:** [June 15, 2008, 7:09pm UTC](https://www.ruby-forum.com/t/little-problem-google-hiring-puzzle/140527 "2008-06-15T19:09:28Z")\
**Posts on this page:** 3\
**Page:** 3

<div class="post-metadata">

**Author:** ![exexex](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/e/5daacb/32.png) [@exexex](https://www.ruby-forum.com/u/exexex)\
**Post date:** [June 21, 2008, 9:56am UTC](https://www.ruby-forum.com/t/little-problem-google-hiring-puzzle/140527/41 "2008-06-21T09:56:41Z")

</div>

On Fri, Jun 20, 2008 at 6:52 PM, botp [removed\_email\_address@domain.invalid](mailto:removed_email_address@domain.invalid) 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

---

<div class="post-metadata">

**Author:** ![exexex](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/e/5daacb/32.png) [@exexex](https://www.ruby-forum.com/u/exexex)\
**Post date:** [June 20, 2008, 6:54pm UTC](https://www.ruby-forum.com/t/little-problem-google-hiring-puzzle/140527/42 "2008-06-20T18:54:28Z")

</div>

On Fri, Jun 20, 2008 at 9:18 PM, Michael T. Richter  
[removed\_email\_address@domain.invalid](mailto:removed_email_address@domain.invalid) 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 🙂

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)

---

<div class="post-metadata">

**Author:** ![exexex](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/e/5daacb/32.png) [@exexex](https://www.ruby-forum.com/u/exexex)\
**Post date:** [June 23, 2008, 6:11am UTC](https://www.ruby-forum.com/t/little-problem-google-hiring-puzzle/140527/43 "2008-06-23T06:11:07Z")

</div>

From: Calamitas [[mailto:removed\_email\_address@domain.invalid](mailto:removed_email_address@domain.invalid)]

# 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

[Previous page](https://www.ruby-forum.com/t/little-problem-google-hiring-puzzle/140527.md?page=2)