Microsoft Interview Question for Developer Program Engineers


Team: BING
Country: India
Interview Type: In-Person




Comment hidden because of low score. Click to expand.
13
of 15 vote

take three pointer. Each to the first element of the list. then find the min of them. compute max(xyx)-Min(xyz). If result less than till now result change it. increment the pointer of the array which contains the minimum of them

- Anonymous October 05, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

if max(xyz)-min(xyz) is not less than result what to do then ?
consider:
A1: 5 7 9 11 12 20
A2: 4 5 11 14 16 20
A3: 1 3 4 8 10 20

- nikkiani1991 October 28, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

public int minGap(int[] a, int[] b, int[] c) 
        {
                int diff = Integer.MAX_VALUE;
                int min = Integer.MAX_VALUE;
                int max = Integer.MIN_VALUE;
                int i, j, k;
                for(i = 0, j = 0, k = 0; i < a.length && j < b.length && k < c.length;) {
                        min = Math.min(a[i], Math.min(b[j], c[k]));
                        max = Math.max(a[i], Math.max(b[j], c[k]));
                        diff = Math.min(diff, max - min);
                        if(diff == 0) break;
                        if(a[i] == min) i++;
                        else if(b[j] == min) j++;
                        else k++;
                }
                return diff;
        }

- dgbfs November 28, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

How can you prove the correctness of this algorithm?

- Anonymous March 17, 2013 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

The correctness argument goes something like this. Let's say the heads of X, Y, and Z are 10, 5, and 20, so that y=5 is the min. Consider all tuples (x, 5, z). Since X is sorted we know that x >= 10 for all x, and likewise all z >= 20. So now we know any solution involving y=5 has the form (x >= 10, 5, z >= 20). Since y=5 is less than 10 and 20, we clearly know the optimal solution for that form has to be (10, 5, 20), which we just evaluated. Therefore, since we have proven that we've already considered the optimal solution for y=5, we can advance the Y pointer beyond y=5 to find more optimal solutions over (X, Y, Z). It's also pretty easy to convince ourselves that the algorithm terminates in linear time, since we always exclude one element from one of the lists. (To be precise, it's O(Nm) time, where m=3, but we can treat as m as a constant in the current formulation.)

Even though it's pretty easy to prove the correctness of the algorithm, there is still risk in messing up the implementation. Fortunately, this problem has a trivial O(N^3) solution as well, so you can use your slow implementation to validate the fast implementation for a bunch of randomly generated small lists. This won't conclusively prove that the faster algorithm works, but it can help identify bugs in the implementation.

- showell30@yahoo.com March 17, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Your code will not work in the case :

array1 = {1,4,12};
array2 = {2,10,11};
array3 = {10,11};

your code will stop when array1 ends but at that time array2 pointer will be at 10 and also array3 pointer will be at 10, but at that time max of min difference is 2 and that is not correct.Answer should be 1.

- Dheeraj Khatri August 04, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

your code will not work in the case of

array1 = {1,4,12};
array2 = {2,10,11};
array3 = {10,11};

- Dheeraj Khatri August 04, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Your code will not work in the case of.
array1 = {1,4,12}
array2 = {2,10,11}
array2 = {10,11}

- khatri August 04, 2015 | Flag
Comment hidden because of low score. Click to expand.
3
of 3 vote

take the list which has minimum element start from first element element1 on list1 and have an index for both of other list now move one by one to find the nearest value of element1 in list2 and list3 find max(i,j,k)-min(i,j,k) store it in result now take element2 from list1 and move index on list2 and list3 to find the nearest of element2 now again find max(i,j,k)-min(i,j,k) if it is less than result then replace result.repeat to end of element in list1 return the result value .if u need the element value then maintain i,j,k when result is replaced.the complexity of worst case is O(sizeoflist1+sizeoflist2+sizeof3) space c omplexity is constant

- sukusuku October 15, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 3 vote

public static int[] MinimumDifference(int[] X, int[] Y, int[] Z) {
		int[] resultAndIndex={Integer.MAX_VALUE,-1,-1,-1};

		int xIndex=0;
		int yIndex=0;
		int zIndex=0;
		
		while (resultAndIndex[0] > 0 && xIndex < X.length && yIndex < Y.length && zIndex < Z.length){
			
			//find the maximum number and the minimum number
			int max = X[xIndex];
			int min = X[xIndex];
			boolean xIsMin = true;
			boolean yIsMin = false;
			if (Y[yIndex] > max){max=Y[yIndex];}
			else if (Y[yIndex] < min) {min=Y[yIndex]; xIsMin = false; yIsMin = true;}
			if (Z[zIndex] > max) {max = Z[zIndex];}
			else if (Z[zIndex] < min) {min = Z[zIndex]; xIsMin = false; yIsMin = false;}
			
			//store the minimum result up to now
			if (resultAndIndex[0] > max - min){
				resultAndIndex[0] = max - min; //the minimum difference
				resultAndIndex[1] = xIndex; //1 is for xIndex
				resultAndIndex[2] = yIndex; //2 is for yIndex
				resultAndIndex[3] = zIndex; //3 is for zIndex
			}
			
			if (xIsMin) xIndex++;
			else if (yIsMin) yIndex++;
			else zIndex++;
		}
		return resultAndIndex;
	}

- leichongchong October 06, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 3 vote

indices i, j, k <-- 0 pointing to lists 1, 2, 3 respectively
minVal <-- +infinity
iMax, jMax, kMax <--0;

at each step 
       find which list[index] is minimum among i, j, k then increase that index by 1
       if minVal is greater than  max(three lists at their index) - min(three lists at their index)) 
               update minVal and iMax, jMax, kMax
while indices are not out of list size
return minVal

takes O(n+m+l)

- taheri.javad October 09, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Even though the concept mentioned by you is correct (in fact same as previous Anonymous comment) I think the ordering of algorithm is incorrect.
The line "find which list[index] is minimum among i, j, k then increase that index by 1" should have been after minVal check & update, otherwise it gives a wrong idea that at each step we first find out the index with min value and increment that index after which we do a minVal > (max (..) - min (..)) check with elements at updated index.

- buckCherry October 20, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

take smallest numbers of all 3 arrays, compute min xyz , max xyz and compare and store, get the next smallest number of the array containing smallest number min xyz , do the above process recursively until the result is more than the previous one, then stop and previous values of xyz are the ans.

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

You will have to find 3 closest numbers from those sorted lists

This is how this can be done :

1. Take a smallest list – say list-1 ( remaining lists are : list-2, list-3)
2. For each number in list-1 find the closed number in list-2 and list-3 )
3. Step#2 can be done using modified binary search ( if you get exact match then its good or else you get a closest value when searching stops) since list is sorted . – ( time complexity log(n) for each element in list-1 ).
4. With each iteration you would also have to store that closest found values from list-1 and list-2 ( make use of hashmap or some other data structure ).
5. Once this is done , iterate through the hashmap and calculate max(x,y,z) – min(x,y,z) -- whichever results in minimum is the correct answer.

Note : you can avoid using extra storage by making use of 6 variables – 3 for holding current combination (x1,y1,z1) and 3 for holding previous combination(x0,y0,z0) which is also minimum – replace the previous combination with current combination when you find that :

[max(x1,y1,z1)-min(x1,y1,z1) ] < [max(x0,y0,z0)-min(x0,y0,z0) ]

e.g. :

List -1 : 1, 3, 5, 7
List -2 : 2, 4, 6, 8
List -3 : 1, 2, 11, 20

After step#3 you would have : ( format : list-1(list-2,list3) )

1(2,1) , 3(2,2) , 5(4,2), 7(6,11).

In this example we have two answers :

1(2,1) and 3(2,2)

time complexity O(nlogn)

- maverick October 10, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

I think the algorithm works and we don't need additional memory to store all the tuples of closest numbers for each elements of the list with smallest size. However this method is so brute force and it benefits only when the size of list with smallest size is relatively very less than sizes of rest two lists. Let's get a bit deeper into the run time calculation to understand this.

If we assume the lists are of sizes k, m, n and k is min of the three lists, then the run time is k(logm+logn). For each element from a list, searching closest elements from other lists takes (logm+logn) and we repeat this for k times. Now we can see that this is better than k+m+n only when k <<< m and k <<< n [ <<< means very less].

- buckCherry October 20, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

How about below approach

A1 -> Array 1
A2 -> Array2
A3 -> Array3

i think below is what needs to be done

max( min(A1), min(A2), min(A3)) - min( max(A1),max(A2),max(A3))

Any thoughts?

- Arulmozhi October 28, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

@Arulmozhi
I think you are right. Why lots of people try to work around it?

- Kevin March 06, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

No this cannot be done as it may not necessarily give elements from all the three arrays

- Lisha February 12, 2016 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

What are the numbers? Integers? And we can have negative numbers or only positive?

- vag November 04, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

No I am wrong,this program is incorrect

- vag November 04, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

What about this?Maybe I am too tired and I write stupid things, but check it out. It prints the arraylist with the max - min elements and then we just get the minimum one...

package maximum;
import java.util.ArrayList;

public class Maximum {

    
    public static void main(String[] args) {
       
        ArrayList<Integer> results = new ArrayList<Integer>();
        
        int[] array1 = {0,1,2,3,4};
        int[] array2 = {3,7,10,100,1000};
        int[] array3 = {0,34,40,300,450};
        
        int max;
        int min;
 
        
        for(int i = 0 ; i< array1.length;i++)
        {
            max = array1[i];
            min = array1[i];
            
            
            for(int j = 0 ; j < array1.length ; j++)
            {
                if(array2[j] > array1[i])
                {
                    if(array2[j]>array3[j])
                    {
                        max = array2[j];
                    }
                    else
                    {
                        max = array3[j];
                    }    
                }
                if(array2[j] < array1[i])
                {
                    if(array2[j]<array3[j])
                    {
                        min = array2[j];
                    }
                    else
                    {
                        min = array3[j];
                    }    
                }
                
            }
            results.add(max - min);
            
        }
        System.out.println(results);
    }
}

- vag November 04, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

step 1 . We will maintain pointer to starting point of three array say x,y,z
step 2 . now we need to find minimum and maximum of A[x] , B[y] , C[z]
step 3 . & we know that Max(abs(a[i]-b[j]),abs(a[i]-c[k]),abs(b[j]-c[k])) = difference of (Max - Min) = P ( say.. )
step 4 . As we Need to minimize above value so we need to reduce this difference so we will increment index having minimum value and again perform step 2 .

- bartender January 24, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

/* You are 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]))"
Please give a solution in O(n) time complexity
*/
#include<iostream>
#include<cstdio>
#include<cmath>
using namespace std;

const int N = 300;
int a[N];
int b[N];
int c[N];
int al, bl, cl;

inline int min(int a, int b, int c)
{
    return min(min(a, b), c);
}

inline int dist(int a, int b)
{
    return max(a-b, b-a);
}

inline int dist(int a, int b, int c)
{
    return max(max(dist(a,b), dist(a,c)), dist(b,c));
}

int main()
{
    cin >> al;
    for (int i = 0; i < al; i++) cin >> a[i];
    cin >> bl;
    for (int i = 0; i < bl; i++) cin >> b[i];
    cin >> cl;
    for (int i = 0; i < cl; i++) cin >> c[i];

    int r = dist(a[0], b[0], c[0]);
    for (int ai = 0, bi = 0, ci = 0; ai < al && bi < bl && ci < cl;)
    {
        r = min(r, dist(a[ai], b[bi], c[ci]));
        int m = min(a[ai], b[bi], c[ci]);
        if (a[ai] - m == 0)
            ai++;
        else if (b[bi] - m == 0)
            bi++;
        else
            ci++;
    }
    cout << r << endl;
    return 0;
}

/*
input:
2 2 5
2 2 9
1 6
output:
4

input:
10 1 2 3 4 5 6 7 8 9 10
5 2 4 6 8 10
3 -1 13 24
output:
3

input:
10 1 2 3 4 5 6 7 8 9 10
5 2 4 6 8 10
3 1 13 24
output:
1
*/

- bartender January 24, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

tom-on-programing.blogspot.in/2012/03/yahoo-interview-question-minimal.html

- bartender January 24, 2013 | Flag
Comment hidden because of low score. Click to expand.
-1
of 1 vote

use Merge sort all the array also keep track of every number such that we can know the number is from which array, Find xyz in such a way that xyz are closest. that's the result.

- Anand Pritam October 05, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

In your algorithm when you find xyz from the merge-sorted combined list, how do you find closest xyz so that each number belongs to each original list! In fact that's the catch of this question!!

- buckCherry October 20, 2012 | Flag
Comment hidden because of low score. Click to expand.
-1
of 1 vote

#include<stdafx.h>
#include<iostream>

using namespace std;
int main()
{
int a[6] = {1,2,3,4,5,6};
int b[6] = {7,8,9,10,11,12};
int c[6] ={13,14,15,16,17,18};
int x,y,z;

for(int i=5; i>=0;i--)
{
if(a[i] <=b[0] || i ==0)
{
x= a[i];
y = b[0];
break;
}
}
for(int i =5; i>=0;i--)
{
if(y>=c[i] || i ==0)
{
z=c[i];
break;
}
}

cout << x << " "<<y<<" "<<z;
}


Find the max(x,y,z) - min(x,y,z), result will be minimum.

- mittalpradeep84 October 05, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

Task at hand : Minimising the function - Max ( x , y , z ) - Min ( x , y , z )
Now to minimise this operation, we need to minimise the first function and maximum the second function, so that we get a less number, or maybe even a negative number.
We simplified our task of minimising the function into smaller tasks.

1) Minimising Max ( x , y , z )
So we need to get the 3 smallest numbers from the three arrays. For this, we need to see atmost 3 elements. That is, the first 3 elements of all the 3 arrays. We could do this in many ways.

2) Maximising Min ( x , y , z )
Similarly, here we need to find the 3 largest elements in the array. Here also, we will need to see only 9 elements, which are the 3 ending elements in all the 3 arrays.

Now, the task of simplifying is achieved :)

- TMH October 05, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

@TMH
Wrong answer. you are calculating different values of x,y,z for min and max.
question is to find x,y,z such that the difference of max and min is least. Also the difference can never be less than 0 but you say it can be negative.
Read the problem carefully then suggest answer.

It can only be solved by taking closest values of x,y and z.

- true lies October 05, 2012 | Flag
Comment hidden because of low score. Click to expand.
-2
of 2 vote

public static int find(int[] X, int[] Y, int[] Z)
	{
		int i = 0;
		int minDiff = diff(X[0], Y[0], Z[0]);
		while(++i < X.length){
			minDiff = Math.min(minDiff, diff(X[i], Y[i], Z[i]));
		}
		return minDiff;
	}
	
	public static int diff(int x, int y, int z){
		return Math.max(x, Math.max(y, z)) - Math.min(x, Math.min(y, z));
	}

- avico81 October 06, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

friend dont u think u are missing some cases in this......of camparison like elements of indexes (0,1,1) , (0,0,1),.......and so many

- shreyans October 13, 2012 | Flag


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