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=14805690One 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 themMy 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.
Programming interview: on sorted arrays, algorithm proof
algorithms
Lets call sorted arrays A1, A2, A3. We have three indices i1, i2, i3. We want to find one triple (i1,i2,i3) such that max(A1[i1], A2[i2], A3[i3]) - min(A1[i1], A2[i2], A3[i3]) is minimal. At beginning i1 = i2 = i3 = 0.One possible way is to try all triples (i1, i2, i3) for 0 <= i1 < A1.lenght, 0 <= i2 < A2.lenght, 0 <= i3 < A3.lenght. But many of those triples will be unnecessary to check.Without loss of generality (this is just for easier talking about arrays) let A1[i1] <= A2[i2] <= A3[i3]. We will do one increment in this block.There is no sence to try triples (j, i2, i3) for j < i1, because arrays are sorted and A1[j] <= A1[i1] which is minimum. Lets pretend we already tried all these (j, i2, i3).There is no sence to try (i1, i2, j) for j > i3 because A3[i3] <= A3[j].By trying triples (i1, j, i3) for arbitrary j we can go worse (min will be less or equal and max will be higher or equal).We tried indices less than i1, i2, i3. We reasoned triples (j < i1, i2, i3) and (i1, j, i3) are unnecessary, (i1, i2, j>i3) too. Same arguments for (j <= i1, k, l = i3). Decrementing i3 is no use as we tried (actually or reasoned about it) this triple before increasing the third index.We are left to increasing i1 which is index of min in the triple. After this the difference might get worse or A1[i1+1] is not minimal, but we proceed the same way.