From: "Michael T. Richter" Date: 2008-06-20T22:18:40+09:00 Subject: Re: little problem (google hiring puzzle) --=-IC/XFjZa4EOxAARoG4RW Content-Type: multipart/alternative; boundary="=-Z0O6jz6nMe7tK2g+BttJ" --=-Z0O6jz6nMe7tK2g+BttJ Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: quoted-printable On Fri, 2008-06-20 at 16:59 +0900, Pe=C3=B1a, Botp wrote: > From: ex [mailto:exeQtor@gmail.com]=20 > # ################## > # There is an array A[N] of N integers. You have to=20 > # compose an array > # Output[N] such that Output[i] will be equal to the=20 > # product of all the elements of A[] except A[i]. > #=20 > # Example: > # INPUT:[4, 3, 2, 1, 2] > # OUTPUT:[12, 16, 24, 48, 24] > #=20 > # Note: Solve it without the division operator and in O(n). > # =3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D= =3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D= =3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D >=20 >=20 > it's friday here, so i guess i'll just join the fun :) >=20 > how about, >=20 > prod=3D lambda{|a| a.inject(1){|p,x| p*x}} > =3D> # >=20 > a=3D[4,3,2,1,2] > =3D> [4, 3, 2, 1, 2] >=20 > pa=3D[] > =3D> [] >=20 > s=3Da.size > =3D> 5 >=20 > s2=3Ds-1 > =3D> 4 >=20 > # 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) >=20 > a2=3Da+a > =3D> [4, 3, 2, 1, 2, 4, 3, 2, 1, 2] >=20 > 1.upto(s) do |i| > pa << prod.call(a2[i,s2]) > end > =3D> 1 >=20 > p pa > [12, 16, 24, 48, 24] > =3D> nil >=20 > can i pass google? =3D) >=20 > 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). --=20 Michael T. Richter (GoogleTalk: ttmrichter@gmail.com) I have to wonder why people think that when they can't manage local personnel within easy strangling and shooting distance, then they can manage personnel thousands of miles away that have different languages, cultures, and business rules. (Joe Celko) --=-Z0O6jz6nMe7tK2g+BttJ Content-Type: text/html; charset=utf-8 Content-Transfer-Encoding: quoted-printable On Fri, 2008-06-20 at 16:59 +0900, Peña, Botp wrote:

From: ex [mail=
to:exeQtor@gmail.com] 
# ##################
# 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 th=
e 
# 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).
# =3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=
=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=
=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D


it's friday here, so i guess i'll just join the fun=
 :)

how about,

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

a=3D[4,3,2,1,2]
=3D> [4, 3, 2, 1, 2]

pa=3D[]
=3D> []

s=3Da.size
=3D> 5

s2=3Ds-1
=3D> 4

# here is the meat:
# i just concat orig array so i don't need to rotat=
e
# then get subarrays in groups of s2 (a.size-1)

a2=3Da+a
=3D> [4, 3, 2, 1, 2, 4, 3, 2, 1, 2]

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

p pa
[12, 16, 24, 48, 24]
=3D> nil

can i pass google? =3D)

kind regards -botp

Eyeballing this looks to me like it's O(n^2). You're iterating over t= he list (1.upto(s)) and on each iteration you're iterating over the list (i= nject).

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 d= oesn't increase roughly by an order of magnitude each time through and inst= ead shoots through the roof, you're not doing O(n).

--
Michael T. Richter <ttmri= chter@gmail.com> (GoogleTalk: ttmrichter@gmail.com)
I have to wonder why people think that when they can't manage local pers= onnel within easy strangling and shooting distance, then they can manage pe= rsonnel thousands of miles away that have different languages, cultures, an= d business rules. (Joe Celko)

--=-Z0O6jz6nMe7tK2g+BttJ-- --=-IC/XFjZa4EOxAARoG4RW Content-Type: application/pgp-signature; name=signature.asc Content-Description: This is a digitally signed message part -----BEGIN PGP SIGNATURE----- Version: GnuPG v1.4.6 (GNU/Linux) iD8DBQBIW65+LqyWkKVQ54QRAssrAKCCYsV81d0108bp/nrMFQI6/4sdlwCdG5xK 2Wz3HRyV5IQvQWgUCdI1ddA= =2ufd -----END PGP SIGNATURE----- --=-IC/XFjZa4EOxAARoG4RW--