Problem:

===========

You are given 3 integer arrays A, B and C of length n1, n2 and n3 respectively. All arrays are sorted. We define triplet of these 3 arrays as (x,y,z) where x is any integer from A, y from B and z from C. We define distance of triplet as maximum difference among triplet elements, i.e. Maximum of x – y, y – z or z – x. Write a program to find minimum triplet distance. (means there are n1*n2*n3 number of possible triplets are possible...among all triplets which triplet has minimum distance...Give only distance, but not triplet elements). Your program must be as much efficient as possible.

Solution:

=========

int incMin(int *i, int *j, int *k); helper function that will increase the minimum of the three input indexes of 3 arrays, e.g. if a[.i] is least out of a[.i], b[j], c[k] then it will do i++ and if any one goes out of bound, it will return ERROR

int windowSize(int i, int j, int k); helper function that returns the current window size = max(a[.i], b[j], c[k]) - min(a[.i], b[j], c[k])

now the concept goes as following:

we start with a window of 3 elements, one from each array. and keep altering the window as required and keep updating the minimum window found so far.

minWindow = 99999; // some very large value

returnVal = 0;

i = j = k =0;

while(returnVal != ERROR) //while one of the arrays does not exhaust

{

..currMinWindow = windowSize(i, j, k);

..if(currMinWindow < minWindow)

....minWindow = currMinWindow;

..returnVal = incMin(&i, &j, &k); // this will increase one of the i, j, k

}

int incMin(int *i, int *j, int *k)

{

..if(a[*i] < b[*j])

..{

....if(a[*i] < c[*k])

....{

......if(i<sizeof(A))

........(*i)++; //a[.i] is minimum, so inc i

......else

........return ERROR;

....}

....else

.....{

........if(k < sizeof(C))

..........(*k)++; //c[k] is minimum, so inc k

........else

..........return ERROR;

......}

..}

..else

..{

....if(b[*j] < c[*k])

....{

......if(j < sizeof(B))

........(*j)++; //b[j] is minimum, so inc j

......else

........return ERROR;

....}

....else

....{

......if(k < sizeof(C))

........(*k)++; //c[k] is minimum, so inc k

......else

........return ERROR;

....}

..}

}

===========

You are given 3 integer arrays A, B and C of length n1, n2 and n3 respectively. All arrays are sorted. We define triplet of these 3 arrays as (x,y,z) where x is any integer from A, y from B and z from C. We define distance of triplet as maximum difference among triplet elements, i.e. Maximum of x – y, y – z or z – x. Write a program to find minimum triplet distance. (means there are n1*n2*n3 number of possible triplets are possible...among all triplets which triplet has minimum distance...Give only distance, but not triplet elements). Your program must be as much efficient as possible.

Solution:

=========

int incMin(int *i, int *j, int *k); helper function that will increase the minimum of the three input indexes of 3 arrays, e.g. if a[.i] is least out of a[.i], b[j], c[k] then it will do i++ and if any one goes out of bound, it will return ERROR

int windowSize(int i, int j, int k); helper function that returns the current window size = max(a[.i], b[j], c[k]) - min(a[.i], b[j], c[k])

now the concept goes as following:

we start with a window of 3 elements, one from each array. and keep altering the window as required and keep updating the minimum window found so far.

minWindow = 99999; // some very large value

returnVal = 0;

i = j = k =0;

while(returnVal != ERROR) //while one of the arrays does not exhaust

{

..currMinWindow = windowSize(i, j, k);

..if(currMinWindow < minWindow)

....minWindow = currMinWindow;

..returnVal = incMin(&i, &j, &k); // this will increase one of the i, j, k

}

int incMin(int *i, int *j, int *k)

{

..if(a[*i] < b[*j])

..{

....if(a[*i] < c[*k])

....{

......if(i<sizeof(A))

........(*i)++; //a[.i] is minimum, so inc i

......else

........return ERROR;

....}

....else

.....{

........if(k < sizeof(C))

..........(*k)++; //c[k] is minimum, so inc k

........else

..........return ERROR;

......}

..}

..else

..{

....if(b[*j] < c[*k])

....{

......if(j < sizeof(B))

........(*j)++; //b[j] is minimum, so inc j

......else

........return ERROR;

....}

....else

....{

......if(k < sizeof(C))

........(*k)++; //c[k] is minimum, so inc k

......else

........return ERROR;

....}

..}

}

Powered by ScribeFire.

## No comments:

## Post a Comment