Yahoo Interview Question for Software Engineer / Developers






Comment hidden because of low score. Click to expand.
0
of 0 vote

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 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

I 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.

- Aditya October 12, 2010 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

I've posted code below. Hope that helps

- chennavarri October 12, 2010 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

Right. But even without using extra space to merge the arrays, we can just advance the pointers on these arrays as in merge sort.

- Anonymous October 08, 2010 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Right. But even without using extra space to merge the arrays, we can just advance the pointers on these arrays as in merge sort.

- Anonymous October 08, 2010 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

/*! 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<<")";
}

- chennavarri October 12, 2010 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

/// 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;
}

- zombie June 21, 2013 | Flag Reply


Add a Comment
Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

Learn More

Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More