<p><em><strong>About an O(n) time, O(1) space algorithm for out-shuffle</strong></em></p>
<hr />
<p>Doing an out-shuffle in O(n) time and O(1) space is possible, but it is <em><strong>tough</strong></em>. Not sure why people think it is easy and are suggesting you try something else.</p>
<p>The following paper has an O(n) time and O(1) space solution (though it is for in-shuffle, doing in-shuffle makes out-shuffle trivial):</p>
<p><a href="http://arxiv.org/PS_cache/arxiv/pdf/0805/0805.1598v1.pdf" rel="nofollow noreferrer">http://arxiv.org/PS_cache/arxiv/pdf/0805/0805.1598v1.pdf</a></p>
<br/>
<p><em><strong>About a method to tackle in-place array modification algorithms</strong></em></p>
<hr />
<p>In-place modification algorithms could become very <em>hard</em> to handle.</p>
<p>Consider a couple:</p>
<ul>
<li>Inplace out-shuffle in linear time. Uses number theory.</li>
<li>In-place merge sort, was open for a few years. An algorithm came but was too complicated to be practical. Uses very complicated bookkeeping.</li>
</ul>
<p>Sorry, if this sounds discouraging, but there is no magic elixir that will solve all in-place algorithm problems for you. You need to work with the problem, figure out its properties, and try to exploit them (as is the case with most algorithms).</p>
<p>That said, for array modifications where the result is a <em>permutation</em> of the original array, you can try the method of <strong>following the cycles of the permutation</strong>. Basically, any permutation can be written as a disjoint set of cycles (see John's answer too). For instance the permutation:</p>
<pre><code>1 4 2 5 3 6
</code></pre>
<p>of <code>1 2 3 4 5 6</code> can be written as</p>
<pre><code>1 -&gt; 1
2 -&gt; 3 -&gt; 5 -&gt; 4 -&gt; 2
6 -&gt; 6.
</code></pre>
<p>you can read the arrow as 'goes to'.</p>
<p>So to permute the array <code>1 2 3 4 5 6</code> you follow the three cycles:</p>
<p>1 goes to 1.</p>
<p>6 goes to 6.</p>
<p>2 goes to 3, 3 goes to 5, 5 goes to 4, and 4 goes to 2.</p>
<p>To follow this long cycle, you can use just one <code>temp</code> variable. Store 3 in it. Put 2 where 3 was.  Now put 3 in 5 and store 5 in the <code>temp</code> and so on. Since you only use constant extra <code>temp</code> space to follow a particular cycle, you are doing an in-place modification of the array for that cycle.</p>
<p>Now if I gave you a formula for computing where an element goes to, all you now need is the set of starting elements of each cycle.</p>
<p>A judicious choice of the starting points of the cycles can make the algorithm easy. If you come up with the starting points in O(1) space, you now have a complete in-place algorithm. This is where you might actually have to get familiar with the problem and exploit its properties.</p>
<p>Even if you didn't know how to compute the starting points of the cycles, but had a formula to compute the next element, you could use this method to get an O(n) time in-place algorithm in some special cases.</p>
<p>For instance: if you knew the array of unsigned integers held only positive integers.</p>
<p>You can now follow the cycles, but negate the numbers in them as an indicator of 'visited' elements. Now you can walk the array and pick the first positive number you come across and follow the cycles for that, making the elements of the cycle negative and continue to find untouched elements. In the end, you just make all the elements positive again to get the resulting permutation.</p>
<p>You get an O(n) time and O(1) space algorithm! Of course, we kind of 'cheated' by using the sign bits of the array integers as our personal 'visited' bitmap.</p>
<p>Even if the array was not necessarily integers, this method (of following the cycles, not the hack of sign bits :-)) can actually be used to tackle the two problems you state:</p>
<ul>
<li><p><code>The in-shuffle (or out-shuffle) problem</code>: When <code>2n+1</code> is a power of <code>3</code>, it can be shown (using number theory) that <code>1,3,3^2,</code> etc are in different cycles and all cycles are covered using those. Combine this with the fact that the in-shuffle is susceptible to divide and conquer, you get an O(n) time, O(1) space algorithm (the formula is <code>i -&gt; 2*i modulo 2n+1</code>). Refer to the above paper for more details.</p>
</li>
<li><p><code>The cyclic shift an array problem</code>: Cyclic shift an array of size <code>n</code> by <code>k</code> also gives a permutation of the resulting array (given by the formula <code>i</code> goes to <code>i+k modulo n</code>), and can also be solved in linear time and in-place using the following the cycle method. In fact, in terms of the number of element exchanges this following cycle method is <em>better</em> than the 3 reverses algorithm. Of course, following the cycle method can kill the cache because of the access patterns, and in practice, the 3 reverses algorithm might actually fare better.</p>
</li>
</ul>
<hr />
<p>As for interviews, if the interviewer is a reasonable person, they will be looking at how you <em>think</em> and approach the problem and not whether you actually solve it. So even if you don't solve a problem, I think you should not be discouraged.</p>
How to master in-place array modification algorithms?
<p>I am preparing for a software job interview, and I am having trouble with in-place array modifications.</p>
<p>For example, in the out-shuffle problem you interleave two halves of an array so that <code>1 2 3 4 5 6 7 8</code> would become <code>1 5 2 6 3 7 4 8</code>. <a href="http://www.careercup.com/question?id=3002" rel="nofollow noreferrer">This question</a> asks for a constant-memory solution (and linear-time, although I'm not sure that's even possible).</p>
<p>First I thought a linear algorithm is trivial, but then I couldn't work it out. Then I did find a simple <code>O(n^2)</code> algorithm but it took me a long time. And I still don't find a faster solution.</p>
<p>I remember also having trouble solving a similar problem from Bentley's Programming Pearls, column 2:</p>
<blockquote>
<p>Rotate an array left by <code>i</code> positions (e.g. <code>abcde</code> rotated by 2 becomes <code>cdeab</code>), in time <code>O(n)</code> and with just a couple of bytes extra space.</p>
</blockquote>
<p>Does anyone have tips to help wrap my head around such problems?</p>