Microsoft Interview Question
Software Engineer in TestsCountry: India
Interview Type: In-Person
#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;
}
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;
}
}
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.
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;
}
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]);
}
#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]);
}
#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();
}
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 head = 0;
int tail = arr.length - 1;
for (int i = 0; i <= tail;) {
if (arr[i] < p) {
swap(arr, i, head);
head++;
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);
}
}
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--;
}
}
}
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;
}
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;
}
Use counting sort: space is O(k) which is O(2) here so constant...
- JustCoding October 22, 2012or 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...