3

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.

Improve this question
5
  • Let's clarify this a bit. I assume array of integers, can they be negative? Is Max(x,y,z) the max product of x*y*z? Can we accept a negative Max(x,y,z) - Min(x,y,z)?
    – Marsellus Wallace
    Mar 17, 2013 at 19:35
  • @Gevorg Max(x,y,z) is most likely the maximum of the 3 values.
    – Bernhard Barker
    Mar 17, 2013 at 19:37
  • @Gevorg Assume that array of integers is positive. Max(x,y,y) is maximum of the 3 values as Dukeling pointed out. Assume we can accept negative Max(x,y,z) - Min(x,y,z).
    – Romonov
    Mar 17, 2013 at 20:09
  • IDK how to formally prove it, but (I believe) that the whole basis for the algorith is to find when the variance among x, y and z are minimal. In other words when 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.
    – SGM1
    Mar 17, 2013 at 20:25
  • 1
    Why are people being so anal on Stackoverflow? This isn't off topic. Re-open the question.
    – darksky
    Mar 18, 2013 at 5:25

2 Answers 2

Reset to default
1

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.

Improve this answer
2
  • I will edit my post to make it more clear, I hope.
    – kyticka
    Mar 17, 2013 at 21:23
  • 1
    This is actually almost correct, just needlessly overcomplicated. We can simply say that all triplets (i1,j2>=i2,j3>=i3) are no better than (i1,i2,i3) and may be discarded. So the next viable triplet is (i1+1,i2,i3).
    – n. m. could be an AI
    Mar 17, 2013 at 21:31
1

The algorithm has as loop-invariant where we know the smallest value of max(x, y, z) - min(x, y, z) for all possible values of x, y, or z smaller than the current values.

To start with x, y, and z are the smallest possible, so the invariant is true at the beginning. At the end, x, y, and z are the largest possible, so they cover all possible values, and we have the answer.

Given some values of x, y, z, if we know the optimal value of max(x, y, z) - min(x, y, z) for smaller values, then any better value would require incrementing x, y, or z.

If we don't increment the minimum of them then every larger value of x, y, or z can only increase the value of max(x, y, z) - min(x, y, z) because the maximum can only increase, and the minimum will stay the same. So the minimum is incremented to the smallest value that could possibly be better than the one we have, which maintains the loop-invariant.

Improve this answer
4
  • "can only increase the value of max" --- so what? It will increase now, but decrease at some next iteration, when we do decide to increment the minimum. Perhaps we will be able to find a smaller target value this way. Can you prove this is not the case?
    – n. m. could be an AI
    Mar 17, 2013 at 21:05
  • @n.m. If the minimum is not changed, then there is no possible future iteration that lowers max-min. We want to increment the minimum because it's the only way to find a smaller target value.
    – fgb
    Mar 17, 2013 at 21:34
  • "If the minimum is not changed, then there is no possible future iteration that lowers max-min" -- no, sorry. If the minimum is never changed, then there's indeed no possible future iteration that lowers max-min. But no one says it is never changed. It is not changed at this particular iteration. It will be changed at some future iteration, and will lower max-min. You need to prove it will not lower max-min enough.
    – n. m. could be an AI
    Mar 17, 2013 at 21:42
  • Yes, I meant if it's never changed. If it needs to eventually be incremented, we might as well increment it immediately. We would only not increment it immediately if there were larger values of the other variables that could give a lower target value.
    – fgb
    Mar 17, 2013 at 21:45

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.