[lnkForumImage]
TotalShareware - Download Free Software
Confronta i prezzi di migliaia di prodotti.
Asp Forum
 Home | Login | Register | Search 


 

Forums >

comp.lang.ruby

little problem (google hiring puzzle

ex

6/15/2008 5:00:00 PM

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
41 Answers

Dave Thomas

6/15/2008 5:27:00 PM

0

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


On Jun 15, 2008, at 11:59 AM, 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):
>
> ################################################################################
> # 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
>
>
>

Tor Erik Linnerud

6/15/2008 5:33:00 PM

0


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
--
Posted via http://www.ruby-....

Rick DeNatale

6/15/2008 5:45:00 PM

0

[Note: parts of this message were removed to make it a legal post.]

On Sun, Jun 15, 2008 at 1:26 PM, Dave Thomas <dave@pragprog.com> 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.denh...

Eric I.

6/15/2008 5:46:00 PM

0

On Jun 15, 12:59 pm, ex <exeQ...@gmail.com> 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 offers Rails & Ruby HANDS-ON public & ON-SITE
workshops.
Ruby Fundamentals Workshop June 16-18 Ann Arbor, Mich.
Ready for Rails Ruby 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://Lea... for all the details.

Robert Dober

6/15/2008 6:48:00 PM

0

On Sun, Jun 15, 2008 at 6:59 PM, ex <exeQtor@gmail.com> 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.blo...

---
As simple as possible, but not simpler.
Albert Einstein

ThoML

6/15/2008 6:53:00 PM

0

See also:

http://www.reddit.com/got...
http://rant.blackapache.net/2008/06/14/an-interesting-littl...
http://www.fsharp.it/2008/06/10/google-interview-question-product-of-other-elements-in-an-ar...
Haskell: http://pastie.textmate....

Dave Thomas

6/15/2008 7:13:00 PM

0


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

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

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.

Rick DeNatale

6/15/2008 8:00:00 PM

0

[Note: parts of this message were removed to make it a legal post.]

On Sun, Jun 15, 2008 at 2:48 PM, Robert Dober <robert.dober@gmail.com>
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.denh...

ThoML

6/15/2008 8:28:00 PM

0

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

Dave Thomas

6/15/2008 9:00:00 PM

0


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