Yahoo Interview Question
Software Engineer / DevelopersTeam: Search
Country: United States
Interview Type: In-Person
public void threeWayPartition(int[] a, int pivot)
{
int p = 0;
int q = a.length - 1;
for(int i = 0; i <= q;) {
if(a[i] < pivot) swap(a, i++, p++);
else if(a[i] > pivot) swap(a, i, q--);
else i++;
}
}
private void swap(int[] a, int i, int j)
{
int t = a[i];
a[i] = a[j];
a[j] = t;
}
It can be solved using three way partitioning:
#include <stdio.h>
#include <conio.h>
void makeArray(int arr[],int low,int high,int n)
{
int startIndex=0,endIndex=n-1,i,temp;
for(i=0;i<=endIndex;)
{
if(arr[i]<low)
{
temp=arr[i];
arr[i]=arr[startIndex];
arr[startIndex]=temp;
startIndex++;
i++;
}
else if(arr[i]>high)
{
temp=arr[i];
arr[i]=arr[endIndex];
arr[endIndex]=temp;
endIndex--;
}
else
{
i++;
}
}
}
int main()
{
int arr[]={1,14,5,20,4,2,54,20,87,98,3,1,32};
int n=sizeof(arr)/sizeof(arr[0]);
makeArray(arr,20,20,n);
int i;
for(i=0;i<n;i++)
printf(" %d ",arr[i]);
}
the word sort and any order doesn't go together...i am hoping you meant 'arrange' rather than sort and that the element on the left and right of k are not sorted. what the interviewer is asking is exactly what quick sort does after selecting the pivot. in your case the pivot will be k. if we have an external array and couple of pointers then this is what i'll do..in the first pass through the array count number of elements less than k(say x), number of them equal to k (say y) then number of element greater than k will be n - x - y. Now fill the external array from position x to y-1 with k. on the second pass of the array if you find an element less than k fill it in a position less than x and if you find something greater than k fill it at a position greater than = x+y-1
description of quick sort has much more efficient solution.
split pivot with right-most element. remember left as a store position
go flom left to right-1. if current is smaler from pivot swap it with store position.
adjust store position by 1.
Last step swap store and pivot. Viola ! o(n)
This question is a step in a quicksort algorithm. 3-way partitioning.
So, could be done in-place.
/**
*
* time: O(N)
* space: O(1)
*
*/
public static void threeWayPartition( int[] arr, int pivot ){
if( arr == null ){
throw new IllegalArgumentException("Array is NULL");
}
int equalStartIndex = 0;
int greaterStartIndex = 0;
for( int i =0; i < arr.length; i++ ){
// equal case
if( arr[i] == pivot ){
swap(arr, greaterStartIndex, i);
greaterStartIndex++;
}
// less case
else if( arr[i] < pivot ){
swap(arr, greaterStartIndex, i);
swap(arr, equalStartIndex, greaterStartIndex);
greaterStartIndex++;
equalStartIndex++;
}
}
}
This code doesn't ensure that k "should" be in the middle ..if k is greater than all the other numbers,then both k's will be at last which is not required
@kartick vvs: Then isn't it assumed in this example that K does have elements greater than itself in the array? If K is the largest element then of course it s going to be at the right most end. If you want to imagine an empty array to the right of it feel free to so that you see K in the "middle". :P...
1.Take an new array of length equal to that of the original array
2.Place K in the middle of the new array.
3. Take two pointers i, j: i pointing to the beginning of the array and j pointing to end of the array
3. Now start from the start of the old array.
a. If the element is less than k place it in the beginning of the array and increment i
b. If the element is greater than k place it in the end of the array and decrement j
c. If the element is equal to K just maintain a count of elements equal to k
4. Once the old array array is traversed completely, place these elements in the left over places in the new array. These places will be just next to k at the left/right side depending on the current values of i and j
Assumptions: Since we are asked to place K in the middle i am assuming that there are equal number of integers lesser/greater than K
import java.util.Scanner;
class SortArray
{
public static void main(String args[])
{
int m, n, c, d;
Scanner in = new Scanner(System.in);
int max = 0;
int min = 0;
int eql = 0;
int x;
int y;
int z;
System.out.println("Enter the size of an array");
m = in.nextInt();
int a[] = new int[m];
int b[] = new int[m];
System.out.println("Enter the elements of the matrix");
for ( c = 0 ; c < m ; c++ )
a[c] = in.nextInt();
int k;
System.out.println("Enter the search element");
k = in.nextInt();
for(int i = 0;i<m;i++){
if(a[i]>k)
max++;
else if(a[i]<k)
min++;
else
eql++;
}
x = 0;
y= min+eql;
z=min;
for(int i=0;i<m;i++){
System.out.print("value of i"+i+"\n");
if(a[i]<k){
System.out.print("value of a inside 1st loop"+a[i]+"\n");
b[x] = a[i];
x++;
if(x>=min)
continue;
}
else if(a[i]>k){
System.out.print("value of a inside 2st loop"+a[i]+"\n");
b[y] = a[i];
y++;
if(y>=m)
continue;
}
else{
System.out.print("value of a inside 3rd loop"+a[i]+"\n");
b[z]=a[i];
z++;
if(z>=min+eql)
continue;
}
}
for(int i=0;i<m;i++){
System.out.print(b[i]+"\t");
}
}}
import java.util.Scanner;
class SortArray
{
public static void main(String args[])
{
int m, n, c, d;
Scanner in = new Scanner(System.in);
int max = 0;
int min = 0;
int eql = 0;
int x;
int y;
int z;
System.out.println("Enter the size of an array");
m = in.nextInt();
int a[] = new int[m];
int b[] = new int[m];
System.out.println("Enter the elements of the matrix");
for ( c = 0 ; c < m ; c++ )
a[c] = in.nextInt();
int k;
System.out.println("Enter the search element");
k = in.nextInt();
for(int i = 0;i<m;i++){
if(a[i]>k)
max++;
else if(a[i]<k)
min++;
else
eql++;
}
x = 0;
y= min+eql;
z=min;
for(int i=0;i<m;i++){
System.out.print("value of i"+i+"\n");
if(a[i]<k){
System.out.print("value of a inside 1st loop"+a[i]+"\n");
b[x] = a[i];
x++;
if(x>=min)
continue;
}
else if(a[i]>k){
System.out.print("value of a inside 2st loop"+a[i]+"\n");
b[y] = a[i];
y++;
if(y>=m)
continue;
}
else{
System.out.print("value of a inside 3rd loop"+a[i]+"\n");
b[z]=a[i];
z++;
if(z>=min+eql)
continue;
}
}
for(int i=0;i<m;i++){
System.out.print(b[i]+"\t");
}
}}
Solution 1
- dgbfs November 11, 20123 way partitioning
tinyurl.com/bg99tr8
Solution 2
Dutch Flag Sort
en.wikipedia.org/wiki/Dutch_national_flag_problem