# 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:** 20\
**Page:** 2

<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 19, 2008, 11:16am UTC](https://www.ruby-forum.com/t/little-problem-google-hiring-puzzle/140527/21 "2008-06-19T11:16:51Z")

</div>

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

---

<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 19, 2008, 11:33am UTC](https://www.ruby-forum.com/t/little-problem-google-hiring-puzzle/140527/22 "2008-06-19T11:33:24Z")

</div>

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

On Thu, Jun 19, 2008 at 2:45 PM, Ragunathan P.

---

<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 19, 2008, 5:23pm UTC](https://www.ruby-forum.com/t/little-problem-google-hiring-puzzle/140527/23 "2008-06-19T17:23:40Z")

</div>

> 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

---

<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 19, 2008, 6:57pm UTC](https://www.ruby-forum.com/t/little-problem-google-hiring-puzzle/140527/24 "2008-06-19T18:57:53Z")

</div>

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

---

<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 19, 2008, 6:13pm UTC](https://www.ruby-forum.com/t/little-problem-google-hiring-puzzle/140527/25 "2008-06-19T18:13:50Z")

</div>

> > 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](http://svn.ruby-lang.org/cgi-bin/viewvc.cgi/branches/ruby_1_8_7/array.c?view=markup)

---

<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 19, 2008, 7:18pm UTC](https://www.ruby-forum.com/t/little-problem-google-hiring-puzzle/140527/26 "2008-06-19T19:18:03Z")

</div>

On Thu, Jun 19, 2008 at 12:12 PM, Ragunathan P. \<  
removed\_email\_address@domain.invalid\> wrote:

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

–  
Rick DeNatale

My blog on Ruby  
[http://talklikeaduck.denhaven2.com/](http://talklikeaduck.denhaven2.com/)

---

<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 19, 2008, 7:24pm UTC](https://www.ruby-forum.com/t/little-problem-google-hiring-puzzle/140527/27 "2008-06-19T19:24:38Z")

</div>

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

---

<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 19, 2008, 11:51pm UTC](https://www.ruby-forum.com/t/little-problem-google-hiring-puzzle/140527/28 "2008-06-19T23:51:43Z")

</div>

On Jun 19, 2:15 am, Ragunathan P.  
[removed\_email\_address@domain.invalid](mailto:removed_email_address@domain.invalid) wrote:

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

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

---

<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, 4:03am UTC](https://www.ruby-forum.com/t/little-problem-google-hiring-puzzle/140527/29 "2008-06-20T04:03:00Z")

</div>

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}

On Thu, Jun 19, 2008 at 5:56 PM, Martin DeMello  
[removed\_email\_address@domain.invalid](mailto:removed_email_address@domain.invalid)

---

<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, 4:15am UTC](https://www.ruby-forum.com/t/little-problem-google-hiring-puzzle/140527/30 "2008-06-20T04:15:18Z")

</div>

Kevin C. wrote:

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

---

<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, 12:58am UTC](https://www.ruby-forum.com/t/little-problem-google-hiring-puzzle/140527/31 "2008-06-20T00:58:40Z")

</div>

On Thu, Jun 19, 2008 at 10:23 AM, Ragunathan P.  
[removed\_email\_address@domain.invalid](mailto:removed_email_address@domain.invalid) wrote:

> 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[i]  
pre[i] = prod  
}

prod = 1  
n.downto(0) {|i|  
prod \*= ary[i]  
post[i] = 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

---

<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:55am UTC](https://www.ruby-forum.com/t/little-problem-google-hiring-puzzle/140527/32 "2008-06-20T06:55:49Z")

</div>

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

---

<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, 8:21am UTC](https://www.ruby-forum.com/t/little-problem-google-hiring-puzzle/140527/33 "2008-06-20T08:21:25Z")

</div>

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

---

<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, 10:41am UTC](https://www.ruby-forum.com/t/little-problem-google-hiring-puzzle/140527/34 "2008-06-20T10:41:07Z")

</div>

Ragunathan P. [removed\_email\_address@domain.invalid](mailto:removed_email_address@domain.invalid) writes:

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

---

<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, 10:50am UTC](https://www.ruby-forum.com/t/little-problem-google-hiring-puzzle/140527/35 "2008-06-20T10:50:34Z")

</div>

yesteray [removed\_email\_address@domain.invalid](mailto:removed_email_address@domain.invalid) writes:

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

---

<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, 10:02am UTC](https://www.ruby-forum.com/t/little-problem-google-hiring-puzzle/140527/36 "2008-06-20T10:02:11Z")

</div>

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

# 

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

how about,

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

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

---

<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, 11:05am UTC](https://www.ruby-forum.com/t/little-problem-google-hiring-puzzle/140527/37 "2008-06-20T11:05:49Z")

</div>

ex [removed\_email\_address@domain.invalid](mailto:removed_email_address@domain.invalid) writes:

> # OUTPUT:[12, 16, 24, 48, 24]
> 
> for k in 0…vals.length  
> 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]

---

<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, 3:21pm UTC](https://www.ruby-forum.com/t/little-problem-google-hiring-puzzle/140527/38 "2008-06-20T15:21:55Z")

</div>

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

> # 
> 
> =\> 4  
> end  
> =\> 1
> 
> p pa  
> [12, 16, 24, 48, 24]  
> =\> nil
> 
> can i pass google? =)
> 
> kind regards -botp

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

---

<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, 11:08am UTC](https://www.ruby-forum.com/t/little-problem-google-hiring-puzzle/140527/39 "2008-06-20T11:08:46Z")

</div>

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

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

J

---

<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, 4:35pm UTC](https://www.ruby-forum.com/t/little-problem-google-hiring-puzzle/140527/40 "2008-06-20T16:35:46Z")

</div>

On Jun 15, 1:59 pm, ex [removed\_email\_address@domain.invalid](mailto:removed_email_address@domain.invalid) wrote:

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

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

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