Adak, do you mean that this problem has order of O(n^2)? Well, if you sort the array, then the numbers with lowest difference are bound to get next to each other. So you need to check only consecutive elements for their differences. I don't know the linear time algo though!
~Vishal
On 11/18/05, [EMAIL PROTECTED] <[EMAIL PROTECTED]> wrote:
#1: He's hiding nothing, but his original statement is misstated. He
said at first he didn't have time to interview all of the programmers,
but in fact what he means is that the programmers don't have time to
wait for him to interview everyone. What happens, then, is that he has
a series of interviews. After each interview, he decides for all time
whether to reject or hire the current programmer. He can't go back to a
previous programmer and hire that one, and once he hires one, he
implicitly rejects all subsequent programmers. The question is what are
we trying to maximize? The probability of choosing the best? In that
case, it's the classic
http://mathworld.wolfram.com/SultansDowryProblem.html Sultan's Dowry
Problem.
