## Microsoft Interview Question for Software Engineer in Tests

• 1
of 1 vote

Country: India
Interview Type: In-Person

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

Use counting sort: space is O(k) which is O(2) here so constant...
or you can use 3 counters to count the number of occurrence of 0, 1, 2 in the given collection, then overwrite the array with those many 0s, 1s, and 2s...
or you can use a hashmap to maintain the counts and basically do the same as above...

Constant space usage and O(N) runtime...

Comment hidden because of low score. Click to expand.
6
of 8 vote

Wiki Dutch National flag for another technique

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

This is the approach interviewer is looking for.

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

``````#include<iostream>
#include<algorithm>
using namespace std;
void swap(int *x ,int *y)
{
int t=*x;
*x=*y;
*y=t;

}
int main()
{
int n;
cin>>n;
int a[n];
for(int i=0;i<n;i++)
cin>>a[i];

int l=0,mid=0,h=n-1;
for(;mid<=h;)
{
if(a[mid]==0)
{
swap(&a[l++],&a[mid++]);
}
else if(a[mid]==1)
++mid;
else if(a[mid]==2)
{
swap(&a[mid], &a[h--]);
}
}
for(int i=0;i<n;i++)
cout<<a[i]<<" " ;
cout<<endl;

return 0;
}``````

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

Will this work for the input {1,01,0,2,2,2,2,2} ?

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

``````sortarray(int arr, int size, int p, int h)
{
int h_index = size -1;
int p_index = 0;

for(int i = 0; i<=h_index;)
{
if(arr[i]<p)
{
swap(arr, i, p_index)
p_index++;
i++;
}
else if(arr[i] >= h)
{
swap(arr, i, h_index);
--h_index;
}
else
++i;
}
}``````

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

Here the function arguments p points 1 and h points to 2. so that all 0 is will be on left, all 2's will be shifted to right and all 1's will be in the middle.

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

Here the function arguments p points 1 and h points to 2. so that all 0 is will be on left, all 2's will be shifted to right and all 1's will be in the middle.

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

DNF Algo for the question asked

``````void DutchNationalFlag012s(int *a, int n) {
int low=0, mid=0, high = n-1;
while (mid<=high) {
switch(a[mid]) {
case 0:
swap(&a[low++], &a[mid++]);
break;
case 1:
mid++;
break;
case 2:
swap(&a[mid], &a[high--]);
break;
}
}
}``````

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

Here is my code to do in a single pass.

``````#include <stdio.h>

void sort_in_a_pass(int arr[], int sz)
{
int s0 = -1, e0 = -1, s1 = -1, s2 = -1, e1 = -1, e2 = -1;
int i;
for(i=0;i<sz;i++)
{
if(arr[i] == 0)
{
if(s0 == -1)
{
s0 = i;
e0 = i;
}
if((i>s1 && s1 != -1))
{
arr[i] = 1;
arr[s1] = 0;
if(s1 < e1)
s1++;
else
{
s1 = i;
e1 = i;
}
}
else if((i>s2 && s2 != -1))
{
arr[i] = 2;
arr[s2] = 0;
if(s2 < e2)
s2++;
else
{
s2 = i;
e2 = i;
}
}
else
e0 = i;
}
else if(arr[i] == 1)
{
if(s1 == -1)
{
s1 = i;
e1 = i;
}
if((i>s2 && s2 != -1))
{
arr[i] = 2;
arr[s2] = 1;
if(s2 < e2)
s2++;
else
{
s2 = i;
e2 = i;
}
}
else
e1 = i;
}
else
{
if(s2 == -1)
{
s2 = i;
e2 = i;
}
e2 = i;
}
}

}

int main(void)
{
int A[] = {2,2,2,1,1,1,0,0,0,1,2,0};
int i;
sort_in_a_pass(A,sizeof(A)/sizeof(int));
for(i = 0; i < sizeof(A)/sizeof(int); i++)
printf(" %d",A[i]);
return 0;
}``````

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

yeah...simple count sort algorithm

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

``````int A[N];
int l=0, r=N-1;
for (int i=0; i<=r; i++) {
while (A[i]!=1) {
if (A[i]==0) swap(i, l++);
if (A[i]==2) swap(i, r--);
}
}``````

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

``````int ott[10]={0,1,0,0,1,2,2,1,0,2};
int n=10;
int firstKnowIndexOftwo    = n-1;
int firstKnownIndexOfZeror = 0;
for(int i=0;i<=firstKnowIndexOftwo;i++){
if(ott[i] == 0){
int temp =  ott[i];
ott[i] = ott[firstKnownIndexOfZeror];
ott[firstKnownIndexOfZeror] = temp;
firstKnownIndexOfZeror++;
}
else if(ott[i] == 2){
int temp =  ott[i];
ott[i] = ott[firstKnowIndexOftwo];
ott[firstKnowIndexOftwo] = temp;
firstKnowIndexOftwo--;
i--;
}
}
for(int j=0;j<n;j++){
printf(" %d ",ott[j]);
}``````

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

``````#include<stdio.h>
#include<stdlib.h>
#include<time.h>
void swap(int *a,int *b)
{
int tmp=(*a);
(*a)=(*b);
(*b)=tmp;
}
int main(int argc,char *argv[])
{
srand(time(NULL));
int A[10]={0,1,0,0,1,2,2,1,0,2};
int *Z,*T;
Z=A;
T=&A[9];
int i=0,flag=1;
for(i;i<10;i++)
{

if((A[i])==2)
{
while((*T)==2)
T--;
if( T > (&A[i]) )
swap(T,(&A[i]));

}
if((A[i])==0)
{
while((*Z)==0)
{
Z++;
}
if(Z < (&A[i]))
swap((&A[i]),Z);
}

}
for(i=0;i<10;i++)
printf("%d",A[i]);``````

}

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

#include <stdio.h>
#include <conio.h>
int dem =0;
void arrangements(int A[], int N)
{
for(int i=0;i<=N;i++)
if(A[i]<A[i+1])
{
A[i]=A[i]+A[i+1];
A[i+1]=A[i]-A[i+1];
A[i]=A[i]-A[i+1];
}
dem++;
if(dem>N) return;
else arrangements(A,N);
}
main()
{
int N=12;
int A[30]={1,0,1,2,2,1,0,0,0,1,2,2};
arrangements(A,N);
for(int i=0;i<N;i++)
printf("%d ", A[i]);
getch();
}

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

``````public class DutchNantionalFlag {
// in array, only 0,1,2 includes
public static void DutchNationalSort(int[] array) {
int count0 = 0;
int count1 = 0;
int count2 = 0;
for (int i = 0; i < array.length; i++) {
if (array[i] == 0)
count0++;
if (array[i] == 1)
count1++;
if (array[i] == 2)
count2++;
}
for (int i = 0; i < count0; i++) {
array[i] = 0;
}
for (int i = count0; i < count0 + count1; i++) {
array[i] = 1;
}
for (int i = count0 + count1; i < count0 + count1 + count2; i++) {
array[i] = 2;
}
for (int i : array) {
System.out.print(i);
}
}

public static void dutchFlagSort(int[] arr, int p, int k) {
int tail = arr.length - 1;
for (int i = 0; i <= tail;) {
if (arr[i] < p) {
i++;
} else if (arr[i] >= k) {
swap(arr, i, tail);
tail--;
} else {
i++;
}
}
for (int i : arr) {
System.out.print(i);
}
}

public static void swap(int[] arr, int i, int j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}

public static void main(String[] args) {
int[] array = { 1, 2, 1, 2, 0, 1, 2, 0, 0, 2, 1, 0 };
DutchNationalSort(array);
dutchFlagSort(array,1,2);
}

}``````

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

Please let me know what is the time complexity of this approach

``````public void SortArray(int[] a)
{
int temp;
int i = 0;
int j = 0;

// swap array element for 0
for (i = 0, j = a.Length - 1; i < j;)
{
if (a[i] == 0)
{
i++;
}
else if ((a[i] != 0 && a[j] == 0))
{
temp = a[i];
a[i] = a[j];
a[j] = temp;
i++;
j--;
}
else if (a[i] != 0 && a[j] != 0)
{
j--;
}

}

// swap array element for 1
for (i = i + 1, j = a.Length - 1; i < j; )
{
if (a[i] == 1)
{
i++;
}
else if ((a[i] != 1 && a[j] == 1))
{
temp = a[i];
a[i] = a[j];
a[j] = temp;
i++;
j--;
}
else if (a[i] != 1 && a[j] != 1)
{
j--;
}
}
}``````

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

Solution O(n)

void Separation012(int *arr, int size)
{

int i = 0;
int j = size - 1;

while(i < j)
{
if(arr[i] == 0)
i++;
else if(arr[j] > 0)
j--;
else
{
swap(&arr[i],&arr[j]);
i++;
j--;
}

}

j = size - 1;
while(i < j)
{
if(arr[i] == 1)
i++;
else if(arr[j] > 1)
j--;
else
{
swap(&arr[i],&arr[j]);
i++;
j--;
}

}

return;
}

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

``````void Separation012(int *arr, int size)
{

int i = 0;
int j = size - 1;

while(i < j)
{
if(arr[i] == 0)
i++;
else if(arr[j] > 0)
j--;
else
{
swap(&arr[i],&arr[j]);
i++;
j--;
}

}

j = size - 1;
while(i < j)
{
if(arr[i] == 1)
i++;
else if(arr[j] > 1)
j--;
else
{
swap(&arr[i],&arr[j]);
i++;
j--;
}

}

return;
}``````

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.