This week's book giveaways are in the Refactoring and Agile forums.We're giving away four copies each of Re-engineering Legacy Software and Docker in Action and have the authors on-line!See this thread and this one for details.
Win a copy of Re-engineering Legacy Software this week in the Refactoring forum
or Docker in Action in the Cloud/Virtualization forum!

# Interview Question: Finding min difference

Himanshu Gupta
Ranch Hand
Posts: 598
Given an N arrays of size K each.. each of these K elements in the N arrays are sorted, each of these N*K elements are unique. Choose a single element from each of the N arrays, from the chosen subset of N elements. Subtract the minimum and maximum element. Now, this difference should be least possible Minimum.. Hope the problem is clear

Sample:

N=3, K=3

N=1 : 6, 16, 67
N=2 : 11,17,68
N=3 : 10, 15, 100
here if 16, 17, 15 are chosen.. we get the minimum difference as 17-15=2

This is the question someone asked at stackoverflow. I tried to understand its solution but wasnt able to. Seems like I am missing something.

Can someone help me in understanding it.

Suggested Solution:

Ranch Hand
Posts: 312
My attempt as follows.

Himanshu Gupta
Ranch Hand
Posts: 598
Can you write it in some sentences so that it becomes easy to understand that what are you doing. Also did you analyze its time complexity?

Ryan McGuire
Ranch Hand
Posts: 1055
4
Himanshu Gupta wrote:Can you write it in some sentences so that it becomes easy to understand that what are you doing. Also did you analyze its time complexity?

If I understand correctly, in the original example it was just a coincidence that the element pulled from each array was at the same position.

For instance, if...
N1 = (15, 33, 55)
N2 = (1, 4, 17)
N3 = (9, 16, 200)

The answer would still be (15, 17, 16) for a minimum difference of 2.

Is that right, Himanshu?

Himanshu Gupta
Ranch Hand
Posts: 598
ya right. The difference of the selected items (max-min) should be minimum.

Ryan McGuire
Ranch Hand
Posts: 1055
4
Is this still an open question? The recent activity at stackoverflow has gone into some more detail to describe the idea behind the solution, including some modifications.