Re: Array Programming Questions

On Wed, 25 May 2005 22:28:14 -0400, William
<wh2leung@xxxxxxxxxxxxxxxxxxxxxxx> wrote:

> I would appreciate your help on the following sample Microsoft interview
>questions:
>
>1. Given an array of length N containing integers between 1 and N,
>determine if it contains any duplicates.
>HINT: [Is there an O(n) time solution that uses only O(1) extra space and
>does not destroy the original array?]
>
>The solution is:
>http://domino.research.ibm.com/Comm/wwwr_ponder.nsf/solutions/January2004.html
>
>but I don't understand what they meant by "Let f(x) be the location of the
>array at address x."

This is a late followup. The rho algorithm works like this: Suppose
we have a successor function that defines a sequence that ends in a
cycle. The object is to find the beginning of the cycle in the
sequence. For example:

a0->a1->a2->a3->a4->a5->a6->a3

The sequence has two parts, a tail (a0->a1->a2) that is not part of
the cycle, and the cycle proper (a3->a4->a5->a6). Let m be the length
of the tail and n be the length of the cycle proper. In our example
m=3 and n=4.

Now we start two sequences, one using single steps and one using
double steps. When the first sequence takes m steps it arrives at the
entry point into the cycle, and the second sequence has moved m points
beyond the entry point. When the first sequence moves n-m steps from
the entry point the second moves 2(n-m) from m points past the entry
point. Both are then at the same point in the cycle, namely m points
before the entry points. Call this point the intersection point.

We now do two single step sequences, one from the original starting
point, and one from the intersection point. In m steps both arrive at
the entry point.


Richard Harter, cri@xxxxxxxx
http://home.tiac.net/~cri, http://www.varinoma.com
Save the Earth now!!
It's the only planet with chocolate.
.

Relevant Pages

  • Re: Proof of Collatz Conjecture?
    ... sequence Cn has a length-3 cycle because there is always one ... any sequence or the cycle. ... print 'PART II: Count legal sequences using partition generator:' ...
    (sci.math)
  • Re: The code of co-workers
    ... -all of the pointers have to be valid (dereferencing an invalid pointer ... -*i+1 and *j+1 must be valid indices into the array that a points into ... these are modified between the same pair of sequence points (modifying ... To avoid burying any useful diagnostics in useless ones, ...
    (comp.programming)
  • Re: Cohens paper on byte order
    ... > you changed from a bit sequence to what appears to be ... an array of unsigned char to represent a bit array, ... in the reverse order instead? ... But the user input IS at the beginning a bit array ...
    (sci.crypt)
  • Re: Is there a Mathematician Cryptographr in the House.
    ...  > the beginning but the array is read only once in entirety. ... posts IMHO. ... Partners agree to employ a publically available character sequence ... All of it since S1 is in essence SR1 after scrambling and has to be ...
    (sci.crypt)
  • Re: Check for Common character sequence ( I will pay)?
    ... Yes you are returning an array of FoundString objects. ... in more than one string. ... This means that you have to identify sequences 1 character at a time, ... Again, obviously, if the 3-character sequence doesn't match, neither will ...
    (microsoft.public.dotnet.framework)