Microsoft Interview Question Software Engineer / Developers
1of 1 votesort an array of 0,1 and 2.
this is more efficient certainly. I'd love to see this solution coming along atleast once by the interviewee had I been interviewing -- irrespective of whether I allow it or not.
.. and no, i don't think this is a trick. When you know that _to_be_sorted nos. are in a definite known range you *should* use counting sort - you get it done in linear time.
This is Dutch National Flag problem. See following like with explanation of this algorithm
geeksforgeeks.org/?p=8133
int[] a = { 2, 0, 1, 1, 2, 0, 2, 2, 0, 1, 1, 2, 1, 0, 2 };
int lo = 0;
int hi = a.Length - 1;
int mid = 0;
while (mid <= hi)
{
switch (a[mid])
{
case 0:
swap(ref a[lo++], ref a[mid++]);
break;
case 1:
mid++;
break;
case 2:
swap(ref a[mid], ref a[hi--]);
break;
}
}
1. Sort the array treating {0} as one group and {1, 2} as one group.
2. Now again sort the array of 1 & 2.
i = 0;
j = len-1;
// first loop sorts the array with 0 at front and {1, 2} at end
while (i <=j) {
while (a[i] ==0) {
i++;
}
while (a[j] == 1 || a[j] == 2) {
j--;
}
}
// This loop sorts array of 1 & 2
i = j;
j = len-1;
while (i <=j) {
while (a[i] ==1) {
i++;
}
while (a[j] == 2) {
j--;
}
}
So you sort the array in two passes. Time complexity = O(n)
void sort( int V[] , int sz )
{
int lptr=-1;
int rptr=sz;
int curr=0;
while( curr < rptr )
{
if( V[curr]==0 )
{
swap( V[curr] , V[lptr+1] );
lptr++;
continue;
}
if( V[curr]==2 )
{
swap( V[curr] , V[rptr-1] );
rptr--;
continue;
}
curr++ ;
}
return;
}
Did you try to run it ?
Try it on array {0, 1, 1, 2, 1, 0, 0, 2, 1} for example, behaviour is funny
BTW, not clear what are you doing with "1"s.
Here is the correct version
void sort012( int V[] , int sz )
{
int *p0 = V;
int *p1 = p0 + 1;
int *p2 = V + sz-1;
int *pend = p2;
while(p0 != pend && p1 < p2)
{
if( *p0 == 0 )
{
++p0;
if( p0 == p1 )
{
++p1;
}
}
else if(*p0 == 1)
{
swap(*p0, *p1);
++p1;
}
else
{
swap(*p0, *p2);
--p2;
}
}
return;
}
why bother to sort? Ask if the array is read only.
If not, then just write
while ( i <= 2 ) { arr[i] = i; ++i; }
Well, This is Dutch Flag Sort . Counting SOrt is not a good Idea because these numbers 0,1,2 may just be satellite data to elements .
correct, expected, obvious solution is counting sort or radix sort or whatever it's called.
I was asked this in an interview and they accepted my answer.
Sorry didn't have time to run it. Someone comment if I have a bug.
void sort(int* begin, int* end) // end param is STL-style one-past-last-element
{
int counts[3] = {0};
for(int* p = begin; p != end; ++p)
{
assert(0 <= *p && *p <=2);
++counts[*p];
}
for(int i = 0; i < 3; ++i)
{
memsetInt(begin, i, counts[i]);
begin += counts[i];
}
}
inline void memsetInt(int* p, int value, int count)
{
for(int i = 0; i < count; ++i)
p[i] = value;
}
there is one creative way you can do this. Since 1 is the middle value of 1 and 2 choose one of the one's as the pivot and run quick sort just for one iteration.
100210002 - take the second 1 as pivot
after one iteration of quick sort you will get
100000122
now just from the left of the pivot to the start use the normal swapping(2 ptr) mechanism
ie from index 0 to index 6 above which is linear
000001122
this is O(n)
dutch flag
#include <cstdio>
void dutchFlag(int array[], int n)
{
if(array && n)
{
int redIndex=0;
int whiteIndex=0;
int blueIndex=n-1;
while(whiteIndex <= blueIndex)
{
if(array[whiteIndex] == 0)
{
array[whiteIndex] = 1;
array[redIndex] = 0;
redIndex++;
whiteIndex++;
}
else if(array[whiteIndex]==2)
{
array[whiteIndex] = array[blueIndex];
array[blueIndex] = 2;
blueIndex--;
}
else if(array[whiteIndex]==1)
{
whiteIndex ++;
}
else
return;
}
}
}
int main(int argc, char *argv[])
{
int k[]={2,2,2,2,2,2,2,2,2,2,2,1,0};
int n=13;
dutchFlag(k,n);
for(int i=0;i<n;++i)
{
printf("%d,",k[i]);
}
}
Running Time - O(n)
The idea is move all 0s towards to beginning of the array and move all 2s to the end of the array. With that 1s will stay in the center.
public void sort012(int[] a) {
int indexOf0 = 0;
int IndexOf2 = a.length -1;
int i = 1;
int temp = 0;
while(i < a.length ) {
if(a[i] == 0 && i > indexOf0) {
temp = a[i];
a[i] = a[indexOf0];
a[indexOf0] = temp;
indexOf0++;
} else if(a[i] == 2 && i < IndexOf2) {
temp = a[i];
a[i] = a[IndexOf2];
a[IndexOf2] = temp;
IndexOf2--;
} else
i++;
}
}
public static void sortColors(int[] nums) {
int frontIndex = 0, endIndex = nums.length - 1;
for (int i = 0; i < 2; i++) {
while (frontIndex < endIndex) {
if (nums[frontIndex] == i) {
frontIndex++;
} else {
if (nums[endIndex] == i) {
int temp = nums[frontIndex];
nums[frontIndex] = nums[endIndex];
nums[endIndex] = temp;
frontIndex++;
} else {
}
endIndex--;
}
}
endIndex = nums.length - 1;
}
}
public static void sortColors(int[] nums) {
int frontIndex = 0, endIndex = nums.length - 1;
for (int i = 0; i < 2; i++) {
while (frontIndex < endIndex) {
if (nums[frontIndex] == i) {
frontIndex++;
} else {
if (nums[endIndex] == i) {
int temp = nums[frontIndex];
nums[frontIndex] = nums[endIndex];
nums[endIndex] = temp;
frontIndex++;
} else {
}
endIndex--;
}
}
endIndex = nums.length - 1;
}
}
There is a trick you can do with this problem. Since the interviewer did not specify in-place sorting.
- prolific.coder May 20, 20101. First pass through the array and make a count of 0,1,2.
2. Then replace the array elements with those number of 0's, 1's and 2's
This is called counting sort if I am not wrong
This is a trick :) but they would want you do in place.