Amazon Interview Question
Software Engineer / DevelopersCountry: United States
Interview Type: Phone Interview
Normal algorithm won't work if pivot is repeated. One more array is needed
def lowPivotHighSort(array, pivot)
smaller = []
equal = []
bigger = []
return nil if array.index(pivot).nil?
array.each do |elem|
smaller << elem if elem < pivot
equal << elem if elem == pivot
bigger << elem if elem > pivot
end
return smaller + equal + bigger
end
public static void partition(int[] A, int key )
{
int i;
for(i=0; i<A.length; i++)
{
if(A[i]==key)
{
int temp = A[0];
A[0] = A[i];
A[i]= temp;
break;
}
}
if(i >= A.length)
{
System.out.println("KEY NOT FOUND");
return;
}
// now A[0] is the pivot
i =1;
int j = A.length-1;
while(i<j)
{
while(i< A.length-1 && A[i]<=A[0])
i++;
while(j > 0 && A[j] > A[0])
j--;
int temp = A[j];
A[j] = A[i];
A[i] = temp;
}
if(i!=j)
{
int temp = A[j];
A[j] = A[i];
A[i] = temp;
}
int temp = A[j];
A[j] = A[0];
A[0] = temp;
}
quick sort partition function
#include <stdio.h>
int a[] = {22, 2,3,3,0,1,4,5,23,215,215};
void swap(int a[], int left, int right)
{
int temp = a[left];
a[left] = a[right];
a[right] = temp;
}
int partition(int key)
{
int left=0;int right=sizeof(a)/sizeof(a[0])-1;
int key_element;int copy = right--;
if(key < 1 && key > sizeof(a)/sizeof(a[0]))
return -1;
else
key_element = a[key-1];
/*put the key in the end of array*/
swap(a, key-1, sizeof(a)/sizeof(a[0])-1);
while(left<right){
while(a[left]<=key_element && left <= right){
left++;
}
while(a[right]>key_element && right > left){
right--;
}
if(left >= right)
break;
swap(a, left, right);
}
if(left > right){
}
else
swap(a, copy, left);
return left;
}
int main()
{
int key, i;
scanf("%d", &key);
printf("key index now %d\n", partition(key));
for(i=0;i<sizeof(a)/sizeof(a[0]);i++)
printf("%4d", a[i]);
}
quick sort partitioning wont work here.......
a different approach is taken....
1).take two pointers,one to starting(say i) and other to ending(say j)...
2). just iterate through the array(say k), if you find element equal to key just increment(k++)...
3).if you find element <key swap(a[i] ,a[k]),and increment i...
4).if you find element greater than key swap(a[k],a[j]) and decrement j(j--).
but note that in this case you must not increment k,as u have a new element at position k,which u have not traversed..
#include<iostream>
using namespace std;
void swap(int &a,int &b)
{
int t;
t=a;
a=b;
b=t;
}
void display(int a[],int n)
{
for(int i=0;i<n;i++)
{
cout<<a[i]<<" ";
}
cout<<endl;
}
void arrange(int a[],int n,int key)
{
int i=0,j=n-1,k=0;
while(k<j)
{
// cout<<"k="<<k<<" ";
if(a[k]<key)
{
swap(a[k],a[i]);
i++;
}
else if(a[k]>key)
{
swap(a[k],a[j]);
j--;
k=k-1;
}
k++;
// display(a,n); uncomment these lines to see what happens at each iteration
}
}
int main()
{
int n,*a,key;
cin>>n;
a=new int[n];
for(int i=0;i<n;i++)
{
cin>>a[i];
}
cout<<"Enter the key. \n";
cin>>key;
arrange(a,n,key);
display(a,n);
return 0;
}
And the solution for it:
public void threeWayPartition(int[] arr, int key) {
int low = 0;
int high = arr.length - 1;
for (int lookAt = 0; lookAt <= high;) {
if (arr[lookAt] < key) {
swap(arr, lookAt++, low++);
} else if (arr[lookAt] > key) {
swap(arr, lookAt, high--);
} else {
++lookAt;
}
}
void swap(int[] arr, int p1, int p2) {
int temp = arr[p1];
arr[p1] = arr[p2];
arr[p2] = temp;
}
}
This problem can be solved by using an approach of binary search:
a. Every time the array is divided into 2 parts and then solve for the left half and the right half as:
b. If the current element is less than the key then enter it into one array and if the current element is greater then enter it into second array. If both are equal then enter into the 2nd array. At last combine the or concatenate the two arrays .Thus the solution O(n). You can test it:
#include <stdio.h>yuh
#include <stdlib.h>
void numberPrintLess(int arr[],int arr1[],int arr2[],int low,int high,int *left,int *right,int key)
{
if(low==high)
{
if(key<arr[low])
{
arr2[*right]=arr[low];
*right=*right+1;
}
else
{
arr1[*left]=arr[low];
*left=*left+1;
}
return;
}
if(low+1==high)
{
if(key<arr[low]&&key<arr[high])
{
arr2[*right]=arr[low];
*right=*right+1;
arr2[*right]=arr[high];
*right=*right+1;
}
else if(key>arr[low]&&key>arr[high])
{
arr1[*left]=arr[low];
*left=*left+1;
arr1[*left]=arr[high];
*left=*left+1;
}
else if(key>arr[low]&&key<arr[high])
{
arr1[*left]=arr[low];
*left=*left+1;
arr2[*right]=arr[high];
*right=*right+1;
}
else if(key<arr[low]&&key>arr[high])
{
arr1[*left]=arr[high];
*left=*left+1;
arr2[*right]=arr[low];
*right=*right+1;
}
else if(key==arr[low]&&arr[low]<arr[high])
{
arr1[*left]=arr[low];
*left=*left+1;
arr2[*right]=arr[high];
*right=*right+1;
}
else if(key==arr[low]&&arr[high]<arr[low])
{
arr1[*left]=arr[high];
*left=*left+1;
arr2[*right]=arr[low];
*right=*right+1;
}
else if(key==arr[high]&&arr[high]<arr[low])
{
arr1[*left]=arr[high];
*left=*left+1;
arr2[*right]=arr[low];
*right=*right+1;
}
else if(key==arr[high]&&arr[low]<arr[high])
{
arr1[*left]=arr[low];
*left=*left+1;
arr2[*right]=arr[high];
*right=*right+1;
}
else if(key==arr[low]&&arr[high]==arr[low])
{
arr1[*left]=arr[high];
*left=*left+1;
arr1[*left]=arr[low];
*left=*left+1;
}
}
else
{
int mid=low+(high-low)/2;
if(arr[mid]<key)
{
arr1[*left]=arr[mid];
*left=*left+1;
}
else if(arr[mid]>key)
{
arr2[*right]=arr[mid];
*right=*right+1;
}
else if(arr[mid]==key)
{
arr2[*right]=arr[mid];
*right=*right+1;
}
numberPrintLess(arr,arr1,arr2,low,mid-1,left,right,key);
numberPrintLess(arr,arr1,arr2,mid+1,high,left,right,key);
}
return;
}
void concatenate(int arr1[],int arr2[],int *left,int *right)
{
int i,arr[25];
for(i=0;i<*left ;i++)
{
arr[i]=arr1[i];
}
int j=i;
for(i=0;i<*right;i++)
{
arr[j]=arr2[i];
j++;
}
for(i=0;i<j;i++)
printf(" %d ",arr[i]);
}
int main()
{
int arr[]={0,-1,-2,0,3,5};
int arr1[25],arr2[25];
int n=sizeof(arr)/sizeof(arr[0]);
int left=0;
int right=0;
numberPrintLess(arr,arr1,arr2,0,n-1,&left,&right,0);
concatenate(arr1,arr2,&left,&right);
}
#include <stdio.h>
main() {
int a[] = { 0, -1, -2, 2, 0, 3, 5},n=7,i,j,k,temp;
i = k = 0;
j = n-1;
while(i<j) {
if(a[i] > k) {
temp = a[i];
a[i] = a[j];
a[j] = temp;
j--;
}
else
i++;
}
printf("Result is : \n");
for(i=0;i<n;i++)
printf("%d ",a[i]);
printf("\n");
}
Hey it is not working correctly for key 0 the output is 0 -1 -2 0 3 5 2 which is completely wrong..!!
public int[] returnArray(int[] arr, int key){
int count = 0;
int count1 = 0;
int[] arr1 = new int[arr.length];
for(int ij = 0 ; ij < arr.length; ij++){
if (arr[ij] < key)
count++;
else if (arr[ij] == key)
count1++;
}
arr1[(count + count1) - 1] = key;
int p = 0, j = (count + count1) - 1, k = j + 1;
for(int i = 0; i < arr.length; i++){
if (arr[i] < key){
arr1[p] = arr[i];
p++;
}
else if (arr[i] > key){
arr1[k] = arr[i];
k++;
}
else if (arr[i] == key){
if (count1 == 1)
{
}
else{
arr1[j-1] = arr[i];
count1--;
}
j--;
}
}
return arr1;
}
public class ArrageNumberByKey {
public static int[] arrrageNumberByKey(int[] array , int key)
{
int length = array.length;
int[] returnArray = new int[array.length];
// if(length%2 == 0)
// {
//
// }
int currentKeyIndex = -1;
for (int i=0; i<length ;i++)
{
if (array[i] < key)
{
currentKeyIndex++;
returnArray[currentKeyIndex] = array[i];
}
}
// returnArray[currentKeyIndex]=key;
for (int i=0; i <length; i++)
{
if (array[i] >= key)
{
currentKeyIndex++;
returnArray[currentKeyIndex] =array[i];
}
}
return returnArray;
}
public static void switchPos(int[] arr, int idx1, int idx2)
{
int tmp = arr[idx1];
arr[idx1] = arr[idx2];
arr[idx2] = tmp;
}
public static void main(String[] arg)
{
int[] array = {-1,0,0,-3,3,4,5};
int[] returnArray = arrrageNumberByKey(array, 0);
for (int i=0; i< returnArray.length ; i++)
{
System.out.println("value "+returnArray[i]);
}
}
}
import java.util.Arrays;
public class MainGeneric {
public static void main(String[] args) {
int[] a = {2, 3, -1, 0, -2 , 1, 8, 10};
int[] tobefilled = new int[a.length];
int right = a.length-1 , left = 0;
int key = 8;
for(int i = 0 ; i < a.length ; i++)
if(a[i] < key){
tobefilled[left] = a[i];
left++;
}else if(a[i] > key){
tobefilled[right] = a[i];
right--;
}
tobefilled[left] = key;
System.out.println(Arrays.toString(tobefilled));
}
}
int key = 0;
arr = { 0, -1, -2, 2, 0, 3, 5},
count =0;
for(int i = 0 ; i < a.length ; i++)
if(a[i] < key){
result[left] = a[i];
left++;
}else if(a[i] > key){
result[right] = a[i];
right--;
} else
{
Count++;
}
for(int i = left ; i < count ; i++)
result[left] = key;
System.out.println(Arrays.toString(result));
A simple way may be:
1. In the first scan - Find all positions of given key. And number of elements less than key. Now you know
- (a) first position of the key in the result array (with key in the middle and lesser ones on left etc..)
- (b) last position of the key in the result array
2. Move all key elements to middle [from indexes (a) to (b)]
3. Now keep two pointers one always pointing to lesser ones and other to greater ones and swapping at every contradiction.
Each step is O(n).
public static void keyArr(int[] arr,int key){
int lowKeyIndex=-1,highKeyIndex=-1;/* LowKey and HighKey used to indicate minimum and maximum key positions in the array*/
int maxIndex=arr.length-1/*Length of array to process*/,temp=0;
for(int index=0;(index<arr.length&&index<=maxIndex);)
{
/* If Current element is greater than Key..Just swap last element with current element..
* Repeat the iteration for the current element..Reduce Max Element Index by 1..
* E.g. [-1,8,0,2,3] Key=0
* Current Index is 1..So current element is 8
* Output [-1,3,0,2,8] maxIndex=3
*/
if(arr[index]>key){
temp=arr[index];
arr[index]=arr[maxIndex];
arr[maxIndex]=temp;
maxIndex--;
}
/* If Current element is equal to Key..Note down the key index in lowKeyIndex for first found key..
* For the consequent keys, place the keys together and increment the highKeyIndex..
* E.g. [-1,-8,0,2,0,3] Key=0
* Current Index is 4..So current element is 0..lowKeyIndex=2
* Output [-1,-8,0,0,2,3] highKeyIndex=3 */
else if(arr[index]==key){
if(lowKeyIndex!=-1){
highKeyIndex=(highKeyIndex!=-1)?(highKeyIndex+1):(lowKeyIndex+1);
temp=arr[highKeyIndex];
arr[highKeyIndex]=arr[index];
arr[index]=temp;
}
else
lowKeyIndex=index;
index++;
}
else{
/* If Current element is less than but found after key is found...Place the current element in lowkeyIndex position..
* Place the element next to highKeyIndex to current postion and put key in the highKeyIndex+1 position
* Increment lowKeyIndex and highKeyIndex
* E.g. [-1,-8,0,0,0,2,4,-3] Key=0
* Current Index is 7..So current element is -3..lowKeyIndex=2 highKeyIndex=4
* Output [-1,-8,-3,0,0,0,2,4] lowKeyIndex=3 highKeyIndex=5 */
if((index>lowKeyIndex)&&(lowKeyIndex!=-1)){
temp=arr[index];
if(maxIndex==-1)maxIndex=lowKeyIndex+1;
arr[index]=arr[highKeyIndex+1];
arr[lowKeyIndex]=temp;
arr[highKeyIndex+1]=key;
lowKeyIndex+=1;
highKeyIndex+=1;
index++;
}
}
}
for(int i=0;i<arr.length;i++)
System.out.print(arr[i]+" ");
}
quick sort partitioning wont work here.......
a different approach is taken....
1).take two pointers,one to starting(say i) and other to ending(say j)...
2). just iterate through the array(say k), if you find element equal to key just increment(k++)...
3).if you find element <key swap(a[i] ,a[k]),and increment i...
4).if you find element greater than key swap(a[k],a[j]) and decrement j(j--).
but note that in this case you must not increment k,as u have a new element at position k,which u have not traversed..
#include<iostream>
using namespace std;
void swap(int &a,int &b)
{
int t;
t=a;
a=b;
b=t;
}
void display(int a[],int n)
{
for(int i=0;i<n;i++)
{
cout<<a[i]<<" ";
}
cout<<endl;
}
void arrange(int a[],int n,int key)
{
int i=0,j=n-1,k=0;
while(k<j)
{
// cout<<"k="<<k<<" ";
if(a[k]<key)
{
swap(a[k],a[i]);
i++;
}
else if(a[k]>key)
{
swap(a[k],a[j]);
j--;
k=k-1;
}
k++;
// display(a,n); uncomment these lines to see what happens at each iteration
}
}
int main()
{
int n,*a,key;
cin>>n;
a=new int[n];
for(int i=0;i<n;i++)
{
cin>>a[i];
}
cout<<"Enter the key. \n";
cin>>key;
arrange(a,n,key);
display(a,n);
return 0;
}
static void Main(string[] args)
{
int[] a = new int[] { 0, 0, -1, -2, 2, 0, 3, 5, 0, 0, 0, 10, -1 };
ArrangeByKey(a, 0);
}
static void ArrangeByKey(int[] a, int key)
{
if (a == null)
return;
int i = 0;
int j = a.Length - 1;
int i0 = -1;
while (i <= j)
{
while (a[i] <= key)
{
if (a[i] == key && i0 == -1)
i0 = i;
else if (a[i] < key && i0 != -1)
{
Swap(a, i0, i);
i0++;
}
i++;
}
while (a[j] > key)
{
j--;
}
if (i <= j)
{
Swap(a, i, j);
}
}
}
static void Swap(int[] a, int i, int j)
{
int tmp = a[i];
a[i] = a[j];
a[j] = tmp;
}
static void Main(string[] args)
{
int[] a = new int[] { 0, 0, -1, -2, 2, 0, 3, 5, 0, 0, 0, 10, -1 };
ArrangeByKey(a, 0);
}
static void ArrangeByKey(int[] a, int key)
{
if (a == null)
return;
int i = 0;
int j = a.Length - 1;
int i0 = -1;
while (i <= j)
{
while (a[i] <= key)
{
if (a[i] == key && i0 == -1)
i0 = i;
else if (a[i] < key && i0 != -1)
{
Swap(a, i0, i);
i0++;
}
i++;
}
while (a[j] > key)
{
j--;
}
if (i <= j)
{
Swap(a, i, j);
}
}
}
static void Swap(int[] a, int i, int j)
{
int tmp = a[i];
a[i] = a[j];
a[j] = tmp;
}
static void Main(string[] args)
{
int[] a = new int[] { 0, 0, -1, -2, 2, 0, 3, 5, 0, 0, 0, 10, -1 };
ArrangeByKey(a, 0);
}
static void ArrangeByKey(int[] a, int key)
{
if (a == null)
return;
int i = 0;
int j = a.Length - 1;
int i0 = -1;
while (i <= j)
{
while (a[i] <= key)
{
if (a[i] == key && i0 == -1)
i0 = i;
else if (a[i] < key && i0 != -1)
{
Swap(a, i0, i);
i0++;
}
i++;
}
while (a[j] > key)
{
j--;
}
if (i <= j)
{
Swap(a, i, j);
}
}
}
static void Swap(int[] a, int i, int j)
{
int tmp = a[i];
a[i] = a[j];
a[j] = tmp;
}
static void Main(string[] args)
{
int[] a = new int[] { 0, 0, -1, -2, 2, 0, 3, 5, 0, 0, 0, 10, -1 };
ArrangeByKey(a, 0);
}
static void ArrangeByKey(int[] a, int key)
{
if (a == null)
return;
int i = 0;
int j = a.Length - 1;
int i0 = -1;
while (i <= j)
{
while (a[i] <= key)
{
if (a[i] == key && i0 == -1)
i0 = i;
else if (a[i] < key && i0 != -1)
{
Swap(a, i0, i);
i0++;
}
i++;
}
while (a[j] > key)
{
j--;
}
if (i <= j)
{
Swap(a, i, j);
}
}
}
static void Swap(int[] a, int i, int j)
{
int tmp = a[i];
a[i] = a[j];
a[j] = tmp;
}
i came up this solution it's partially correct someone please help me out to correct the whole solution...
Test case sucess:
test case 1: 0 ,-1,-2,2,0,3,5 n=7 key =0
test case 2: 1 ,7,5,8,3,9,5 n=7 key =5
test case 3: 1 ,6,2,4,3,7 n=6 key =3
Test case failure:
test case 4: 1 ,7,5,8,3,9,2 n=7 key =5
test case 5: 1 ,6,2,4,3,2 n=6 key =3
#include<iostream.h>
#include<conio.h>
void main()
{
clrscr();
int arr[50];
int n,key,x,i=0,j=0;
cout<<"Enter n and key:";
cin>>n>>key;
j=n-1;
cout<<"Enter array:";
do
{
cin>>x;
if(x<key)
{
arr[i]=x;
i++;
}
if(x==key)
{}
else
{
arr[j]=x;
j--;
}
}while(j>=i);
//arr[i]=arr[j]=key;
for(i=0;i<n;i++)
cout<<arr[i] <<" ";
getch();
}
*errr wrong code
please help me out with this one....
#include<iostream.h>
#include<conio.h>
void main()
{
clrscr();
int arr[50];
int n,key,x,i=0,j=0;
cout<<"Enter n and key:";
cin>>n>>key;
j=n-1;
cout<<"Enter array:";
do
{
cin>>x;
if(x<=key)
{
arr[i]=x;
i++;
}
else
{
arr[j]=x;
j--;
}
}while(j>=i);
for(i=0;i<n;i++)
cout<<arr[i] <<" ";
getch();
}
Do a linear scan and count how many items < key.
Place the key in the right index in the array (maybe use a separate output array).
Maintain 3 pointers - 1 at the 1st position of the array that's less than the key (unless key is the 1st), another index next position after the key and 3rd index on the key.
Do another linear scan and if element is < place at the position of 1st index & increment that index. Same if element > key, use 2nd index. If element equal, place it before or right after the 3rd index.
This will be O(n).
sorry for a little messy code
public static void partition(int []arr, int k)
{
if(arr == null || arr.length == 0)
return;
int left = 0, right = arr.length-1;
int _kIdxLeft = -1, _kIdxRight = arr.length;
while(left < right) {
while(arr[left] <= k) {
if(arr[left] == k)
switchPos(arr, left++, ++_kIdxLeft);
else
left++;
}
while(arr[right] >= k) {
if(arr[right] == k) {
switchPos(arr, right--, --_kIdxRight);
} else {
right--;
}
}
switchPos(arr, left++, right--);
}
while(_kIdxLeft >= 0) {
switchPos(arr, --left, _kIdxLeft--);
}
while(_kIdxRight < arr.length) {
switchPos(arr, ++right, _kIdxRight++);
}
}
public static void switchPos(int[] arr, int idx1, int idx2)
{
int tmp = arr[idx1];
arr[idx1] = arr[idx2];
arr[idx2] = tmp;
}
#include <stdio.h>
#include <stdlib.h>
int a[] = { 0, -1, -2, 2, 0, 3, 5};
int main()
{
int key,i;
printf("enter the key:");
scanf("%d",&key);
arrange(key);
}
void arrange(int key)
{
int n = sizeof(a)/sizeof(a[0]);
int i,j,left = 0,right= n-1;
int temp;
for(i=0;i<n;i++)
{
if(a[i]==key)
{
temp = a[right];
a[right] = a[i];
a[i] = temp;
break;
}
}
if(i>=n)
{
printf("key not found\n");
exit(0);
}
int x = a[right];
i = left - 1;
int k;
for(j=left;j<right-1;j++)
{
if(a[j]<=x)
{
i++;
k = a[i];
a[i] = a[j];
a[j] = k;
}
}
k = a[i+1];
a[i+1] = a[right];
a[right] = k;
printf("after arranging the array is:\n");
for(j=0;j<n;j++)
{
printf("%d\t",a[j]);
}
printf("\n");
}
Partition function of quick sort
- Anonymous June 30, 2013