The following is a programming interview question: Given 3 sorted arrays. Find(x,y,z), (where x is from 1st array, y is from 2nd array, and z is from 3rd array), such that Max(x,y,z) - Min(x,y,z) is minimum. This question is discussed here: http://www.careercup.com/question?id=14805690
One possible solution discussed in the career cup page is the following: "Take three pointers. 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"
My question is, how can we prove the correctness of this algorithm? If not, can we come up with cases where the algorithm fails. And if so, what is a correct algorithm to solve this problem with the proof.
Max(x,y,z)
the max product ofx*y*z
? Can we accept a negativeMax(x,y,z) - Min(x,y,z)
?Max(x,y,z)
is most likely the maximum of the 3 values.abs(x-y) + abs(y-z)
is minimal. You'd increment from the the lowest number because you can't decrement the max value and parse until >1. The expression evaluate to 0 or >2. You parse through the entire list.