## Microsoft Interview Question

• 0

Country: India

Comment hidden because of low score. Click to expand.
3
of 7 vote

``````Iterative Program logic explaination of function: alternateLettersAndNums()

initial: 1 2 3 4 5 6 7 8 | a b c d e f g h

step 1a: 1 [2] 3 [4] 5 [6] 7 [8] | [a] b [c] d [e] f [g] h
leaving 1 element from start, elements selected from step 1a in [] are swapped respectively with elements after the bar: '|', resulting in:
Step 1b: 1 [a] 3 [c] 5 [e] 7 [g] | [2] b [4] d [6] f [8] h

Step 2a: 1 [a] {3 [c]} 5 [e] {7 [g]} | {[2] b} [4] d {[6] f} [8] h
leaving 2 element from start, elements in group of 2 with in {} are swapped with elements with in {} after bar, resulting in:
step 2b: 1 [a] [2] b 5 [e] [6] f | 3 [c] [4] d 7 [g] [8] h

Step 3a: 1 [a] [2] b {5 [e] [6] f} | {3 [c] [4]} d 7 [g] [8] h
leaving 4 element from start, elements in group of 4 with in {} are swapped with elements with in {} after bar, resulting in:
Step 3b: 1 [a] [2] b {3 [c] [4] d} | {5 [e] [6] f} 7 [g] [8] h

Final o/p: 1 a 2 b 3 c 4 d 5 e 6 f 7 g 8 h
/////////////////////////////////////////
Program:
/*
Constraints met:
Space complexity: In-Place, O(1)
Time Complexity: O(N):
*/

#include<stdio.h>
#include<math.h>

static void swap(char a[], int s, int e, int len)
{
int i=s, j=e, temp=0;
for(i=s; (i-s+1<=len)&&(i); i++, j++)
{
temp = a[i];
a[i] = a[j];
a[j] = temp;
}
}

void alternateLettersAndNums(char arr[], int len)
{
int jumps, i, k, no, ch, temp;
int c = (len + 1)/2;

for(jumps=0; (i = (int)pow((double)2, jumps))<(int)len/2; jumps++)
{
i = (int)pow((double)2, jumps);
for(k=0; k < c; k+=i*2)
{
no = i+k;
ch = c+k;
swap(arr, no, ch, i);
}
}
return;
}

void alternateLettersAndNumsDriver()
{
int i;
char A[] = {'1', '2', '3', '4', '5', '6', '7', '8', 'A', 'B', 'C', 'D', 'E', 'F', 'G', 'H'};

printf("\nGiven array:\n");
for(i=0; i<sizeof(A)/sizeof(char); i++)
printf("%c  ", A[i]);

alternateLettersAndNums(A, sizeof(A)/sizeof(char));

printf("\nAfter alternating:\n");
for(i=0; i<sizeof(A)/sizeof(char); i++)
printf("%c  ", A[i]);
return;
}
/////////////////////////////////////////////``````

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

Even if this works, this is nlogn.

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

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

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

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

Comment hidden because of low score. Click to expand.
3
of 9 vote

``````/*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;``````

}

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

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

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

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

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

This works. But dont know if this is O(n) or not.

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

@anonymous :
{1} + {1+1} + {1+1+1} + {1+1+1+1} + ... + {1+1+1+ ... + 1(N/2-2 time)}(N/2-2 times) = 1+2+3+4+5+ ... + N/2-2 = (N/2-2)*(N/2-1)/2 = O(N*N)

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

o(n) is impossible. Did you mean O(n)?

And are you just posting a puzzle or was this really asked in an interview? (with the O(n) time and O(1) space restriction).

Comment hidden because of low score. Click to expand.
1
of 3 vote

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``````

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

oops, works only for 1234abcd

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

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']

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

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

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.

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

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

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

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

but for the problem 1234abcd -> a1b2c3d4.

(Which can be trivially converted to 1a2b3c4d).

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

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

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

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

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

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

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

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

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

Get the length of the string first (Say its n)... then divide the length by 2... use 2 variables i and j where i starts from 1 and j from n/2+1... Increment i by 2 every-time and j by 1 and swap them... that is it...

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

the question is not clear... do we just need to show the pattern on console,(since it is given output),or we have to modify the array as well..?? and the array should contain the pattern,please do post

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

None of the posted answers is right.

Comment hidden because of low score. Click to expand.
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.

Comment hidden because of low score. Click to expand.
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 and evaluated the complexity

Comment hidden because of low score. Click to expand.
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 and evaluated the complexity

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

How about solution in python? Isn't it correct?

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

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 :)

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

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

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

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.

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

+1 , even python one fails for 12345abcd

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

Actually there is one correct answer now. It is a long post with C code. Has the following at the top:

``// From www DOT ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi?board=riddles_cs;action=display;num=1094241218``

See that thread for a proof of correctness.

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

this is In-place matrix transposition problem, you can google it, its a famous algo.

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

``````void specialSort(char arr[], int len)
{
if(!arr || len < 3)
return;

int i = (len-1)/2, j = i+1;

while(i>0 && j<(len-1))
{
int m = i, n = j;
while(m < n)
{
swap(arr[m],arr[m+1]);
m+=2;
if(m<n)
{
swap(arr[n],arr[n-1]);
n-=2;
}
}
i--;
j++;
}
}``````

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

``````void specialSort(char arr[], int len)
{
if(!arr || len < 3)
return;

int i = (len-1)/2, j = i+1;

while(i>0 && j<(len-1))
{
int m = i, n = j;
while(m < n)
{
swap(arr[m],arr[m+1]);
m+=2;
if(m<n)
{
swap(arr[n],arr[n-1]);
n-=2;
}
}
i--;
j++;
}
}``````

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

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

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

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

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

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

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

MERGE SORT!!!!
I REALLY UNDERSTAND THE DIFFERENCES BETWEEN MICROSOFT AND GOOGLE!!!

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

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

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

Assume char for i position is ch.
If it is a digit, its right position should be (ch - '0') * 2 - 1.
If it is not a digit, its right position should be (ch - 'a') * 2.
Can be solved by circle sort, O(n) time, O(1) space.

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

position for alphabet: (ch - 'a') * 2
position for digit: (ch - '0') * 2 - 1
Can be solved by circle sort in O(n) time, O(1) space.

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

position for alphabet: (ch - 'a') * 2
position for digit: (ch - '0') * 2 - 1
Can be solved by circle sort in O(n) time, O(1) space.

Comment hidden because of low score. Click to expand.
-1
of 3 vote

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

Comment hidden because of low score. Click to expand.
-1
of 1 vote

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.

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

LOL!

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

Why not
if(input == '1234abcd')
{
output = '1a2b3c4d';
}

Lemme know if dosesn't satify your input criteria.. ;)

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.

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