# Interview Question: Finding min difference

posted 4 years ago

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:

Link

- 0

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:

Link

My Blog SCJP 5 SCWCD 5

posted 4 years ago

- 0

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?

My Blog SCJP 5 SCWCD 5

Ryan McGuire

Ranch Hand

Posts: 1048

4

posted 4 years ago

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?

- 0

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?

posted 4 years ago

- 0

ya right. The difference of the selected items (max-min) should be minimum.

My Blog SCJP 5 SCWCD 5

Ryan McGuire

Ranch Hand

Posts: 1048

4

posted 4 years ago

- 0

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.

I agree. Here's the link: http://aspose.com/file-tools |