## Microsoft Interview Question

**Country:**India

This code will work only with an assumption that given input is of length 8. The logic will fail if we change the input window..

Eg. It won't work with - 123456abcdef

The algorithm will work with slight modification,

1) it should consider of swapping all from {2^i to 1} in boundary condition only.

for example : consider the case of 6 element :

```
1 [2] 3 [4] 5 [6] | {a} b {c} d {e} f
1a [3c] 5e|{2b} 4d {6f} <- this will not be swaped as there is not matching block to which it can swap this is a modification
1a 2b [5e]|{3c 4d} 6f <- here [5e] is the only left block so it will choose it, this is a modification.
1a 2b 3c 4d|5e 6f
Now consider the case of 7:
1 [2] 3 [4] 5 [6] 7 | {a} b {c} d {e} f {g} <- {g} will not be swapped
1a [3c] 5e [7] | {2b} 4d {6f} g <- [7] wil be swapped here(remember the modification)
1a 2b [5e 6f] | {3c 4d} 7g
1a 2b 3c 4d |5e 6f 7g
```

ya but it require O(n*log(n)) + O(1) complexity

```
/*Recursive solution*/
void Alter(char *arr, int mid, int len)
{
if(!arr || (len == 0) || (mid == 0))
return;
int tmp = arr[mid];
int k = mid;
Alter(arr, --k, len);
arr[mid + k] = arr[len/2 + k];
arr[mid + k + 1] = tmp;
return;
}
void AlterNumCharArray()
{
char arr[10] = {'1', '2', '3', '4', '5', 'a', 'b', 'c', 'd', 'e'};
int mid, len;
len = 10;
mid = len/2;
printf("\n Array before Alternation = ");
for(int i = 0; i < len; i++)
printf("%c ", arr[i]);
Alter(arr, mid-1, len);
printf("\n Array after Alternation = ");
for(int i = 0; i < len; i++)
printf("%c ", arr[i]);
return;
```

}

I believe the recursive algo will use n spaces (n int tep), which is an extra buffer. Am I rite?

can this be called of complexity O(n) ? I think yes ?

public static string[] Rearrange(string[] input)

{

int StartIndex = input.Length / 2;

int numOfSwaps = StartIndex - 2;

for (int k = 0; k <= numOfSwaps; k++)

{

int j = StartIndex - k;

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

{

string temp = input[j];

input[j] = input[j - 1];

input[j-1] = temp;

j = j + 2;

}

}

return input;

}

python

```
def inorder(a):
N = len(a)
startpos = 1
cpos = startpos
curelem = a[cpos]
while True:
npos = 0
if cpos < N/2:
npos = cpos * 2
else:
npos = (cpos - N/2)*2 + 1
tmp = a[npos]
a[npos] = curelem
cpos = npos
if cpos == startpos:
cpos += 2
if cpos > N /2:
break
startpos = cpos
tmp = a[cpos]
curelem = tmp
```

fixed:

```
def inorder(a):
N = len(a)
startpos = 1
cpos = startpos
curelem = a[cpos]
swaps = 0
while swaps < N - 2:
npos = 0
if cpos < N / 2:
npos = cpos * 2
else:
npos = (cpos - N / 2) * 2 + 1
tmp = a[npos]
a[npos] = curelem
cpos = npos
swaps += 1
if cpos == startpos:
cpos += 2
startpos = cpos
tmp = a[cpos]
curelem = tmp
return a
```

inorder([1,2,3,4,'a','b','c','d'])

[1, 'a', 2, 'b', 3, 'c', 4, 'd']

inorder([1,2,3,4,5,'a','b','c','d','e'])

[1, 'a', 2, 'b', 3, 'c', 4, 'd', 5, 'e']

inorder([1,2,3,4,5,6,7,'a','b','c','d','e','f','g'])

[1, 'a', 2, 'b', 3, 'c', 4, 'd', 5, 'e', 6, 'f', 7, 'g']

Only N - 2 swap operations are required

(first and last elements are in right positions from the begining).

We start from element with index 1.

For every element we calculate its new position:

all elements which indexes are smaller than (N / 2)(left part) will be shifted to the right:

new_position = current_position * 2

all elements on right from the middle(middle is included) will be shifted to the left:

and new_position = (current_position - N / 2) * 2 + 1.

On each step:

memorize an element which is being replaced - tmp = a[npos]

put current element into its new(final) position - a[npos] = curelem

make replaced element to be current one - curelem = tmp

The trick is tracking position where we start from - startpos:

if new_position is equal to startpos(we are back) we have to move right for 2 elements, because

they are in final position already.

```
// From www DOT ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi?board=riddles_cs;action=display;num=1094241218
#include <stdio.h>
#include <stdlib.h>
#include <malloc.h>
void Inshuffle(int *A, int N);
void follow_cycle(int *A, int N, int seed);
void cyclic_shift(int *A, int size, int distance);
void reverse(int *A, int size);
int Inverseof2(int M);
/***************************
Main Insuffle Algorithm.
Shuffle a1 a2 ..an b1 b2 ...bn
to
b1 a1 b2 a2 .... bn an
Parameters: A = the array
N = 2n, size of the array.
The permutation is given by
i -> 2i mod (N + 1)
We shuffle the array starting
from A[1] for easier coding.
****************************/
void Inshuffle(int *initialA, int initialN)
{
int m =1;
int i;
int power3 = 1;
int seed = 1;
int k = 1;
int n = initialN/2; //N is assumed to be even.
int *A = initialA;
int N = initialN;
while (N > 0){
//Reset Values.
m = 1;
i = 0;
power3 = 1;
seed = 1;
k = 1;
n = N/2;
//Step 1: Find an m such that 2m+1 is the largest power of 3 <= N+1
for (i = 0; i <= N+1; i ++){
if (3*power3 > N+1){
break;
}
power3 = 3*power3;
}
k = i;
m = (power3 - 1)/2;
//Step 2: Cyclic Right Shift A[m+1, n+m] by m
cyclic_shift(A+m+1,n,m);
// Step3: Do inshuffle of A[1....2m] by 'following cycle'.
for (i = 0 ; i < k; i ++)
{
follow_cycle(A,2*m,seed);
seed = 3*seed;
}
// Step 4: Recurse on A[2m+1...,2n]
//Could have made a recursive call here:
//Inshuffle(A+2*m,2*(n-m));
// But to make it O(1) space, convert tail recursion to iteration and put in a while loop.
A = A + 2*m;
N = 2*(n-m);
// Reset Values.
} //End of while loop.
}
/****************************************
Follow the cycle starting at seed.
For example: insuffle of 1 2 3 4 5 6 7 8
1 -> 2 -> 4 -> 8 -> 7 -> 5 -> 1
We follow this cycle in reverse order.
We look at 1. Save A[1].
Then look at what goes to 1, i.e 5 = 1*x
where x is inverse of 2.
Now fill A[1] with A[5].
Now look at what goes into A[5]. 7 = 5*x
(x is inverse of 2)
So fill A[5] with A[7].
And so on.
*****************************************/
void follow_cycle(int *A, int N, int seed)
{
int cur;
int inverse2 = Inverseof2(N+1);
int tmp;
int prev;
cur = (seed*inverse2 % (N+1));
tmp = A[seed];
prev = seed;
while (cur != seed){
A[prev] = A[cur];
prev = cur;
cur = (cur*inverse2 % (N+1));
}
A[prev] = tmp;
}
/*******************************
cyclic right shift an array by a given amount.
********************************/
void cyclic_shift(int *A, int sz, int k)
{
reverse(A,sz - k);
reverse(A+sz-k,k);
reverse(A,sz);
}
/******************************
reverse an array
*******************************/
void reverse(int *A, int sz)
{
int i;
int tmp;
for (i = 0; i < sz/2; i++)
{
tmp = A[i];
A[i] = A[sz-i-1];
A[sz-i-1] = tmp;
}
}
/***************************
find x such that 2x = 1 (mod M)
M is assumed to be an odd integer.
x = (M+1)/2
***************************/
int Inverseof2(int M)
{
return (M+1)/2;
}
int main()
{
int n;
int i;
int *A;
printf("Enter the value of n, (total size of array = 2n): ");
scanf("%d",&n);
A = (int *)malloc((2*n+1)*sizeof(int));
for (i = 0; i <= 2*n; i++){
A[i] = i;
}
Inshuffle(A,2*n);
printf("\n[");
for (i = 1; i <= 2*n; i ++){
printf(" %d",A[i]);
}
printf(" ]\n");
free(A);
return 1;
}
```

```
#include<stdio.h>
#include<string.h>
char* func(char arr[])
{
int start,cpos,npos,i,N;
char temp,cur_ele;
N=strlen(arr);
start=1;
cpos=start;
cur_ele=arr[cpos];
for(i=1;i<N-1;i++)
{
npos=0;
if(cpos<N/2)
npos=cpos*2;
else
npos=(cpos-N/2)*2+1;
temp=arr[npos];
arr[npos]=cur_ele;
cpos=npos;
if(cpos==start)
{
cpos=cpos+2;
start=cpos;
temp=arr[cpos];
}
cur_ele=temp;
}
return arr;
}
int main()
{
char str[20],*p;
gets(str);
p=func(str);
puts(p);
}
```

#include<iostream>

using namespace std;

char *str(char *s);

char *str(char *s)

{

int i=0,j=0,k=0;

char tmp1=s[k],temp2=s[++k];

while(s[i]<97)

i++;

while(s[i]!='\0')

{

s[j++]=tmp1;

tmp1=temp2;

temp2=s[++k];

s[j++]=s[i++];

}

s[j]='\0';

return s;

}

int main()

{

char *s;

cin>> s;

cout<<str(s);

return 0;

}

```
#include<stdio.h>
#include<string.h>
int main()
{
char str[10000];
char str1[10000];
int arr[10000];
scanf("%s",str);
int i,j=0,k,a,m=0;
k=strlen(str);
for(i=0;i<k;i++)
{
a=str[i]-'0';
if(a>=0&&a<=9)
{
arr[j]=a;
j=j+1;
}
else{
str1[m]=str[i];
m=m+1;
}
}
for(i=0;i<j;i++)
{
printf("%d%c",arr[i],str1[i]);
}
return 0;
}
```

This might be work for all the cases...

#define SIZE 8

void exchange(char arr[], int x, int y)

{

int i =x;

while( x!=0 || y != SIZE-1)

{

if ( i<= y)

{

int t = arr[i];

arr[i] = arr[i+1];

arr[i+1] = t;

i = i+2;

}else{

i = x= x-1;

y = y+1;

}

}

}

int _tmain(int argc, _TCHAR* argv[])

{

char arr[8] = {'1','2','3','4','a','b','c','d'};

exchange(arr, (SIZE/2 -1), SIZE/2);

return 0;

}

recursive solution by r.s above is correct

it takes O(n) time and constant space without using any extra DS.

Ans by I.mnext is correct as well, though it takes O(nlogn) time.

I have traced both the solutions.

recursive solution by r.s above is correct

it takes O(n) time and constant space without using any extra DS.

Ans by I.mnext is correct as well, though it takes O(nlogn) time.

I have traced both the solutions and evaluated the complexity

recursive solution by r.s above is correct

it takes O(n) time and constant space without using any extra DS.

Ans by I.mnext is correct as well, though it takes O(nlogn) time.

I have traced both the solutions and evaluated the complexity

Solution in Python is correct. As I have traced it, it takes O(N) time with constant space.

Its also easily convertible to C/C++/JAVA.

Thumbs up :)

Unfortunately it doesn't work for:

l = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 'a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k', 'l', 'm', 'n', 'o', 'p', 'q', 'r', 's', 't', 'u', 'v', 'w', 'x', 'y', 'z']

a bug is in moving startpos 2 elements to the right. Actually step is not constant. I modified the code to work correctly, but now it doesn't obey constraints(memory and complexity) For the list above:

step: 2

step: 2

step: 4

step: 2

step: 6

step: 2

step: 32

figuring out what a step depends on...

Yes, this is a hard problem and easy to think you have got a correct solution.

You testcase should try it for at least 10000 different values of n.

And if you claim some time and space complexity better try proving it.

//

// This assumes that the string sent in is properly formatted as "123456abcdef"

// and handles if this is not the case

//

static void PermutationsCombinations(string s)

{

int alpha = 0;

StringBuilder sb = new StringBuilder();

// Assuming that the string has to have equal number of digits and characters

if (s.Length % 2 != 0)

{

Console.WriteLine("The string is not even numbered - 1-digit to be paired with 1-character");

return;

}

// Parse the string and determine the exact position where the alphabets start within

for (int i = 0; i < s.Length; i++)

if (char.ToLower(s[i]) >= 'a' && char.ToLower(s[i]) <= 'z')

{

alpha = i;

break;

}

// Verify that the position is exactly half of the provided string

if (alpha != (s.Length/2))

{

Console.WriteLine("There are not equal digits and characters in the string!");

return;

}

// Use a stringBuilder class to collect the different digits and alphabets

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

{

sb.Append(s[i]);

sb.Append(s[i + alpha]);

}

Console.WriteLine(sb);

}

There is one importnant from my perspective thing (which I was not familar with previously): if the algo uses n additional bits it is considered to use O(1) additional space anyway. (Since a representation of at least number 'n' requires log(n) bits.)

So we could just mark already swapped numbers in the array doing cycles and do not start the cycle for those numbers which are already marked. Result: O(n) times (for n-2 swaps) and O(1) space (for n bits).

Here is my solutions in C#

static void Main(string[] args)

{

string[] arr = new string[] { "1","2","3","4", "a","b","c","d",};

int arrayLength = arr.Length;

if (arr.Length / 2 % 2 != 0)

{

arrayLength = arrayLength - 2;

int startIndex = (arr.Length / 2)-1;

while (startIndex < arr.Length - 2)

{

string temp = arr[startIndex];

arr[startIndex] = arr[startIndex + 1];

arr[startIndex + 1] = temp;

startIndex++;

}

}

for (int i = 1, j = arrayLength / 2; i < arrayLength && j < arrayLength; i++, j++)

{

string temp = arr[j];

arr[j] = arr[i];

arr[i] = temp;

i++; j++;

}

int movesRequired = (arrayLength - 4) / 2;

int numPointer = arrayLength / 2;

int charPointer = numPointer + 1;

string nextIntValue = arr[numPointer];

string nextCharValue = arr[charPointer];

while (movesRequired > 0)

{

movesRequired--;

int newIntPos = GetNewPositionForInt(numPointer, arrayLength);

int newCharPos = GetNewPositionForChar(charPointer, arrayLength);

string tempInt = arr[newIntPos];

string tempChar = arr[newCharPos];

arr[newIntPos] = nextIntValue;

arr[newCharPos] = nextCharValue;

numPointer = newIntPos;

charPointer = newCharPos;

nextIntValue = tempInt;

nextCharValue = tempChar;

}

}

private static int GetNewPositionForChar(int charPointer, int arrayLength)

{

int mid = arrayLength / 2;

if (charPointer >= mid)

{

int diff = (charPointer - mid - 1);

int pow = GetPowerOf2(diff);

return diff == 0 ? 2 + 1 : 2 + pow + 1;

}

else

{

return (2 * (charPointer-1)) + 1;

}

}

private static int GetNewPositionForInt(int numPointer, int arrayLength)

{

int mid= arrayLength/2;

if (numPointer >= mid)

{

int diff = (numPointer - mid);

int pow = GetPowerOf2(diff);

return diff == 0 ? 2 : (2 + pow);

}

else

{

return 2 * numPointer;

}

}

private static int GetPowerOf2(int diff)

{

int powOf2 = 1;

while (diff > 0)

{

diff--;

powOf2 *= 2;

}

return powOf2;

}

My observation:

correct position of i if i belongs to 1st half of the array will be j=2*i, or if i belongs to 2nd half then it will be j=2*i-len+1

if length is not power of 2:

say

12345abcde

start from i=1;

then try to place s[i] to its correct poition j which is 2;

then take s[j] and try to place it in proper place which is 4. So new j is 4.

next j=8.

and go on like this..

Now if lenth is not power of 2, then in one round it gets over..

But if its power of 2,

eg:

1234abcd

0->0

1->2

2->4

4->1

5->3

6->5

7->7

so starts with i=1;

1->2

2->4

4->1

one cycle ended.. new cycle starts from 3...

so for length len where len=power of 2...

one cycle starts from 1

next cycle from 3

next from 5

then 7

........until its <len/2

code is

```
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
int ispowerof2(int len){
if(len==1)
return 1;
if(len%2==1)
return 0;
return ispowerof2(len/2);
}
char *change(char *str){
int i=1,j,k;
int flag=0;
char t,t1;
int len=strlen(str);
if(ispowerof2(len))
flag=1;
if(flag==0){
t=str[1];
while(1){
if(i<len/2)
j=2*i;
else
j=2*i-len+1;
if(str[j]==t)
return str;
t1=str[j];
str[j]=t;
t=t1;
i=j;
}
}
else{
k=1;
i=1;
t=str[1];
while(k<len/2){
if(i<len/2)
j=2*i;
else
j=2*i-len+1;
if(str[j]==t){
k+=2;
t=str[k];
i=k;
//continue;
}
else{
t1=str[j];
str[j]=t;
t=t1;
i=j;
}
}
return str;
}
}
main(){
char *s;
s=malloc(100*sizeof(char));
strcpy(s,"123456789abcdefghi");
s=change(s);
printf("%s",s);
}
```

```
void SwapFromMid(char *str, int start, int mid, int end)
{
if(end -start <1) return;
int i= start;
int j= mid;
char temp;
while(i<=mid-1 && j<=end)
{
temp = str[i]; str[i] = str[j]; str[j]=temp;
i++;j++;
}
return;
}
int main()
{
char str[MAX_SIZE];
cout<<"Enter the string"<<endl;
cin>>str;
int len = strlen(str);
int i=1;
int j = len/2;
while(i<=(len/2-1))
{
SwapFromMid(str,i,j,len-i-1);
i++;
}
cout<<"String after swap: ";
cout<<str<<endl;
return 1;
}
```

Assuming that numbers and letters are always a continuous sequence, we can get the expected position of any element in O(1).

Position of any digit D = (D - 1) * 2

Position of any letter L = (L - 1) * 2 + 1

Input --> 1 [2] 3 4 5 6 [a] b c d e f

Initially we maintain two pointers on the elements between [] that gives us

1 a [3] 4 5 6 [2] b c d e f

Now that we have one element in the correct position and another (2) in a faulty position, we maintain the pointer pointing to [2] and move the other pointer to the correct position of (2) using the equation above. and repeat that until both elements pointed to are in their correct positions.

O(n) time and in place.

- pavi.8081 September 01, 2012