## Microsoft Interview Question

Software Engineer / DevelopersBy working on a few examples I realized that the if(i == start) part of the above code is executed only for odd values of 'n'.

For odd values of 'n' say n=11, the sequence of movements that we have are:

1 - 2 - 4 - 8 - 16 - 11 - 1

3 - 6 - 12 - 3

5 - 10 - 20 - 19 - 17 - 13 - 5

7 - 14 - 7

9 - 18 - 15 - 9

Each of these sequences have only one ascent. While for even values of n, say n = 10, the sequence is:

1 - 2 - 4 - 8 - 16 - 13 - 7 - 14 - 9 - 18 - 17 - 15 - 11 - 3 - 6 - 12 - 5 - 10 - 1

Here the number of elements cannot be odd since its given that a goes from 1 to n. and b also goes from 1 to n . Even if a and b individually have odd number of elements , they still would total up to even in the final array.

I am not sure if I am missing something here? This looks like a simple problem. I wrote following code for the same.

DWORD MergeArrays(int *Arr1, int *Arr2, int Len)

{

//Assumption Arr1 length is equal to 2 * Len. If not need to reallocate the memory

int i, j;

for(i = (2*Len - 1), j = Len - 1; i >= 0, j >= 0; i--, j--)

{

Arr1[i--] = Arr2[j];

Arr1[i] = Arr1[j];

}

return 0;

}

Am I missing something here? I thought following would be the simplest code to solve this

```
DWORD MergeArrays(int *Arr1, int *Arr2, int Len)
{
//Assumption Arr1 length is equal to 2 * Len. If not need to reallocate the memory
int i, j;
for(i = (2*Len - 1), j = Len - 1; i >= 0, j >= 0; i--, j--)
{
Arr1[i--] = Arr2[j];
Arr1[i] = Arr1[j];
}
return 0;
}
```

Am I missing something here? I thought following would be the simplest code to solve this

```
DWORD MergeArrays(int *Arr1, int *Arr2, int Len)
{
//Assumption Arr1 length is equal to 2 * Len. If not need to reallocate the memory
int i, j;
for(i = (2*Len - 1), j = Len - 1; i >= 0, j >= 0; i--, j--)
{
Arr1[i--] = Arr2[j];
Arr1[i] = Arr1[j];
}
return 0;
}
```

We need to insert value of middle element of array,immediately after first element.(take the middle element, store it in temp, shift the array to left from second position till middle of array and then insert that value stored in temp as second element of array.

{

t=lower+1; // lower bound of array

mid=size/2; // size= array size

while(mid<n)

{

temp=a[mid];

for(i=mid;i>t;i--)

{

a[i]=a[i-1];

}

a[t]=temp;

t+=2;

mid++;

}

For n = 2m we've the solution :

public static void Reorder(int start, int end)

{

int abslength = end - start + 1;

for (int i = 0; i < abslength; i++)

Console.Write(array[i] + ",");

int thisstart = 0;

for (int span = abslength; span > 2; span = span / 2)

{

for (int i = start; i < end; i = i + span)

{

thisstart = i;

int quart = span / 4;

int mid = span / 2;

swapBlock(thisstart + quart, thisstart + mid, quart);

}

}

}

private static void swapBlock(int start1, int start2, int length)

{

int temp = 0;

int i = start1, j = start2;

for (; i < (start1 + length); i++, j++)

{

Console.WriteLine("Swap "+i+" with "+j);

temp = array[i];

array[i] = array[j];

array[j] = temp;

}

}

Does array a have enough storage to hold 2n values ? if yes the solution seems trivial, run through a from n-1 to 1 and placing the values in slots 2n-1, 2n-3..1 and run through b placing 0 to n in a's 1,3,5..2n

However, the question seems to suggest that array a has only has space for n elements.

Here is one solution.

```
public static int memberOfGroup(int x, int n)
{
int x1 = x;
int groupId = x;
do
{
x = n + (x-1);
while(x%2==0)
{
x = x/2;
}
if(groupId>x)
{
groupId = x;
}
}while(x!=x1);
return groupId;
}
public static int[] reorderArray(int[] a)
{
int n = a.length;
int count = 0;
int i = 1;
while(true)
{
int cur = i;
int next = i;
int temp = a[cur];
do
{
next = (2*cur)/n + (2*cur)%n;
int temp1 = a[next];
a[next] = temp;
temp = temp1;
count++;
cur = next;
}
while(next!=i);
if(count<n-2)
{
do
{
i+=2;
if(memberOfGroup(i, n)==i) break;
}while(true);
}
else
{
break;
}
}
return a;
}
public static int[] createArray(int n)
{
if(n%2==0)
{
int[] a= new int[n];
for(int i=0; i< n/2; i++)
{
a[i] = i;
}
for(int i=n/2; i< n; i++)
{
a[i] = i-(n/2);
}
return a;
}
return null;
}
public static void main(String[] args)
{
int[] a = createArray(128);
a = reorderArray(a);
for(int i=0; i<a.length; i++)
{
System.out.println(a[i]);
}
}
```

I am not sure how to compute the time complexity of this algorithm though

I think I got it:

Notice that element at index i is shifted to the right by 2*i, modulo 2n-1.

Try it first to understand the pseudocode.

Pseudocode:

traverse array from i = index 0 to n

get the new index of i in variable nI

the current index i is also in variable cI

nI = 2*i % (2n -1), cI = i

do

swap values at nI and cI

cI = nI

np = 2*cI % (2n -1)

while nI is not index

#include <iostream>

#include <algorithm>

#include <iterator>

using namespace std;

int main( int argc, char **argv )

{

// array in question

int array[] = { 1, 3, 5, 7, 9, 100, 200, 300, 400, 500 };

// declaration

int init = 1;

int mid = (sizeof( array ) / sizeof( array[0] )) / 2;

int i = init;

int n = mid;

// basic algorithm

while ( init < mid )

{

i = init ++;

while ( i < mid ) swap( array[ i++ ], array[ n++ ] );

n = mid;

}

// displaying

copy( array, array + (mid * 2), ostream_iterator<int>(cout," ") );

cout << endl;

return EXIT_SUCCESS;

}

Hi Solution for this problem is :

Elements of a category are : n

Elements of b category are : n

array size is 2n

1) Go to n+1 postion.

2) Pick this element is toggle it with element at nth position.

3) Now go to nth position and toggle it with element at n-1 position.

4) REPEAT step 2-3 n-1 times.

5) Once done now go to n+2 and repeat steps 2-5 n-2th times.

6) Final array will be a1, b1, a2, b2, a3, b3,...

Code................

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

int nth = 5;

for (int Z = 0; Z <= nth - 2; Z++)

{

for (int j = 0; j < nth - 1 - Z; j++)

{

int temp;

temp = a[nth - j + Z];

a[nth - j + Z] = a[nth - 1 - j + Z];

a[nth - 1 - j + Z] = temp;

}

}

// sorted array a here .

```
void changeArr(int arr[]){
int temp,j=1;
int m=arr.length()/2;
temp=arr[j];
while(j<arr.length()){
arr[j]=arr[m];
m++;j++;
if(j<arr.length()){
int temp1=a[j];
arr[j]=temp;
temp=temp1;
j++;
}
}
}
```

I think this is a trick question. You can only create one blank space while swapping and you need to do shift operation. I dont see any way how this can be done in O(n) & O(1) iteratively. Using recursion, it can be easily solved in this way

// arr - array

// total length of array = 2n

assign(int i, int a, int b)

{

if(i < n)

{

// a = arr[i]; b = arr[n+i];

assign(i + 1, arr[i],arr[n+i]);

}

// overwrite the source array with function arguments

arr[i*2] = a;

arr[i*2 + 1] = b;

}

// to start the operation

assign(0,arr[0],arr[n]);

recursion has an implicit O(n) space complexity. if that is allowed, then this is the correct answer

works prefectly.....

#include<iostream>

using namespace std;

void print(int arr[], int start,int end)

{

for(int i=start;i<=end;i++)

{

cout<<arr[i]<<" ";

}

cout<<endl;

}

void swap(int &x,int &y)

{

int temp=x;

x=y;

y=temp;

}

void corr_arr(int arr[], int start, int end)

{

int new_end=end;

if((end-start)%2!=0)

{

new_end=end-1;

}

int mid= start + (new_end-start) /2;

while(mid!=start)

{

if(mid==new_end)

{

mid--;

}

if(mid==start)

break;

swap(arr[mid],arr[new_end]);

new_end--;

}

}

void corr_arr1(int arr[], int start, int end)

{

int check=(end-start)%2;

int new_start=start;

if((end-start)%2!=0)

{

new_start=start+1;

}

int mid= start + (end-new_start) /2 ;

if(check==1)

mid++;

while(mid!=end)

{

if(mid==new_start)

{

mid++;

}

if(mid==end)

break;

swap(arr[mid],arr[new_start]);

new_start++;

}

}

void reorder(int arr [], int size)

{

int arr1_start=0;

int arr1_end=size/2-1;

int arr2_start=size/2;

int arr2_end=size-1;

print(arr,0,size-1);

corr_arr(arr,arr1_start,arr1_end);

print(arr,0,size-1);

corr_arr1(arr,arr2_start,arr2_end);

print(arr,0,size-1);

if((size/2)%2==1)

{

for(int i=1;i<size/2;i+=2)

{

swap(arr[i],arr[i+(size/2)]);

}

}

else

{

int size1=size -2 ;

for(int i=1;i<=size/2;)

{

swap(arr[i],arr[i+(size1/2)]);

i+=2;

}

}

print(arr,0,size-1);

}

void main()

{

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

int size=sizeof(arr)/sizeof(int);

reorder(arr, size);

}

assume the array is A[2n], then, if i is from 0 to n-1, the final position of A[i] is 2*i; if i is from n to 2n-1, the final position of A[i] is 2(i-n)+1. So simply move all A[i] to its final position is the solution.

psuedo code is as following.

for (i =0; i< 2n; i++) {

if (i < n)

A[i] <-> A[2i];

else

A[i] <-> A[2(i-n)+1];

}

quickswap(int* a, int len)

{

if(len<=2) return;

for(int i=len/4;i<len/2;i++)

swap(a[i],a[i+len/4]);

quickswap(a,len/2);

quickswap(a+len/2,len/2);

}

No, this is not correct.

It is working only if len is power of 2.

And complexity is not O(n) but O(logN)

Let the arrays be A and B.

A = [1, 2, 3, 4, 5]

B = [a, b, c, d, e]

Now the algorithm goes like:

1. Swap the even position elements from array A with odd position element from array B.

This will give

A = [1, a, 3, c, 5]

B = [2, b, 4, d, e]

2. Now form groups of elements from array A and array B, taking two elements at a time.

A = [(1,a),(3,c),(5)]

B = [(2,b),(4,d),(e)]

3. Repeat step 1. This time swap the even groups from array A with odd groups in array B.

Now, A = [(1,a),(2,b),(5)]

B = [(3,c),(4,d),(e)]

4. Now again form groups by grouping two adjacent groups together and repeat step 1.

This gives us : A = [(1,a,2,b),(5)] and B = [(3,c,4,d),(e)]

after repeating step 1 on the above array we get data as

(1,a,2,b),(3,c,4,d),(5),(e)

Now we cant group further, and our algo terminates with the desired output.

PS : I havent handled all the edge cases, but I feel it can be worked out with little more thinking.

If we look at a simple example, we will know how to handle it.

a1, a2, a3

b1, b2, b3

================

a1, a2, a3

b1, a3, b3,

tmp = b2

===============

a1, a2, a2

b1, a3, b3

===============

a1, b1, a2

b1, a3, b3

==============

a1, b1, a2

tmp,a3, b3

Here tmp is equal to b2 from the first step

so, it is O(2n), which is also O(n), and O(1) memory.

We can easily figure out the code based on which array is the data we wanna use from to fill which hole of the arrays.

As KK commented, I don't think one can use recursion for this problem, unless the recursive function does not take any argumentrs - because for each argument it takes, the space used is 0(n) where n is number of recursive calls.

But here's an iterative one:

// right: points to first array element

// on the right which needs to be

// brought to the left.

// len: length of the array

// arr: is the array itself

void changeArr( int *arr, int len, int *right ) {

int t1 = *arr;

int t2 = *right;

int end = arr + len;

int *pos = arr; // points to next pos that needs to be filled

while ( right < end ) {

swap(pos,t1); // temp = *pos,*pos = t1,t1 = temp; use LHS int

++pos; // advance position to fill

swap(pos,t2); // use RHS int

t1 = t2; // set the next LHS int to be used

t2 = *++right; // set the next RHS element to be used

++pos; // advance the position again

}

}

You need to call the above function with correct "right".

if you are implementing swap as a function, we need to make sure to pass t1 by reference, or use pointer..

if you are implementing swap as a function, we need to make sure to pass t1 by reference, or use pointer..

If Memory is not a concern, here is a quick solution:

```
public static string[] ReorderArray(string[] input)
{
int length = input.Length;
string[] output = new string[length];
int eventPos=0;
int oddPos=length/2; //start for second half of the input
for (int i = 0; i < length; i++)
{
if (i % 2 == 0)//even position 0, 2, 4, ..
{
output[i] = input[eventPos++];
}
else //odd position 1, 3, 5, ...
{
output[i] = input[oddPos++];
}
}
return output;
}
```

Yes there is an O(n) time, O(1) solution. Search the web for

Inshuffle in-place linear algorithm.

```
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
namespace ConsoleApplication1
{
class Program
{
static void Main(string[] args)
{
int[] num = { 1, 3, 5, 7,9,11,13,15, 2, 4, 6, 8,10,12,14,16 };
int temp = 0;
int nxt = 1;
for (int i = 0; i < num.Length/2; i++)
{
temp = num[num.Length / 2 + i];
for (int t = num.Length / 2 + i; t>i+nxt ; t--)
{
num[t] = num[t - 1];
}
num[i+nxt] = temp;
nxt +=1 ;
}
for (int i = 0; i < num.Length; i++)
{
Console.Write(num[i] + " ");
}
Console.ReadLine();
}
}
}
```

this works, but what is the complexity of this?

1: a1 { a2 a3 a4 b1 b2 b2 } b4

2: a1 b1 { b2 b3 a2 a3 } a4 b4

3: a1 b1 a2 { a3 b2 } b3 a4 b4

4: a1 b1 a2 b2 a3 b3 a4 b4

Try doing the above using a program

Simple C++ solution, but in O(n^2):

```
#include <iostream>
void RotateLeft(int v[], int i, int m) {
int tmp = v[i];
for(int j = i - 1; j >= i - m; --j){
v[j + 1] = v[j];
}
v[i - m] = tmp;
}
void Interleave(int v[], int n) {
for(int i = 0; i < n; ++i){
RotateLeft(v, i + n, n - i - 1);
}
}
int main() {
int v[] = {1,2,3,4, 10,20,30,40};
int len = sizeof(v) / sizeof(int);
Interleave(v, len / 2);
// 1 10 2 20 3 30 4 40
for(int i = 0 ; i < len; ++i){
std::cout << v[i] << " ";
}
std::cout << std::endl;
return 0;
}
```

I think this can be solved in O(n) using Stack.

1. Take 2 pointes say i and j

2. i points to an position and j points to bn position

3. in loop while i > 0 and j > an position

4. read element at j the position and push it to stack.

5. read element at i th position and push it to stack.

6. decrement i and j

7. repeat step 3 to 6 untill i becomes a1 or j becomes b1

8. pop all the elements from stack and assign them in the array.

9. Now the elemtns in array are a1b1a2b2.....anbn positioned.

This is my implementation of the direct and inverse problems solutions (perfect_shuffle_permutation_backward completely answers the question and works perfect with O(n) time and O(log log n) (same as in-place) memory requirements):

```
#include <iostream>
#include <iterator>
#include <vector>
#include <algorithm>
#include <cstdlib>
#include <cassert>
template< class V >
struct perfect_shuffle_permutation_forward
{
typedef typename V::iterator I;
typedef typename V::size_type SIZE;
void operator () (V & v) const
{
operator () (v.begin(), v.size());
}
void operator () (I const begin, I const end) const
{
operator () (begin, std::distance(begin, end));
}
void operator () (I const first, SIZE const size) const
{
SIZE sub_size;
for (SIZE offset(0); offset < size; offset += sub_size) {
sub_size = 1;
while (offset + sub_size * 3 < size) {
sub_size *= 3;
}
I const curr(first + offset);
cycle_leader(curr, sub_size);
++sub_size;
if (offset > 0) {
I const prev(first + offset / 2);
I const next(curr + sub_size / 2);
std::rotate(prev, curr, next);
}
}
}
private :
void cycle_leader(I const & begin, SIZE const & size) const
{
for (SIZE p(1); p < size; p *= 3) {
permutation permutation_(p, size);
auto & leader(begin[p]);
while (++permutation_) {
using std::swap;
swap(leader, begin[permutation_]);
}
}
}
struct permutation
{
permutation(SIZE const & leader_, SIZE const & size_)
: leader(leader_)
, current(leader_)
, size(size_)
{ ; }
bool operator ++ ()
{
if ((current % 2) != 0) {
current += size;
}
current /= 2;
return (current != leader);
}
operator SIZE () const
{
return current;
}
private :
SIZE const & leader;
SIZE current;
SIZE const & size;
};
};
template< class V >
struct perfect_shuffle_permutation_backward
{
typedef typename V::iterator I;
typedef typename V::size_type SIZE;
void operator () (V & v) const
{
operator () (v.begin(), v.size());
}
void operator () (I const begin, I const end) const
{
operator () (begin, std::distance(begin, end));
}
void operator () (I const first, SIZE const size) const
{
SIZE sub_size;
for (SIZE offset(0); offset < size; offset += sub_size) {
sub_size = 1;
while (offset + sub_size * 3 < size) {
sub_size *= 3;
}
I const curr(first + offset);
{
SIZE const rest(size - offset);
I const first(curr + (sub_size + 1) / 2);
I const middle(curr + (rest / 2 + rest % 2));
I const last(middle + (sub_size + 1) / 2);
std::rotate(first, middle, last);
}
cycle_leader(curr, sub_size);
++sub_size;
}
}
private :
void cycle_leader(I const & begin, SIZE const & size) const
{
for (SIZE p(1); p < size; p *= 3) {
permutation permutation_(p, size);
auto & leader(begin[p]);
while (++permutation_) {
using std::swap;
swap(leader, begin[permutation_]);
}
}
}
struct permutation
{
permutation(SIZE const & leader_, SIZE const & size_)
: leader(leader_)
, current(leader_)
, size(size_)
{ ; }
bool operator ++ ()
{
current *= 2;
if (!(current < size)) {
current -= size;
}
return (current != leader);
}
operator SIZE () const
{
return current;
}
private :
SIZE const & leader;
SIZE current;
SIZE const & size;
};
};
template< class V >
struct test
{
typedef typename V::size_type SIZE;
typedef typename V::value_type F;
typedef perfect_shuffle_permutation_forward< V > PF;
typedef perfect_shuffle_permutation_backward< V > PB;
bool operator () (SIZE const VECTOR_SIZE) const
{
V v;
v.reserve(VECTOR_SIZE);
for (SIZE i(0); i < v.capacity(); ++i) {
v.push_back(F(i));
}
V w(v);
std::copy(v.begin(), v.end(), std::ostream_iterator< F >(std::cout, " "));
std::cout << std::endl;
PF perfect_shuffle_permutation_forward_;
perfect_shuffle_permutation_forward_(v);
std::copy(v.begin(), v.end(), std::ostream_iterator< F >(std::cout, " "));
std::cout << std::endl;
PB perfect_shuffle_permutation_backward_;
perfect_shuffle_permutation_backward_(v);
std::copy(v.begin(), v.end(), std::ostream_iterator< F >(std::cout, " "));
std::cout << std::endl;
return ((v.size() == w.size()) && std::equal(v.begin(), v.end(), w.begin()));
}
};
int main(int argc, char *argv[])
{
typedef std::vector< int > V;
test< V > test_;
std::cout << std::endl;
for (std::size_t i(0); i < 30; ++i) {
assert(test_(i));
std::cout << std::endl;
}
return EXIT_SUCCESS;
}
```

{

actual = 2;

mid = n / 2 + 1;

for(int i=1;i<n;i++;

{

temp = a[actual];

a[actual]=a[mid];

a[mid]=temp;

actual++;

mid++;

}

}

for O(n) in time and O(1) in space

ques: Suppose we have an array a1,a2,... ,an, b1,b2,..., bn How to change this array to

- Ravi Kant Pandey April 25, 2007a1,b1,a2,b2, ...,an,bn in O(n) time and in O(1) space.

Solution:

the position of a0 and bn is fixed and they wont change so we have to replace remaining n-2 elements

count=n-2;

we strat from 2nd element find its position store the element at that position in temp variable and store 2nd element at that position.

now find the position of the stored temp varible and do as above

but it ends up at the position where u start so

start again from a position which ends up relocationg maximum no of elements.

#include<stdio.h>

#define n 10

int main(){

int a[n];

int count=0,i=1,put,temp,j=0;

int start=1;

for(j=0;j<n;j++)

a[j]=j;

printf("\n\n Elements: ");

for(j=0;j<n;j++)

printf("%d ",a[j]);

put=a[1];

while(count < n-2){

count++;

if(i< (n/2)){

temp=a[i*2];

a[i*2]=put;

put=temp;

i=2*i;

}

else{

temp=a[2*(i- (n/2))+1];

a[2*(i-(n/2))+1]=put;

put=temp;

i=2*(i-(n/2))+1;

if(i==start){

start=start+2;

put=a[start];

i=start;

}

}

}

printf("\n\nAfter Reordering: ");

for(j=0;j<n;j++)

printf("%d ",a[j]);

}

its not working when n>62 ie n=64 66 .....

could anyone improve or get another solution......