Q.1) Given an array of size 2N such that 1st N elements are odd and remaining N elements are even. Update this array such that after 1st odd number, 1st even number will come, then 2nd odd number and then 2nd even number and so on.

So if input array is { 1, 3, 5, 7, 2, 4, 6, 8}

Output array will be {1, 2, 3, 4, 5, 6, 7, 8}

Ans)

If we can use extra memory, we can easily achieve this in O(n) but problem to achieve O(n) without using extra space.

Approach #1
-------------
The new position of an element can be obtained as follows:
new index = (2*old index)%N where N is the final index(Num of elements - 1)

Sample code
arrange(int[] a, int N) {
    int count = 0, i=1, temp = 0;
    if (N >= 1) {
           temp = a[1];
    }
    while (count < (N-1)) {//To keep track of num of rearranges which is N-1 in total
         swap(temp, a[(2*i)%N]);
         i = (2*i)%N;
         count++;
    }
}

Approach #2
--------------
You can refer different approaches in the below link
http://dailyjobquestions.com/2011/10/16/divide-and-conquer/

Q.2) Now, an extension to above question.
Convert an array "a1 a2 a3.. an b1 b2 b3 .. bn c1 c2 c3 ... cn" to "a1 b1 c1 a2 b2 c2 ... an bn cn" in place.

Apporach #1
--------------
Above approach of finding final position and swapping will work good in this one also. Only difference is final position need to be calculate as i = (3*i)%N

Approach #2
--------------

Refer this link for some good questions including this one

Explanation from above link

Solution:we divide the array in four sections:[X,Y|A,B]
It is easy to see that with swaps we can modify it to the form [X,A|Y,B].
Now do recursion to solve [X|A] and [Y|B] separately,essentially using divide and conquer.[as given in comments section]

For example:
{ 1,2,3,4,5,6,7,8,a,b,c,d,e,f,g,h }
X = { 1,2,3,4 }, Y = { 5,6,7,8 }, A = { a,b,c,d }, B = {e,f,g,h}

{ 1,2,3,4,a,b,c,d,5,6,7,8,e,f,g,h }

[X|A] = {1,2,3,4,a,b,c,d }

U = { 1,2 }, V = {3,4}, W = {a,b}, Z = {c,d}
swap V and W:
[U,W|V,Z] = { 1,2,a,b,3,4,c,d }

[U|W] = { 1,2,a,b }
swap 2 and a:
{ 1,a,2,b }
=======================
Based on that solution, we can naively solve our problem as follows:
First, convert it to a1, b1, a2, b2, ..., an, bn, c1, c2, ..., cn

Next, convert the new array to the desired form a1, b1, c1, a2, b2, c2, ..., an, bn, cn by considering (a1, b1) as A1, ... (an, bn) as An