Microsoft Interview Question for Software Engineer / Developers






Comment hidden because of low score. Click to expand.
0
of 0 vote

ques: Suppose we have an array a1,a2,... ,an, b1,b2,..., bn How to change this array to
a1,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......

- Ravi Kant Pandey April 25, 2007 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

By 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

- k June 23, 2007 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- poly August 21, 2007 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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;
}

- Sandy October 30, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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;
}

- Anonymous October 30, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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;
}

- sandy October 30, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

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.

- codebug June 05, 2007 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

The shift operation will prove very expensive resulting in O(n^2). does any1 have a correst solution to this problem

- Vel October 29, 2007 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

{
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++;

}

- Meg July 06, 2007 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

this is O(n ^ 2)

- socailmetric January 05, 2009 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

This algorithm works. I wonder if anybody has found any O(n) algorithm with just 0(1) space.

- Daniel Johnson February 01, 2009 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

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;
}
}

- Diganta October 04, 2007 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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.

- sb October 14, 2007 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- Vimil November 10, 2007 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- Dom November 20, 2007 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

#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;
}

- bwc November 20, 2007 | Flag Reply
Comment hidden because of low score. Click to expand.
8
of 8 votes

I don't think this algorithm is O(n)

- greatht November 20, 2007 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

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 .

- Anonymous0708 November 21, 2007 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Read the question man, O(n) time, O(1) memory

- J May 03, 2008 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

Well the above solution is right but it takes O(n2)...
It has to be done in O(n)

- Vamsi November 28, 2007 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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++;
		}
	}
}

- Vamsi November 28, 2007 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Perfect solution

- de-coder September 25, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

Sorry pasted the wrong one. This might work

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

- Vamsi November 29, 2007 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Above Solution is not working...
For array 1..10 try out 3 and 4 are not a correct position

- K2G December 08, 2007 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

vamsi ur code is not workin

- goobe April 09, 2008 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- KK April 16, 2008 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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);
}

- usafzz May 21, 2008 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Perfect job!!!

- yingdi February 24, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Perfect job!!!

- yingdi February 24, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

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];
}

- lensbo September 10, 2008 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Have you ever thought about your solution? It is definitely not working!

- Anonymous September 14, 2008 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

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);
}

- winia October 31, 2008 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

This algorithm is correct... O(n) time and O(1) space..

- Prateek September 30, 2010 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

No, this is not correct.
It is working only if len is power of 2.
And complexity is not O(n) but O(logN)

- Anon April 02, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

did not work for n= 16
input = arr[]={1,9,2,10,3,11,4,12,5,13,6,14,7,15,8,16};
expected out put :1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16

output of ur code is : 1
5
9
13
2
6
10
14
3
7
11
15
4
8
12
16

- SDguy May 13, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

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.

- algooz November 08, 2008 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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.

- Yixin November 14, 2008 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- acoader November 18, 2008 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- acoader November 18, 2008 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- acoader November 18, 2008 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Have you ever tested your program? It is NOT correct at all!!!

- Anonymous January 15, 2009 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

Has anybody found a correct O(n) time and O(1) space solution to this problem ?

- Daniel Johnson January 27, 2009 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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;
        }

- SaiS March 11, 2009 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

Inshuffle in-place linear algorithm.

- T March 12, 2009 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Glad you din't say Google.

- Anonymous October 17, 2010 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

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?

- Jack_2060 August 23, 2009 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- YawnSolutionKarma August 31, 2009 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

This one does not work!
It takes O(n^2) time.

- qimi October 07, 2009 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

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;
}

- Markus February 28, 2010 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Here is the solution:
interviewcodesnippets.com/?p=171

- moe July 30, 2010 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

@above the code in the link is O(nlogn) not O(n)

- Anonymous February 21, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

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.

- Anand patil August 05, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

But the question says no additional space to be used.

- Andy September 30, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

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;
}

- Dukales November 09, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

{
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

- trevium September 21, 2007 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

This would not work .

- Joe October 30, 2007 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Won't work

- RDK November 30, 2008 | Flag


Add a Comment
Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

Learn More

Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More