aspose file tools*
The moose likes Programming Diversions and the fly likes Interview Question: Finding min difference Big Moose Saloon
  Search | Java FAQ | Recent Topics | Flagged Topics | Hot Topics | Zero Replies
Register / Login


Win a copy of EJB 3 in Action this week in the EJB and other Java EE Technologies forum!
JavaRanch » Java Forums » Other » Programming Diversions
Bookmark "Interview Question: Finding min difference" Watch "Interview Question: Finding min difference" New topic
Author

Interview Question: Finding min difference

Himanshu Gupta
Ranch Hand

Joined: Aug 18, 2008
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:
Link



My Blog SCJP 5 SCWCD 5
Madhan Sundararajan Devaki
Ranch Hand

Joined: Mar 18, 2011
Posts: 312

My attempt as follows.









S.D. MADHAN
Not many get the right opportunity !
Himanshu Gupta
Ranch Hand

Joined: Aug 18, 2008
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

Joined: Feb 18, 2005
Posts: 988
    
    1
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

Joined: Aug 18, 2008
Posts: 598

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

Joined: Feb 18, 2005
Posts: 988
    
    1
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
 
subject: Interview Question: Finding min difference
 
Similar Threads
programming questioin
Deranged permutations
MultiDimenaional Array sort
Java Code
BST problem (Online waiting)