## Microsoft Interview Question for Software Engineer / Developers

• 0

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

Just put the characters in place first. So for every position in the array 1,3,5,... and so on, just place the characters c1,c2,c3 by exchanging the values of the integers in those positions by the character positions.

After this, you will have the array with all the characters at right positions, but the integers will be randomly distributed. Use modified quicksort on adjacent positions (0,2,4,6...) of the array to sort the integers.

The running time of the algo is O(n + nlgn) = O(nlgn)

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

Why to sort numbers?
What if the numbers in original array itself are not sorted....????!!!!

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

another simple solution that works in O(n) time.

Traverse the array and find the right location. Eg: if an element is located at position 2 (array starts at 0) its right position would be 2*2 mod maxIndexofArray = 4. Replace the value at position 4 and and find the right position for this new element. Keep track of the start index to make sure we dont do into an infinite loop. Get the next untouched element and repeat.

``````pseudo code:
startIndex,curIndex =0; maxIndexofArray=lenghtofArray-1;
while (curIndex != maxArrayofIndex)
{
do {
curIndex = curIndex*2;
curVal = array[curIndex];
array[curIndex] = prevVal;
prevVal = curVal;
}while (curIndex != startIndex)
curIndex = (curIndex *2) + 1
startIndex = curIndex;
prevVal = array[curIndex];
}``````

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

Well how do you keep track of an untouched element ? Its an in-place algo that we are looking for

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

Above solutoin has a bug... curIndex should be incremented.,

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

void in_place_rearrange(int arr[], size_t n){
int temp1=arr[1];
int temp2=-1;
size_t index=1;
size_t start=1;
for(int i=1;i!=2*n-1;++i){
if(index<n){
index=index*2;
}else{
index=2*(index-n)+1;
}
temp2=arr[index];
arr[index]=temp1;
temp1=temp2;
if(index==start){
for(size_t j=start;j!=2*n-1;++j){
if((arr[j]+j)%2!=1){
index=j;
temp1=arr[j];
break;
}
}
}
}
};

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

Note that the first and the last values never change their position. So, we have to deal with 2n-2 values.

Integers at index i, should end up at j = 2*n. Similarly, characters at index i, should end up at j = 2*n+1.

With the above information, we start with the second index of the array and determine its correct position in the final array. The old value at this position is recorded along with its index, which is used in the next iteration. We perform this 2n-2 times to ensure all elements end up in their final positions.

int count = 0;
int i = 2;
int j, tmp = a[i], tmp1;

while (count < 2*n-2)
{
count++;

if (i < n)
j = 2*i;
else
j = 2*i+1;

tmp1 = a[j];
a[j] = tmp;
tmp = tmp1;
i = j;
}

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

Firstly in else case it should be 2*i+1 mod n(size of the array)... secondly there is a possibility that a cycle forms and all numbers are not traversed. like if the size of array is 10

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

array with int and char together???? what kind of array is it???
array is a collection of similar data types...BASICS :)

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

A char can be manipulated in similar ways as an int. You can store a character value in an integer variable... BASICS? no?

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

Anonymous has raised a valid question. I think instead of chars we can assume that we have different set of numbers and focus on the logic of pairing up things in the required manner.

Consider the following example where n(=12) is an even number
e.g. 1 2 3 4 5 6 7 8 9 10 11 12 a b c d e f g h i j k l

step 1: for the first n part do not move the even positioned elements and for the next n part do not move the odd positioned elements.(i.e. 1_3_5_7_8_9_11_ _b_d_f_h_j_l) but interchange the even positioned elements of the first n part with the odd positioned elements of the second n part which results into the following sequence. 1 a 3 c 5 e 7 g 9 i 11 k 2 b 4 d 6 f 8 h 10 j 12 l, which can be viewed as pairs indicated below
(1 a) (3 c) (5 e) (7 g) (9 i) (11 k) (2 b) (4 d) (6 f) (8 h) (10 j) (12 l)

Step 2: Apply the same pairing logic as described above fix the odd positioned pairs in the first n-element array and even positioned elements in the second n-element array and exchange the rest will result into the following

(1 a) (2 b) (5 e) (6 f) (9 i) (10 j) (3 c) (4 d) (7 g) (8 h) (11 k)(12 l)

Now this can be viewed by pairing up four elements togeher in the following way

(1 a 2 b) (5 e 6 f) (9 i 10 j) (3 c 4 d) (7 g 8 h) (11 k 12 l)

step 3: Do the same thing like fixing the odd positioned elements in first half and even positioned in the second half and exchange the rest

(1 a 2 b) (3 c 4 d) (9 i 10 j) (5 e 6 f) (7 g 8 h) (11 k 12 l)

step 4: Pair up the adjacent elements again to result into the following

(1 a 2 b 3 c 4 d) (9 i 10 j) (5 e 6 f 7 g 8 h) (11 k 12 l)

step 5: Apply the same logic again and you will end up with the result
(1 a 2 b 3 c 4 d 5 e 6 f 7 g 8 h 9 i 10 j 11 k 12 l)

Logic needs to be changed a little bit in when n = odd number and I am working on it.

But there is a lot of overhead of exchanging elements if anybody can come out with some insight to overcome this pls discuss it. Thank you.

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

Good idea, Mohan.
I tested it, and it works.
It is O(n*lgn) which beats O(n^2).

int[] a = {1, 2, 3, 'a', 'b', 'c'};
int subLen=1;
int i,j;
int n=a.length/2;

while(subLen < n){
i = subLen;
j = n;
while(i<n){
for(int k=0; k< subLen; k++){
swap(a, i, j);
i ++;
j ++;
}
i = i+subLen;
j = j+subLen;
}
subLen *= 2;
}

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

But the time complexity is still O(nlogn)

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

``````void alternateIntChar()
{
vector<char> vc;
char i;
for( i = 0; i < 10; i++)
vc.push_back(i+'0');
for(i=0;i<10;i++)
vc.push_back(i+'a');
cout << "Before: "<< endl;
vector<char>::iterator it;
for(it=vc.begin(); it != vc.end(); ++it)
cout << *it << ",";
vector<char>vo;
for(i=0;i<vc.size()/2;i++)
{
vo.push_back(vc[i]);
vo.push_back(vc[i+10]);
}
cout << "After: " << endl;
for(it=vo.begin(); it != vo.end(); ++it)
cout << *it << ",";``````

}

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

// PairUp.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"

#include <iostream>
using namespace std ;

int LEN ;

//int arr[] = { 2, 4, 6, 8, 10, 12, 14, 16, 18, 3, 5, 7, 9, 11, 13, 15, 17, 19 } ; //With n=5
/* 0 1 2 3 4 5 6 7 8 9
* result = { 2, 3, 4, 5, 6, 7, 8, 9, 10, 11}
* */

static int count = 0 ;

int * CreateArray(int N )
{
int* arr = new int[2*N] ;
for ( int i = 1 ; i <= 2*N; i++)
{
if ( i <= N )
{
arr[i-1] = i*2 ;
}
else
{
arr[i-1] = (i-N)*2 +1 ;
}
}
return arr ;
}

void PrintArray(int*arr)
{

for (int i = 0 ; i < LEN*2 ;i++)
{
cout<<arr[i]<<" " ;
}
cout<<endl;
}

void Swap(int* a, int*b)
{
int t = *a;
*a = *b;
*b = t ;
}

//Assume that array length is 2n
//Assume that the array contains a_1, a_2, ..., a_n, b_1, b_2, ...b_n
//we need to give the output as (a_1,b_1), (a_2,b_2),...(a_n,b_n)

void PairUp(int* arr,int start, int end)
{

if (end - start <= 2 )
{
return ;
}
else
{

PrintArray(arr) ;
int mix = start + (end - start )/2 - 1 ;
Swap(&arr[mix], &arr[mix+1] );

count++ ;

PrintArray(arr) ;

for ( int i = 0 ; i < (end - start)/2 - 2 ; i++ )
{
Swap( &arr[mix-1-i],&arr[mix-i]) ;
Swap( &arr[mix+1+i],&arr[mix+2+i]) ;
PrintArray(arr) ;
count+=2 ;

}
PairUp(arr, start+2, end -2 );

}

}
int main(int argc, char** argv)
{
LEN = atoi(argv[1]) ;

int* arr = CreateArray(LEN);

PairUp(arr, 0, LEN*2 );
cout<<"----------count------"<<count<<endl ;

delete[] arr;

return 0;
}

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

using System;
using System.Collections.Generic;
using System.Text;

namespace alternate
{
class Program
{
static int length;
static void swap(ref int a, ref int b)
{
int temp = a;
a = b;
b = temp;
}

static int GetCorrectPosition(int pos)
{
if (pos <= length /2)
{
return 2 * pos - 1;
}
else
{
return (pos - length/2) * 2;
}
}

static int count;
static void alternate(ref int[] arr)
{
for (int i = length / 2; i > (length/4); i--)
{
int start = i;
int new_pos = GetCorrectPosition(start);
while (true)
{
++count;
swap(ref arr[new_pos], ref arr[start]);
int temp = new_pos;
new_pos = GetCorrectPosition(new_pos);
if (start == new_pos)
break;
}

if (count >= length/2)
break;
}
}
static void Main(string[] args)
{
int[] arr = { 0, 1, 3, 2, 4};
length = arr.Length - 1;
alternate(ref arr);
Console.WriteLine(count);
}
}
}

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

arr[i1, i2, i3, ... in, c1, c2, c3, ... cn]
We need two extra int variables(Is not this allowed in terms of in-place algo? Sorry and please ignore this answer if that is not allowed).
tempInt, tempPosition are those two variables.
1) i1 is not touched.
2) tempInt = arr[1];
3) arr[1] = arr[n];
4) tempPosition = n;
5) arr[n] = arr[i];
6) tempInt = arr[2];
7) arr[2] = arr[tempPosition];

keep doing this.
O(n) and n+2 space is needed

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

The correct answer without the temporay array. Cheers.

``````void Shuffle(int *pData, int mid, int size)
{
if(size > 2)
{
for(int index = (mid & 1) ? mid + 1 : mid; index < size; index += 2)
{
int temp = pData[index];
pData[index] = pData[index / 2];
pData[index / 2] = temp;
}
for(int index = 2 * (mid - 1) - 1; index >= mid; index -= 2)
{
int indexF = mid - 1;
for(int indexS = index; indexS >= mid; indexS -= 2)
{
int temp = pData[indexF];
pData[indexF--] = pData[indexS];
pData[indexS] = temp;
}
}
int newMid = (mid & 1 ? mid + 1 : mid) / 2;
Shuffle(pData, newMid, mid);
}
}

int tArray[] = {1,2,3,4,5,6,7,8,9,21,22,23,24,25,26,27,28,29};
Shuffle(tArray, 9, 18);
for(int i = 0; i < 18; i++)
cout << tArray[i] << " ";
cout << endl;``````

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

By using recursion, your space complexity becomes O(N), which is identical to construct a new array.

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

just go to mid of the array.
try swapping the numbers as follows.
initial:123abc
go to mid swap mid & mid+1
12a3bc
2 recursive calls
one to i-1
so it swaps i-1 and i
other to i+1
so it swaps i+1 and i+2
1a2b3c
check for boundary conditions...
here u need one temp variable for swapping ..

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

try with 1234abcd
1234abcd
123a4bcd i=4
12a3b4cd i=3,5
1a23bc4d i=2,6

its wrong, but good try

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

this can be done with much ease:

say you have a1,a2,a3,a4,b1,b2,b3,b4
you can do it with an example :a1,a2,a3,a4,b1,b2,b3,b4
now swap 1 pair : a1,a2,a3,[a4,b1],b2,b3,b4 ->a1,a2,a3,b1,a4,b2,b3,b4
now swap 2 pairs :a1,a2,[a3,b1],[a4,b2],b3,b4->a1,a2,b1,a3,b2,a4,b3,b4
now swap 3 pairs : a1,[a2,b1],[a3,b2],[a4,b3],b4->a1,b1,a2,b2,a3,b3,a4,b4
so if you have more number of elements obviously more swaps.

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

thats right! beautiful

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

Just because you agree with it, it is correct and beautiful?

LOL. I suggest you try to prove that it is correct.

Also, what is the time complexity of this?

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

i1 i2 i3 i4 i5 i6 i7 i8 c1 c2 c3 c4 c5 c6 c7 c8//swap i5-i8 with c1-c4

i1 i2 i3 i4 c1 c2 c3 c4 i5 i6 i7 i8 c5 c6 c7 c8//swap i3,i4 with c1,c2,swap c5,c6 with i7,i8

i1 i2 c1 c2 i3 i4 c3 c4 i5 i6 c5 c6 i7 i8 c7 c8//swap i2 with c1, swap i4 with c3 ........

i1 c1 i2 c2 i3 c3 i4 c4 i5 c5 i6 c6 i7 c7 i8 c8

so we do the swap like binary sorting, the complexity is O(nlogn)

``````int* rearrange(int A[],int length)
{
int binary=1;
length=length/2;
while(length>1)
{
for(int m=0;m<binary;m++)
{
for(int n=0;n<length/2;n++)
{
int temp=A[(2*m+1)*length-length/2+n];
A[(2*m+1)*length-length/2+n]=A[(2*m+1)*length+n];
A[(2*m+1)*length+n]=temp;
}
}
binary=binary*2;
length=length/2;
}
return A;
}``````

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

None of the in-place solutions which claim O(N) time are correct. What kind of discussion is this?

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

'spt' suggested a good method.. My solution is inspired from him.. It takes O(n) time and 1 extra varaible..

Algo-

Consider array[] from 1 to n instead of o to n-1 (easy for calculation and understanding)

//Error checking..
if(n%2==1 || n <2)
return error;

int a = i2;

While (1)
{
if (a == integer)
//Calculate correct postn and store in postn
else
// calculate correct postn and store in postn

if(postn==2)
break;

Swap array[postn] and a
}

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

Sorry coder, your solution is wrong too.

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

for i = 1 to 2*n-1 step 2
....CircularRotate(A,i,(i-1)/2 +n)

Example :
<abcde12345>
<a1bcde2345> after CircularRotate(A,1,5) ( 5 shifts)
<a1b2cde345> after CircularRotate(A,3,6) ( 4 shifts)
<a1b2c3de45> after CircularRotate(A,5,7) ( 3 shifts)
<a1b2c3d4e5> after CircularRotate(A,7,8) ( 2 shifts)

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

for i = 1 to 2*n-1 step 2
....CircularRotate(A,i,(i-1)/2 +n)

Example :
<abcde12345>
<a1bcde2345> after CircularRotate(A,1,5) ( 5 shifts)
<a1b2cde345> after CircularRotate(A,3,6) ( 4 shifts)
<a1b2c3de45> after CircularRotate(A,5,7) ( 3 shifts)
<a1b2c3d4e5> after CircularRotate(A,7,8) ( 2 shifts)

CircularRotate(A,i,j)
{
char temp=a[j];
while(j>i)
a[j--]=a[j-1];
a[j]=temp;
}

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

YetAnotherCoder, your algorithm is O(n^2), isn't it?

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

i think posible's solution is correct..ne comments ??

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

possible's solution is O(n^2) even if correct.

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

There is an easy O(nlogn) solution and supposedly O(n) is also possible.

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

An O(n logn) time algorithm uses divide and conquer, and the following problem:

Given an array a[1..n], give an algorithm to do an inplace cyclic shift in O(n) time.

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

1 2 3 4 5 c1 c2 c3 c4 c5 - array
0 1 2 3 4 5 6 7 8 9 - current positions
0 2 4 6 8 1 3 5 7 9 - position where it should be placed

start from 1st position
copy the value to temp
see where it should be placed( position 2)
now swap the value at temp and position 2
now again check for where the 2nd element should be place(new position 4) go to position 4 and swap with temp. keep doing this till you come back to position 1.

This is O(n) solution

To get the new position if current position is less than n/2 do 2*i
if current position >= n/2 do 2*i/(n-1)

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

1 2 3 4 5 c1 c2 c3 c4 c5 - array
0 1 2 3 4 5 6 7 8 9 - current positions
0 2 4 6 8 1 3 5 7 9 - position where it should be placed

start from 1st position
copy the value to temp
see where it should be placed( position 2)
now swap the value at temp and position 2
now again check for where the 2nd element should be place(new position 4) go to position 4 and

swap with temp. keep doing this till you come back to position 1.

This is O(n) solution

To get the new position if i less than n/2 do 2*i
if i > n/2 do 2*i/(n-1)

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

666, It might be O(n) algorithm, but it gives the wrong answer.

For most n, you don't even touch all elements. You have the code, try it out for n = 10 to 20 say.

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

the O(n) algorithm without a temp array has a problem, when you move an element to its future place, and then move the element at that place to its future place, ..., until you reach the start place. that is one cycle.
However, one cycle may not cover all elements in the array. some elements are not moved. how to know if some elements are not moved and who they are, that's the problem? we only have constant space to resolve this problem.

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

http://mathworld.wolfram.com/Out-Shuffle.html

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

let n1 n2 n3 n4 c1 c2 c3 c4 be the array..
let us call it num and ch arrays each having 4 elements..
we will swap the last (n=4)/2 elements of num with the first n/2 elements of char
so two new array becomes n1 n2 c1 c2 and n3 n4 c3 c4..n=2
divide and conquor...
O(log n)
this will wrk out for even n's only ..
for odd n's..
n1 n2 n3 c1 c2 c3 suppose..
we willhave to move c1 to n2 using shifting....
n1 c1 | n2 n3 c2 c3...
now apply the prev method on second array,...
(nlogn)

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

here is a simple solution.

1)consider the array as 2 arrays each with size n/2.
2)create another array of size n
3)copy i1,c1,i2,c2,...
4)copy them back to the original array

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

the solution needs to be an "in place algorithm", cant use an additional array

Comment hidden because of low score. Click to expand.
-2

u bastard.. dont u read the question atleast?
Do you think we all are here to read ur stupid answers..

Please read the question and think why ppl are debating on this.. Dont be a dumb or fool man.. come on..

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

Chill out ghost rider . Although I like how you call him a bastard then you say please LOL.
The solution its nlogn.
i1 c1 i2 c2 i3 c3 i4 c4
i1 i2 c1 c2 i3 c3 i4 c4
i1 i2 c1 c2 i3 i4 c3 c4
i1 i2 i3 i4 c1 c2 c3 c4

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.