Amazon Interview Question
Software Engineer / DevelopersCountry: United States
Interview Type: Phone Interview
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!!!
Wonderful ! I think this is exactly what the interviewer was looking for !!! Thanks.. It has been bugging me ever since.
I guess then you didn't really get the well explained Dutch National Flag write ups you found on the web.
Good luck.
Oh I did.. and I dont think there is much difference between the dutch national flag algorithm and this one. I just liked the way he explained it, hence the vote. Nothing against the dutch algorithm per se :)
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--;
}
}
}
#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
He has used conio , getch so that anyone else can just copy paste and run the program,. dont be so oversmart dude..!
you must be using gcc compiler .... conio.h is not present it this.
remove #include<conio.h> and getch() from above code and then run :) :)
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;
}
(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++;
}
hi jackass..
i think u should increse a2 pointer only if both the condition fails..
try for the following input u algo fail if you are increasing a2 all the times..
5 5 4 5 4 6 5 5 6 6 4
pls correct me if I am wrong
Counting sort is a great answer. Stupid interviewer.
- Anonymous September 23, 2011For 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).