## 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

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

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

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

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

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

How can you prove the correctness of this algorithm?

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.

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

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.

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

your code will not work in the case of

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

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

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

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

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

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)

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

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.

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.

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)

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

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

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

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?

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

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

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

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

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?

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

No I am wrong,this program is incorrect

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

}

}
System.out.println(results);
}
}``````

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 .

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

``````/* 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
*/``````

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

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

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.

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

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!!

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.

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.

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 :)

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

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

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

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));
}``````

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

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

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.

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