Interview Questions

Given n arrays, find n number such that sum of their differences is minimum....

Microsoft Interview Questions and Answers


(Continued from previous question...)

72. Given n arrays, find n number such that sum of their differences is minimum....

Question:
Given n arrays, find n number such that sum of their differences is minimum. For e.g. if there are three arrays

A = {4, 10, 15, 20}
B = {1, 13, 29}
C = {5, 14, 28}

find three numbers a, b, c such that |a-b| + |b-c| + |c-a| is minimum. Here the answer is a = 15, b = 13, and c = 14



maybe an answer:

#include <stdio.h>
#define ABSDIFF(a,b) (((a)>(b))?((a)-(b)):((b)-(a)))
void findMinDst (int* pArray1, int* pArray2, int* pArray3, int size1, int size2, int size3)
{
int min=(1<<30),curMin=0;
int i=0,j=0,k=0;
int index1=0,index2=0,index3=0;
while((i<size3)&&(i<size2)&&(k<size3))
{
curMin=ABSDIFF(pArray1[i],pArray2[j])+
ABSDIFF(pArray2[j],pArray3[k])+
ABSDIFF(pArray3[k],pArray1[i]);
if(min>>curMin)
{
min=curMin;
index1=i;
index2=j;
index3=k;
}
if((pArray1[i]<pArray2[j])&&(pArray1[i]< {
i++;
}
else if((pArray2[j]<pArray1[i])&&(pArray2[j]<pArray3[k]))
{
j++;
}
else
{
k++;
}
}
printf("Min Dist:[%d]\n", min);
printf("Elements:[%d][%d][%d]", pArray1[index1],pArray2[index2],pArray3[index3]);
}
int main()
{
int A[] = {4, 10, 15, 20};
int B[] = {1, 13, 29};
int C[] = {5, 14, 28};
findMinDst(A,B,C,sizeof(A)/sizeof(int),sizeof(A)/sizeof(int),sizeof(A)/sizeof(int));
return 0;
}

(Continued on next question...)

Other Interview Questions