Interview Question: Replacing two arrays's place in memory

Given two consecutive arrays, A and B. They look something like

int AandB[] = {a1,a2,...,am,b1,b2,...,bn};

You need to write a program that would switch the order of arrays A and B in the memory, so that B would appear before A. In our example, AandB should become

int AandB[] = {b1,b2,...,bn,a1,...,am};

What's the most efficient way to do that?

Three array reverses:

(a1 a2 a3 a4 a5 b1 b2 b3)
 b3 b2 b1 a5 a4 a3 a2 a1
(b3 b2 b1)a5 a4 a3 a2 a1
 b1 b2 b3 a5 a4 a3 a2 a1
 b1 b2 b3(a5 a4 a3 a2 a1)
 b1 b2 b3 a1 a2 a3 a4 a5

Expressed using a "rev" function that takes a start and end:

rev(AandB, 0, n+m)
rev(AandB, 0, m)
rev(AandB, m, n)

For rev (omitting types, etc. for clarity):

rev(x, i, j) {
    j--; // j points to one after the subarray we're reversing
    while (i < j) {
        tmp = x[i];
        x[i] = x[j];
        x[j] = tmp;
        i++;
        j--;
    }
}

My answer:

First, I'm assuming wlog that m<n.

Since every permutation can be decomposed into disjoint cycles, so can the permutation which takes a1,...,am,b1,..,bn to b1,..,bn,a1,...,am. And since given an index i, it is easy to calculate p(i) (assume wlog that m<n, then if i<=m, we have p(i)=n+i, if i>m we have p(i)=i-m).

We can start with AandB[i] and move its value to p(i)=j, then, take the value in AandB[j] and move it to p(j), etc. Since permutations can be decompose into disjoint cycles, we'll end up in i.

We only need to keep track of which elements did we already move. It is possible to prove that in our case, no cycle in the permutation will contain two consecutive elements of A, so I think it is enough to keep track of how many elements of A have we ordered.

Another simple option which is not as efficient is to note that given {a1,...,am,b1,...bn}, it is possible to replace a1..am with b(n-m)..b(n), getting {b(n-m)...b(n),b(1)..b(m),a1..am}. And now by recursion, solve the same problem for the first n elements of your array. But this is probably not so efficient.

There are some more details which I omitted, but anyhow the interviewer told me that it's not the way to go, and there's some very clever solution that is also very simple.

The transformation you want to do is essentially a circular shift by n (or by m, depending on the direction of the shift).

E.g., we have 1 2 3 4 5 6 7 a b c (I use letters and numbers to separate two arrays) During this transformation, 1 will move to the position of 4, 4 will move to 7, 7 to c, c to 3, 3 to 6, etc. Eventually, we'll return to the position 1, from which started.
So, moving one number at the time, we completed it.

The only trick is that sometimes we'll return to 1 before completing whole transformation. Like in the case 1 2 a b c d, the positions will be 1 -> a -> c -> 1. In this case, we'll need to start from 2 and repeat operation.

You can notice that amount of repetitions we need is a greatest common divisor of n and m.

So, the code could look like

int repetitions = GCD(n, m);
int size = n + m;
for (int i = 0; i < repetitions; ++i) {
    int current_number = a[i];

    int j = i;
    do {
        j = (j + n) % size;

        int tmp = current_number;
        current_number = a[j];
        a[j] = tmp;
    } while (j != i);
}

Greatest common divisor can be easily computed in O(logn) with well-known recursive formula.

edit
It does work, I tried in Java. I only changed data type to string for ease of representation.

    String[] a = {"1", "2", "3", "4", "5", "6", "a", "b", "c"};
    int n = 3;
    int m = 6;

    // code from above...

    System.out.println(Arrays.toString(a));

And Euclid's formula:

int GCD(int a, int b) {
    if (a == 0) {
        return b;
    }
    return GCD(b % a, a);
}

Well, thinking while typing here...

I'm assuming by "in memory" you can't cheat by creating one or more new arrays, even as temporaries. I will also assume that you can have a single temporary variable (otherwise swapping contents would get really tricky).

It looks like your two sub-arrays can be different sizes, so you can't just swap a1 with b1 and a2 with b2, etc.

So you need to figure out where the "a" array elements will start first. You do that by finding "n". Then you'd have to repeatedly save the first remaining "a" element, and put the first remaining "b" element there.

Now here's where it gets tricky. You need to get the save "a" element into its rightful spot, but that may contain an unswapped element. The easiest thing to do would probably be to just shift up all the remaining elements by one, and put your saved "a" at the end. If you do that repeatedly, you'll end up with everything in the right place. That's a lot of shifting though if the arrays are large.

I believe a slightly more sophisiticated algorithim could just do shifting for the elements in the delta (the first "q" elelments, where "q" is the delta between your array sizes) and only while working in the delta area. After that it would just be simple swaps.

we can use array_merge from php.

use array_splice() first to split these arrays and then use the above function. This is for php.