# 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:** 1

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

</div>

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

#===============================================================================

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

---

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

</div>

How about a little cheat…

vals = [4, 3, 2, 1, 2]  
sum\_logs = vals.map {|v| Math.log(v)}.inject {|a,b| a+b}  
p vals.map {|v| Integer(Math.exp(sum\_logs - Math.log(v))) }

Dave

---

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

</div>

vals = [4, 3, 2, 1, 2]  
product = integers.reduce(&:\*)  
p vals.map{|n| product.quo(n).to\_i}

I don’t see a division operator in there, do you? 🙂

Tor Erik

---

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

</div>

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

> Hi guys, I wonder if someone can find a pure ruby solution instead of  
> mine (I still can get out of my _loop_ mind):

You can certainly do things in a more Rubyish way, but since you’re  
constrained by the computational complexity, any method you use you  
have to know the complexity of. And the Ruby docs don’t necessarily  
tell you, forcing you to dig into the Ruby source, much of which is in  
C.

For example, you use the code:

> back.unshift(mb)

That line is in a loop of n iterations. Now _if_ unshift is itself  
O(n), you just went to O(n\*\*2). Oops!

Here’s a snippet of your code:

> ans = []  
> front.each\_index{|k| ans.push(front[k]\*back[k]) }

A more Rubyish way to do that would be:

ans = front.zip(back).map { |f, b| f \* b }

But I can’t be certain of the computational complexity of the call to  
zip. Now I suspect it is O(n), and if it is then you’re home free.  
But if not you can kiss your Google dream job goodbye. 😉

Eric

====

[LearnRuby.com](http://LearnRuby.com) offers Rails & Ruby HANDS-ON public & ON-SITE  
workshops.  
Ruby Fundamentals Workshop June 16-18 Ann Arbor, Mich.  
Ready for Rails R. Workshop June 23-24 Ann Arbor, Mich.  
Ruby on Rails Workshop June 25-27 Ann Arbor, Mich.  
Ruby Plus Rails Combo Workshop June 23-27 Ann Arbor, Mich.  
Please visit [http://LearnRuby.com](http://LearnRuby.com) for all the details.

---

<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 15, 2008, 8:50pm UTC](https://www.ruby-forum.com/t/little-problem-google-hiring-puzzle/140527/5 "2008-06-15T20:50:03Z")

</div>

On Sun, Jun 15, 2008 at 6:59 PM, ex [removed\_email\_address@domain.invalid](mailto:removed_email_address@domain.invalid) wrote:

vals = ARGV.map{|x| Integer x}

class Array  
def accumulate init, op

# something like this will be in 1.9 🙂

```
inject([init]){ |a,e| a << a.last.send( op, e ) }

```

end  
end

ans = vals[0…-2].accumulate(1, :_).  
zip( vals[1…-1].reverse.accumulate(1, :_).reverse ).  
map{|x,y| x \* y }

p vals  
p ans

## I feel that one can rely on map, reverse, zip and inject to be O(N) anyway nobody asked you for O(N) performance IIRC.

[http://ruby-smalltalk.blogspot.com/](http://ruby-smalltalk.blogspot.com/)

* * *

As simple as possible, but not simpler.  
Albert Einstein

---

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

</div>

See also:

[http://www.reddit.com/goto?id=6ngfy](http://www.reddit.com/goto?id=6ngfy)  
[http://rant.blackapache.net/2008/06/14/an-interesting-little-problem/](http://rant.blackapache.net/2008/06/14/an-interesting-little-problem/)  
[http://www.fsharp.it/2008/06/10/google-interview-question-product-of-other-elements-in-an-array-in-on/](http://www.fsharp.it/2008/06/10/google-interview-question-product-of-other-elements-in-an-array-in-on/)  
Haskell: [http://pastie.textmate.org/215440](http://pastie.textmate.org/215440)

---

<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 15, 2008, 9:14pm UTC](https://www.ruby-forum.com/t/little-problem-google-hiring-puzzle/140527/7 "2008-06-15T21:14:50Z")

</div>

On Jun 15, 2008, at 12:44 PM, Rick DeNatale wrote:

> used n times in a loop.
> 
> I think it might be O(n log n) but don’t have the time right now to  
> prove  
> that.

Adding one extra element to vals adds:

- one more iteration to the sum loop,
- one extra call to Math.log in that loop,
- one extra iteration to the inject loop
- one extra iteration around the second map loop
- one extra call to Math.log
- one extra call to Math.exp
- one extra call to Integer

I’m guessing it’s linear, but I may well be wrong.

We could memoize Math.log(v), but that would only affect running time,  
and not the order or the algorithm.

---

<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 15, 2008, 10:01pm UTC](https://www.ruby-forum.com/t/little-problem-google-hiring-puzzle/140527/8 "2008-06-15T22:01:31Z")

</div>

On Sun, Jun 15, 2008 at 2:48 PM, Robert D. [removed\_email\_address@domain.invalid](mailto:removed_email_address@domain.invalid)  
wrote:

> I feel that one can rely on map, reverse, zip and inject to be O(N)  
> anyway nobody asked you for O(N) performance IIRC.

From the original post:

# Note: Solve it without the division operator and in O(n).

–  
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 15, 2008, 7:46pm UTC](https://www.ruby-forum.com/t/little-problem-google-hiring-puzzle/140527/9 "2008-06-15T19:46:07Z")

</div>

On Sun, Jun 15, 2008 at 1:26 PM, Dave T. [removed\_email\_address@domain.invalid](mailto:removed_email_address@domain.invalid) wrote:

> How about a little cheat…
> 
> vals = [4, 3, 2, 1, 2]  
> sum\_logs = vals.map {|v| Math.log(v)}.inject {|a,b| a+b}  
> p vals.map {|v| Integer(Math.exp(sum\_logs - Math.log(v))) }

Quite nice, and I’m more convinced that this is actually O(n) than the  
original solution. I suspect that Array#unshift is O(n) itself in most  
implementations which would make for O(m) where n \< m \<= n\*2, since  
it’s  
used n times in a loop.

I think it might be O(n log n) but don’t have the time right now to  
prove  
that.

–  
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 15, 2008, 11:01pm UTC](https://www.ruby-forum.com/t/little-problem-google-hiring-puzzle/140527/10 "2008-06-15T23:01:35Z")

</div>

On Jun 15, 2008, at 3:29 PM, ThoML wrote:

> There appears to be another minor complication. If one increases the  
> size of vals
> 
> vals \*= 200
> 
> one gets an error: `Integer’: Infinity (FloatDomainError)

Well, to be fair,

1771117911399122021943501576570463920868438730355453249145726540660962310694485994703406981661443989507309617613625154922865835810313868152815318277751521931338734019325348671637367964185869331777657562542031550576686039535823298586722498517733604903356381988668531963257069336339415675144908390480164171374292523565379769479171592421376

is probably outside the scope of the domain of integers considered by  
Google when setting the problem, but it’s an interesting exercise to  
see how to scale the log sum, do the work, then scale the answers  
back. It’s still O(N) in that case…

Dave

---

<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 15, 2008, 10:30pm UTC](https://www.ruby-forum.com/t/little-problem-google-hiring-puzzle/140527/11 "2008-06-15T22:30:25Z")

</div>

> I’m guessing it’s linear, but I may well be wrong.

There appears to be another minor complication. If one increases the  
size of vals

vals \*= 200

one gets an error: `Integer’: Infinity (FloatDomainError)

---

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

</div>

On Sun, Jun 15, 2008 at 9:59 PM, Rick DeNatale [removed\_email\_address@domain.invalid](mailto:removed_email_address@domain.invalid)  
wrote:

> # Note: Solve it without the division operator and in O(n).

Right Rick but the array did not have n elements but N :).  
Maybe I am a little bit autistic ☹  
Robert

---

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

</div>

I wasn’t aware of the unshift overload, here I think I got O(n),  
however this looks more like C++ than ruby imho:

vals = [4, 3, 2, 1, 2]

ans = Array.new(vals.size)  
mp = 1

for k in 0…vals.length  
ans[k] = mp  
mp \*= vals[k]  
end

mp = 1  
for k in 0…vals.length  
ans[vals.length - 1 - k] \*= mp  
mp \*= vals[vals.length - 1 - k]  
end

p vals  
p ans

---

<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 17, 2008, 7:15am UTC](https://www.ruby-forum.com/t/little-problem-google-hiring-puzzle/140527/14 "2008-06-17T07:15:19Z")

</div>

On Jun 16, 10:25 pm, ex [removed\_email\_address@domain.invalid](mailto:removed_email_address@domain.invalid) wrote:

> I wasn’t aware of the unshift overload, here I think I got O(n),  
> however this looks more like C++ than ruby imho:

# How this looks?

def prod\_all\_but\_me(a)  
na = a.size  
v = 1  
ea = Array.new(na){ |i| [v,v\*=a[na-i-1]][0] }  
v = 1  
Array.new(na){ |i| [v_ea[na-i-1],v_=a[i]][0] }  
end

# array size

n = (ARGV[0]||5).to\_i

# INPUT (random array)

a = (1…n).to\_a.sort\_by{ rand }  
p a

# OUTPUT

p prod\_all\_but\_me(a)

---

<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 17, 2008, 7:46am UTC](https://www.ruby-forum.com/t/little-problem-google-hiring-puzzle/140527/15 "2008-06-17T07:46:24Z")

</div>

On Jun 16, 10:25 pm, ex [removed\_email\_address@domain.invalid](mailto:removed_email_address@domain.invalid) wrote:

> I wasn’t aware of the unshift overload, here I think I got O(n),  
> however this looks more like C++ than ruby imho.

Yeah, the challenge is that to insure O(n) you have to use just the  
basic Array operations removing some of the Ruby tricks from your  
toolbox. Sometimes other constraints dominate, and there’s not a  
whole lot you can do. But I agree with you that your second solution  
is O(n).

By the way, in case it wasn’t clear, the problem with Array#unshift is  
that by inserting at the beginning of the array, it likely requires  
that all other elements to need to shift up by one, making it O(n).  
Pushing onto the end of the array is likely O(1). And, Array#reverse  
(and Array#reverse!) are likely O(n). So one way around the problem  
is to create the array in the “wrong” direction and the reverse it.

I don’t think that this solution has all the Ruby niceness, but I’m  
pretty sure it’s O(n):

====

vals = [4, 3, 2, 1, 2]

forward\_prods = [1]  
0.upto(vals.size - 2) do |i|  
forward\_prods \<\< forward\_prods.last \* vals[i]  
end

backward\_prods = [1]  
(vals.size - 1).downto(1) do |i|  
backward\_prods \<\< backward\_prods.last \* vals[i]  
end  
backward\_prods.reverse!

answer = forward\_prods.zip(backward\_prods).map { |f, b| f \* b }

p answer

====

Best,

Eric

====

[LearnRuby.com](http://LearnRuby.com) offers Rails & Ruby HANDS-ON public & ON-SITE  
workshops.  
Ready for Rails R. Workshop June 23-24 Ann Arbor, Mich.  
Ruby on Rails Workshop June 25-27 Ann Arbor, Mich.  
Ruby Plus Rails Combo Workshop June 23-27 Ann Arbor, Mich.  
Please visit [http://LearnRuby.com](http://LearnRuby.com) for all the details.

---

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

</div>

On 15 Jun 2008, at 18:59, ex wrote:

> Hi guys, I wonder if someone can find a pure ruby solution instead of  
> mine (I still can get out of my _loop_ mind):

This works

a = [4, 3, 2, 1, 2]  
x = a.inject([1]) { |sum, i | sum \<\< sum.last \* i }  
x.pop  
y = a.reverse.inject([1]) { |sum, i| sum \<\< sum.last \* i }  
y.pop  
y.reverse!  
o = []  
a.length.times { |i| o[i] = x[i] \* y[i] }  
p o

---

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

</div>

################################################################################

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

Here is my attempt:

input = [4,3,2,1,2]  
output = []

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

puts output

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

</div>

its ugly, could be written in any language, but it works and should be  
O(n).

def products input  
li, ri, prod\_left, prod\_right = 0, input.length - 1, 1, 1  
res = Array.new(input.length, 1)  
while (li \< input.length)  
prod\_left = prod\_left \* (li != 0 ? input[li - 1] : 1)  
prod\_right = prod\_right \* (ri != (input.length - 1) ? input[ri + 1]  
: 1)  
res[li] \*= prod\_left  
res[ri] \*= prod\_right  
li += 1  
ri -= 1  
end  
res  
end

cheers

simon

---

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

</div>

On Jun 18, 2008, at 11:41 AM, Ragunathan P. wrote:

> > #=
> 
> puts output

This is O(n^2).

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

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

</div>

On Jun 18, 2008, at 11:41 AM, Ragunathan P. wrote:

> > #=
> 
> puts output

This is O(n^2).

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

Ray

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