Interview test - rearrange the array [duplicate]

Question

Possible Duplicate:
Reordering of array elements

In given array of elements like [a1,a2,a3,..an,b1,b2,b3,..bn,c1,c2,c3,...cn] Write a program to merge them like [a1,b1,c1,a2,b2,c2,...an,bn,cn]. We have to do it in O(1) extra space.

Sample Testcases:

Input #00:

{1,2,3,4,5,6,7,8,9,10,11,12}

Output #00:

{1,5,9,2,6,10,3,7,11,4,8,12}

Explanation:

Here as you can notice, the array is of the form
{a1,a2,a3,a4,b1,b2,b3,b4,c1,c2,c3,c4} 

EDIT: I got it in Amazon placement test. Have been trying it for a long time. PLease provide psuedo code. What i tried is finding new position p for second element e(1st is already at correct position), inserting e at p and repeating the same for the old element at position p. But this is ending in a cycle. I tried detecting cycle and incrementing the starting position by 1. But even this is not working.

EDIT2:

#include <iostream>
using namespace std;

int pos(int i, int n) 
{
    if(i<n)  
     {
         return  3*i;

           }

       else if(i>=n && i<2*n)
       {

            return 3*(i-n) + 1;
            }
    else if(i>=2*n && i<3*n)
       {
            return 3*(i-2*n) + 2;
            }
return -1;
}
void printn(int* A, int n)
{
         for(int i=0;i<3*n;i++)  
             cout << A[i]<<";";

    cout << endl;
     }

void merge(int A[], int n)
{
 int j=1;    
 int k =-1;
 int oldAj = A[1];
 int count = 0;
 int temp;
 while(count<3*n-1){

 printn(A,n);
 k = pos(j,n);
 temp = A[k];
 A[k] = oldAj;
 oldAj = temp;
 j = k;
 count++;
 if(j==1) {j++;}
}

 }

int main()
{
    int A[21] = {1,4,7,10,13,16,19,2,5,8,11,14,17,20,3,6,9,12,15,18,21};
    merge(A,7);

    cin.get();}

Answer 1

This is the so called in-place in-shuffle algorithm, and it's an extremely hard task if you want to do it efficiently. I'm just posting this entry so people don't post their so called "solutions" claiming that it can be extended to work with O(1) space, without any proof...

Here is a paper for a simpler case when the list is in the form: a1 a2 a3 ... an b1 b2 b3 .. bn:

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

Answer 2

Here's is a description of an algorithm with 3 elements of extra space and O(n^2) complexity:

sa, sb, sc are, respectively, next source index for a, b and c sequences. d is the copy destination index.

On each iterarion:

• Copy elements at sa, sb and sc to temporary storage

• Shift the array elements to the left to fill in the now vacant indices sa, sb and sc

• This leaves three empty positions at d

• Copy the three elements from temporary storage to empty positions.

Example (dots indicate "empty" positions):

First iteration:
 copy to tmp: ., 2, 3, 4,  ., 6, 7, 8,   .,10,11,12
              1            5             9
 shift:       ., ., ., 2,  3, 4, 6, 7,   8,10,11,12
 copy to dst: 1, 5, 9, 2,  3, 4, 6, 7,   8,10,11,12

Second iteration:
copy to tmp: 1, 5, 9, .,   3, 4, ., 7,   8, .,11,12
                      2          6         10
shift:       1, 5, 9, .,   ., ., 3, 4,   7, 8,11,12
copy to dst: 1, 5, 9, 2,   6,10, 3, 4,   7, 8,11,12

Third iteration:
copy to tmp: 1, 5, 9, 2,   6,10, ., 4,   ., 8, .,12
                                 3       7    11 
shift:       1, 5, 9, 2,   6,10, ., .,   ., 4, 8,12
copy to dst: 1, 5, 9, 2,   6,10, 3,  7  11, 4, 8,12

EDIT:

And here's a working program (it takes a bit more than a verbal description :)))

#include <stdio.h>

#define N 4

int a[] = {1, 2,3, 4, 5, 6, 7, 8, 9, 10, 11, 12};

void
rearrange ()
{
  int i;
  int d;
  int sa, sb, sc;
  int tmp [3];

  d = 0;
  sa = 0;
  sb = sa + N;
  sc = sb + N;

  while (sc < N*3)
    {
      /* Copy out.  */
      tmp [0] = a [sa];
      tmp [1] = a [sb];
      tmp [2] = a [sc];

      /* Shift  */
      for (i = sc; i > sb + 1; --i)
        a [i] = a [i - 1];

      for (i = sb + 1; i > sa + 2; --i)
        a [i] = a [i - 2];

      sa += 3;
      sb += 2;
      sc++;

      /* Copy in.  */
      a [d++] = tmp [0];
      a [d++] = tmp [1];
      a [d++] = tmp [2];
    }
}

int
main ()
{
  int i;
  rearrange ();

  for (i = 0; i < N*3; ++i)
    printf ("%d\n", a [i]);
  putchar ('\n');
  return 0;
}

Appears to work. shrug