Yahoo Interview Question
Software Engineer / DevelopersI em not able to get how the merging would work ..
because for checking the distance to be minimum
You have to go through all the pairs and while merging you will go linearly and would be able to look up all the possible pairs.
/*! Find the minimum triplet given three sorted arrays
Given with three sorted arrays ( in ascending order), you are required to find a triplet ( one element from each array) such that distance is minimum.
Distance is defined like this :
If a[i], b[j] and c[k] are three elements then distance=max(abs(a[i]-b[j]),abs(a[i]-c[k]),abs(b[j]-c[k]))"
Algorithm:
Merge these three arrays using a merge from merge sort approach. While merging check for the distance and save the ones that keep it min.
The distance between consecutives is always min.
NOTE:: Code was not written in a quick and dirty way.
Complexity:: O(i+j+k)
*/
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
template<typename T, int size>
int length(T(&)[size]){return size;}
int distance (int a,int b,int c){
return max(max(abs(a-b),abs(a-c)),abs(b-c));
}
int main(){
vector<int> mergeArray;
//initialization
int a[] = {-33,-24,-14,-1,4,5,6,7,8,35,106,109,112,128,224,228,335,439,1100,1120,1302,4019,4299,5666,5999,8888,9999,10000};
int b[] = {-4,-3,1,6,19,33,64,79,84,112,15,24,35,39,100,120,127,1002,4001,4002};
int c[] = {-1,2,4,8,16,32,64,128,256,512,1024,2048,4096,8192,16384};
int a_len= length(a),b_len= length(b),c_len= length(c);
int maxElement = max(max(a[a_len-1],b[b_len-1]),c[c_len-1])+1; //max of all arrays
int amin = a[0], bmin = b[0], cmin = c[0]; //initial minimums
int a_curr,b_curr,c_curr,a1,b1,c1,currMin,currDistance,minDistance=maxElement+1;
int i=0,a_indx=0,b_indx=0,c_indx=0; //counters
long numOfLoopings = 0;
while(true){
numOfLoopings++;
//!Step1: get current element, if not max, current is set to max when end of array is reached in Step-4
if(a_curr!=maxElement) a_curr = a[a_indx];
if(b_curr!=maxElement) b_curr = b[b_indx];
if(c_curr!=maxElement) c_curr = c[c_indx];
//!Step2: Find current minimum element that is to be inserted into the final mergeArray
currMin = min(min(a_curr,b_curr),c_curr);
if(currMin==maxElement) break; //if min element is maxElement then all arrays have reached end
mergeArray.push_back(currMin); //push into merging array
i = (currMin==a_curr)?1:((currMin==b_curr)?2:3); //i=1 if a , i=2 if b , i=3 if c
//!Step3: Find the distance between the consecutive triplet.
a1=((a_curr==maxElement)?a[a_len-1]:a_curr);
b1=((b_curr==maxElement)?b[b_len-1]:b_curr);
c1=((c_curr==maxElement)?c[c_len-1]:c_curr);
currDistance = distance(a1,b1,c1);
if(minDistance>currDistance) {amin=a1;bmin=b1;cmin=c1;
// cout<<"Dist:: "<<currDistance<<"[ "<<a1<<","<<b1<<","<<c1<<"]"<<endl;
minDistance=currDistance;} //if distance is less than store values
//!Step4: Increment the array index that has current min and if out-of-bounds then set current element to maxElement+1 of all arrays
if(i==1)if(a_indx<(a_len-1)) ++a_indx;else a_curr=maxElement;
if(i==2)if(b_indx<(b_len-1)) ++b_indx;else b_curr=maxElement;
if(i==3)if(c_indx<(c_len-1)) ++c_indx;else c_curr=maxElement;
}
cout<<" Minimum Triplet:: [A: "<<amin<<" , B: "<<bmin<<" ,C: "<<cmin<<"]"<<endl;
cout<<" Merged Array:: ";
for(int i=0;i<mergeArray.size();++i)cout<<" "<<mergeArray[i];
cout<<endl<<" Number of times the loop was run:: "<<numOfLoopings-1<<". which is O("<<a_len<<"+"<<b_len<<"+"<<c_len<<") = O("<<a_len+b_len+c_len<<")";
}
/// Using Merge Sort Method
int run()
{
/// (1<<31)-1 is an append item
int A[] = {2, 4, 6, 8, (1<<31) - 1};
int B[] = {1, 3, 5, 70, (1<<31) - 1};
int C[] = {40, 50, 60, 70, 80, (1<<31) - 1};
int sz1 = sizeof(A)/sizeof(A[0]);
int sz2 = sizeof(B)/sizeof(B[0]);
int sz3 = sizeof(C)/sizeof(C[0]);
int i = 0, j = 0, k = 0;
int minx = (1 << 31) - 1;
while((i < sz1) && (j < sz2) && (k < sz3)) {
int k1 = A[i], k2 = B[j], k3 = C[k];
int m = abs(k1 - k2);
m = m < abs(k2 - k3) ? abs(k2 - k3) : m;
m = m < abs(k1 - k3) ? abs(k1 - k3) : m;
minx = minx < m ? minx : m;
int m1 = k1 < k2 ? k1 : k2;
m1 = m1 < k3 ? m1 : k3;
if(m1 == k1) i ++;
else if(m1 == k2) j ++;
else k ++;
if((i == sz1 - 1) && (j == sz2 - 1) && (k == sz3 - 1)) break;
}
printf("minx is : %d\n", minx);
return 0;
}
Merge these three arrays using a merge from merge sort approach. While merging check for the distance and save the ones that keep it min.
- chennavarri October 08, 2010