programming forums Java Mobile Certification Databases Caching Books Engineering Micro Controllers OS Languages Paradigms IDEs Build Tools Frameworks Application Servers Open Source This Site Careers Other all forums
this forum made possible by our volunteer staff, including ...
Marshals:
• Campbell Ritchie
• Ron McLeod
• Paul Clapham
• Bear Bibeault
• Junilu Lacar
Sheriffs:
• Jeanne Boyarsky
• Tim Cooke
• Henry Wong
Saloon Keepers:
• Tim Moores
• Stephan van Hulst
• Tim Holloway
• salvin francis
• Frits Walraven
Bartenders:
• Scott Selikoff
• Piet Souris
• Carey Brown

# Interview Question: Finding min difference

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?

Bartender
Posts: 1197
22

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
Bartender
Posts: 1197
22
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.

 Consider Paul's rocket mass heater.