Microsoft Interview Question for Software Engineer in Tests


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

- JustCoding October 22, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
6
of 8 vote

Wiki Dutch National flag for another technique

- eugene.yarovoi October 22, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

This is the approach interviewer is looking for.

- Akshat January 25, 2013 | Flag
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;
}

- rajesh pandey October 22, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Anonymous January 03, 2013 | Flag
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;
    }
}

- Manikanta October 22, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- Manikanta October 22, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- Manikanta October 22, 2012 | Flag
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;
		}
	}
}

- crystal.rishi2 October 22, 2012 | Flag Reply
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;
}

- Samrat October 22, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

yeah...simple count sort algorithm

- The Artist October 22, 2012 | Flag Reply
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--);
    }
}

- pckben October 22, 2012 | Flag Reply
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]);
    }

- Madhu S. Kapoor October 22, 2012 | Flag Reply
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]);

}

- grvtech17 October 23, 2012 | Flag Reply
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();
}

- Nguyen Anh November 08, 2012 | Flag Reply
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 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);
	}

}

- Kevin March 04, 2013 | Flag Reply
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--;
                }
            }
        }

- James April 01, 2013 | Flag Reply
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;
}

- Sidhartha May 02, 2013 | Flag Reply
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;
}

- Sidhu May 02, 2013 | Flag Reply


Add a Comment
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.

Learn More

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.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More