How to master in-place array modification algorithms?

I am preparing for a software job interview, and I am having trouble with in-place array modifications.

For example, in the out-shuffle problem you interleave two halves of an array so that 1 2 3 4 5 6 7 8 would become 1 5 2 6 3 7 4 8. This question asks for a constant-memory solution (and linear-time, although I'm not sure that's ev开发者_高级运维en possible).

First I thought a linear algorithm is trivial, but then I couldn't work it out. Then I did find a simple O(n^2) algorithm but it took me a long time. And I still don't find a faster solution.

I remember also having trouble solving a similar problem from Bentley's Programming Pearls, column 2:

Rotate an array left by i positions (e.g. abcde rotated by 2 becomes cdeab), in time O(n) and with just a couple of bytes extra space.

Does anyone have tips to help wrap my head around such problems?

About an O(n) time, O(1) space algorithm for out-shuffle

Doing an out-shuffle in O(n) time and O(1) space is possible, but it is tough. Not sure why people think it is easy and are suggesting you try something else.

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

http://arxiv.org/PS_cache/arxiv/pdf/0805/0805.1598v1.pdf

About a method to tackle in-place array modification algorithms

In-place modification algorithms could become very hard to handle.

Consider a couple:

• Inplace out-shuffle in linear time. Uses number theory.
• In-place merge sort, was open for a few years. An algorithm came but was too complicated to be practical. Uses very complicated bookkeeping.

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

That said, for array modifications where the result is a permutation of the original array, you can try the method of following the cycles of the permutation. Basically, any permutation can be written as a disjoint set of cycles (see John's answer too). For instance the permutation:

1 4 2 5 3 6

of 1 2 3 4 5 6 can be written as

1 -> 1
2 -> 3 -> 5 -> 4 -> 2
6 -> 6.

you can read the arrow as 'goes to'.

So to permute the array 1 2 3 4 5 6 you follow the three cycles:

1 goes to 1.

6 goes to 6.

2 goes to 3, 3 goes to 5, 5 goes to 4, and 4 goes to 2.

To follow this long cycle, you can use just one temp variable. Store 3 in it. Put 2 where 3 was. Now put 3 in 5 and store 5 in the temp and so on. Since you only use constant extra temp space to follow a particular cycle, you are doing an in-place modification of the array for that cycle.

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.

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.

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.

For instance: if you knew the array of unsigned integers held only positive integers.

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.

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.

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:

• The in-shuffle (or out-shuffle) problem: When 2n+1 is a power of 3, it can be shown (using number theory) that 1,3,3^2, 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 i -> 2*i modulo 2n+1). Refer to the above paper for more details.

• The cyclic shift an array problem: Cyclic shift an array of size n by k also gives a permutation of the resulting array (given by the formula i goes to i+k modulo n), 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 better 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.

As for interviews, if the interviewer is a reasonable person, they will be looking at how you think 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.

The basic strategy with in place algorithms is to figure out the rule for moving a entry from slot N to slot M.

So, your shuffle, for instance. if A and B are cards and N is the number of chards. the rules for the first half of the deck are different than the rules for the second half of the deck

 // A is the current location, B is the new location.
 // this math assumes that the first card is card 0
 if (A < N/2)
    B = A * 2;
 else
    B = (A - N/2) * 2 + 1;

Now we know the rule, we just have to move each card, each time we move a card, we calculate the new location, then remove the card that is currently in B. place A in slot B, then let B be A, and loop back to the top of the algorithm. Each card moved displaces the new card which becomes the next card to be moved.

I think the analysis is easier if we are 0 based rather than 1 based, so

 0 1 2 3 4 5 6 7  // before
 0 4 1 5 2 6 3 7  // after

So we want to move 1->2 2->4 4->1 and that completes a cycle then move 3->6 6->5 5->3 and that completes a cycle and we are done.

Now we know that card 0 and card N-1 don't move, so we can ignore those, so we know that we only need to swap N-2 cards in total. The only sticky bit is that there are 2 cycles, 1,2,4,1 and 3,6,5,3. when we get to card 1 the second time, we need to move on to card 3.

 int A = 1;
 int N = 8;
 card ary[N]; // Our array of cards
 card a = ary[A];

 for (int i = 0; i < N/2; ++i)
 {
     if (A < N/2)
        B = A * 2;
     else
        B = (A - N/2) * 2 + 1;

     card b = ary[B];
     ary[B] = a;
     a = b;
     A = B;

     if (A == 1)
     {
        A = 3;
        a = ary[A];
     }
 }   

Now this code only works for the 8 card example, because of that if test that moves us from 1 to 3 when we finish the first cycle. What we really need is a general rule to recognize the end of the cycle, and where to go to start the next one.

That rule could be mathematical if you can think of a way, or you could keep track of which places you had visited in a separate array, and when A is back to a visited place, you could then scan forward in your array looking for the first non-visited place.

For your in-place algorithm to be 0(n), the solution will need to be mathematical.

I hope this breakdown of the thinking process is helpful to you. If I was interviewing you, I would expect to see something like this on the whiteboard.

Note: As Moron points out, this doesn't work for all values of N, it's just an example of the sort of analysis that an interviewer is looking for.

Frank,

For programming with loops and arrays, nothing beats David Gries's textbook The Science of Programming. I studied it over 20 years ago, and there are ideas that I still use every day. It is very mathematical and will require real effort to master, but that effort will repay you many times over for your whole career.

Complementing Aryabhatta's answer:

There is a general method to "follow the cycles" even without knowing the starting positions for each cycle or using memory to know visited cycles. This is specially useful if you need O(1) memory.

For each position i in the array, follow the cycle without moving any data yet, until you reach...

• the starting position i: end of the cyle. this is a new cycle: follow it again moving the data this time.
• a position lower than i: this cycle was already visited, nothing to do with it.

Of course this has a time overhead (O(n^2), I believe) and has the cache problems of the general "following cycles" method.

For the first one, let's assume n is even. You have:

first half: 1 2 3 4
second : 5 6 7 8

Let x1 = first[1], x2 = second[1].

Now, you have to print one from the first half, one from the second, one from the first, one from the second...

Meaning first[1], second[1], first[2], second[2], ...
Obviously, you don't keep two halves in memory, as that will be O(n) memory. You keep pointers to the two halves. Do you see how you'd do that?

The second is a bit harder. Consider:

12345
abcde
..cde
.....ab
..cdeab
cdeab

Do you notice anything? You should notice that the question basically asks you to move the first i characters to the end of your string, without affording the luxury of copying the last n - i in a buffer then appending the first i and then returning the buffer. You need to do with O(1) memory.

To figure how to do this you basically need a lot of practice with these kinds of problems, as with anything else. Practice makes perfect basically. If you've never done these kinds of problems before, it's unlikely you'll figure it out. If you have, then you have to think about how you can manipulate the substrings and or indices such that you solve your problem under the given constraints. The general rule is to work and learn as much as possible so you'll figure out the solutions to these problems very fast when you see them. But the solution differs quite a bit from problem to problem. There's no clear recipe for success I'm afraid. Just read a lot and understand the stuff you read before you move on.

The logic for the second problem is this: what happens if we reverse the substring [1, 2], the substring [3, 5] and then concatenate them and reverse that? We have, in general:

1, 2, 3, 4, ..., i, i + 1, i + 2, ..., N

reverse [1, i] =>
i, i - 1, ..., 4, 3, 2, 1, i + 1, i + 2, ..., N

reverse [i + 1, N] =>
i, i - 1, ..., 4, 3, 2, 1, N, ..., i + 1

reverse [1, N] =>
i + 1, ..., N, 1, 2, 3, 4, ..., i - 1, i

which is what you wanted. Writing the reverse function using O(1) memory should be trivial.

Generally speaking, the idea is to loop through the array once, while

• storing the value at the position you are at in a temporary variable
• finding the correct value for that position and writing it
• either move on to the next value, or figure out what to do with your temporary value before continuing.

A general approach could be as follows:

1. Construct a positions array int[] pos, such that pos[i] refers to the position (index) of a[i] in the shuffled array.

2. Rearrange the original array int[] a, according to this positions array pos.

   /** Shuffle the array a. */    
   void shuffle(int[] a) {
       // Step 1
       int [] pos = contructRearrangementArray(a)
       // Step 2
       rearrange(a, pos);
   }
   
   /**
    * Rearrange the given array a according to the positions array pos.
    */
   private static void rearrange(int[] a, int[] pos)
   {
       //  By definition 'pos' should not contain any duplicates, otherwise rearrange() can run forever.
      // Do the above sanity check.
       for (int i = 0; i < pos.length; i++) {
           while (i != pos[i]) {
               // This while loop completes one cycle in the array
               swap(a, i, pos[i]);
               swap(pos, i, pos[i]);
           }
       }
   }
   
   /** Swap ith element in a with jth element. */
   public static void swap(int[] a, int i, int j) 
   {
       int temp = a[i];
       a[i] = a[j];
       a[j] = temp;
   }
   

As an example, for the case of outShuffle the following would be an implementation of contructRearrangementArray().

/**
 * array     : 1 2 3 4 5 6 7 8
 * pos       : 0 2 4 6 1 3 5 7
 * outshuffle: 1 5 2 6 3 7 4 8 (outer boundaries remain same)
 */
public int[] contructRearrangementArray(int[] a)
{
    if (a.length % 2 != 0) {
        throw new IllegalArgumentException("Cannot outshuffle odd sized array");
    }
    int[] pos = new int[a.length];
    for (int i = 0; i < pos.length; i++) {
        pos[i] = i * 2 % (pos.length - 1);
    }
    pos[a.length - 1] = a.length - 1;
    return pos;
}