From: Rick DeNatale <rick.denatale@...>
Date: 2008-06-20T02:15:59+09:00
Subject: Re: little problem (google hiring puzzle)

------=_Part_12814_18989993.1213895840369
Content-Type: text/plain; charset=ISO-8859-1
Content-Transfer-Encoding: 7bit
Content-Disposition: inline

On Thu, Jun 19, 2008 at 12:12 PM, Ragunathan Pattabiraman <
ragunathan.pattabiraman@gmail.com> 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


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/

------=_Part_12814_18989993.1213895840369--