CareerCup

Counting sort is a great answer. Stupid interviewer.

For a swapping based solution, one thing you can do is make a pass to find out what the three numbers are, and then use the Dutch National Flag solution (do a websearch and you should find something there).

Assumption: The three numbers are known
suppose the three distinct numbers are x1,x2,x3
lets assume that after sorting these three these will be x1<x2<x3
Solution can be achieved in two runs through the array and this will be O(n)
In the first run get x1 always to the left of the array by swapping whenever x1 is encountered
Then in the second run, come from right to left maintaining x3 always at the end by swapping whenever x3 is encountered
finally x2 will end up in middle of the array
Eg:55454655664
after the first run the above approach will return
44455655665
after second run from behind the above approach will return
44455555666

Hope this example explains!!!


If the three number are not known, run another loop which determines the three :) (O(3n))
Please suggest any better algo if any!!!

the program for the above problem. this a variant of dutch flag problem proposed by Dijkstra. so this program also works for dutch problem.

public static void dutchflag(int [] a){
	int min = Integer.MAX_VALUE;
	int max = Integer.MIN_VALUE;
	int n = a.length;
	for(int i=0; i<n; i++){
		if(a[i] < min){
			min = a[i];
		}
		if(a[i] > max){
			max = a[i];
		}
	}
		
	int i = 0, j = n-1;
	for(int k=0; k<n; k++){
		if(a[k] == min){
			int temp = a[k];
			a[k] = a[i];
			a[i] = temp;
			i++;
		}
	}
	for(int k=n-1; k>=0; k--){
		if(a[k] == max){
			int temp = a[k];
			a[k] = a[j];
			a[j] = temp;
			j--;
		}
	}
}

use 6 pointers 2 for each number start and end of number sequence in array...

#include<iostream.h>
#include<conio.h>
#include<string.h>
void swap(char *,char *);
int main()
{
char str[20];
cout<<"Enter the string : \t";
gets(str);
int top,bottom,index,length;
length=strlen(str);
index=0;
top=0;
bottom=length-1;
while(index<length&&bottom>=index)
{
if(str[index]=='1')
{swap(&str[index++],&str[top++]);
}
else if(str[index]=='3')
{swap(&str[index],&str[bottom--]);
}
else
index++;
}
cout<<endl<<"formatted string is : "<<str;
getch();
return 0;
}
void swap(char *a, char *b)
{
int temp;
temp=*a;
*a=*b;
*b=temp;
}


This code is for three distinct no 0 ,1 ,2.. you can customize your program after knowing all three distinct no in O(n)
Basically it is dutch national flag problem.. en.wikipedia.org/wiki/Dutch_national_flag_problem

This is an example of Dutch National Flag problem.

Do people even read the previous comments?

The very first comment mentioned the Dutch National Flag. Then we have at least two after that... what's up with that?

@sunilkumarmax: The three numbers are not known in advance, but you can easily find them while traversing the list.

No need for an extra pass to find all the elements.
Here is the "algo", assumption: there are three distinct numbers:

swap(A,n)
{
  f=0,s=0,i=1
  while(i<n)
  {
    if(A[i] == A[s]) continue;
  
    if(A[i] > A[s])  s=i; 

     if(A[i]<A[s])
     {
       swap(A[s++],A[i])

       if(A[s-1]<A[f])
         swap(A[f++],A[s-1])

     }
 }
}

here is a modified wiki code-

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

#include "stdafx.h"
#include <stdlib.h>
#include <iostream>
using namespace std;

void swap (int &a, int &b){
int temp=0;
temp=a;
a=b;
b=temp;
}

void print(int data[]){
for(int i=0;i<10;i++)
cout<<data[i]<<"\t";
cout<<endl;
}

void threeWayPartition(int data[], int size, int low, int high) {

int p = -1;
int q = size;
for (int i = 0; i < q;) {
if (data[i] <= low) {
swap(data[i], data[++p]);
} else if (data[i] >= high) {
swap(data[i], data[--q]);
} else {
++i;
}
}
}

int _tmain(int argc, _TCHAR* argv[])
{
int data[]={6,6,4,4,5,6,5,4,5,6};
threeWayPartition(data, 10,4,6);

print(data);
return 0;
}

How about using the Max heap , where we assumed that x1 is the max,
x1
/ \
x2 x3
Now we need to compare x2 ,x3 with x1
if x2 > x1 then swap (x2,x1)...
now compare x2 with x3
if x3 > x2 then swap (x3,x2)
that n-1 complexity

(1) Find the distinct elements and put them in b1, b2, b3;
(2) Keep 3 pointers a1 = 0, a2 = 0, a3 = length - 1;

for(int i = 0 ; i < length ; i++)
{
if( arr[a2] == b1 )
{
swap(arr[a2], arr[a1])
a1++;
}
else if( arr[a2] == b3 )
{
swap(arr[a2], arr[a3])
a3--;
}
a2++;
}