Win a copy of Think Java: How to Think Like a Computer Scientist this week in the Java in General forum!
  • Post Reply
  • Bookmark Topic Watch Topic
  • New Topic

Interview Question: Finding min difference

 
Himanshu Gupta
Ranch Hand
Posts: 598
Android Eclipse IDE Ubuntu
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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

 
Madhan Sundararajan Devaki
Ranch Hand
Posts: 312
Java MS IE
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
My attempt as follows.







 
Himanshu Gupta
Ranch Hand
Posts: 598
Android Eclipse IDE Ubuntu
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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: 1061
4
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Android Eclipse IDE Ubuntu
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
ya right. The difference of the selected items (max-min) should be minimum.
 
Ryan McGuire
Ranch Hand
Posts: 1061
4
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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.
 
  • Post Reply
  • Bookmark Topic Watch Topic
  • New Topic