techInterview Discussion

Answers to technical interview questions. A part of TechInterview.org

A part of techInterview.org: answers to technical interview questions.

Your host: Michael Pryor

smallest difference pair in an integer array in O(n)time

Given an array of integers find two integers x and y such that |x-y| is minimum among all such pairs.
Lorien Send private email
Wednesday, May 19, 2010
 
 
In O(n)?  That will be interesting.  There are O(n squared) possible (x,y) pairs.

Sincerely,

Gene Wirchenko
Gene Wirchenko Send private email
Wednesday, May 19, 2010
 
 
If using only comparisons, O(n) not possible.

Essentially the Element distinctness problem.
Anonical
Wednesday, May 19, 2010
 
 
Forgot to mention.

Omega(nlogn) lower bound for Element distinctness problem has been shown.

And current problem can easily be solved by sorting.
Anonical
Wednesday, May 19, 2010
 
 
Thanks for the response,
it appears that element distinctness problem (say EDP) is indeed related to this one,
can we formally 'reduce' it to EDP ?
Let me try,
let's call the problem in question to be 'P'
if we were able to find out the solution to P in time t (< O(nlogn))
then given an array with a duplicate pair we can use the same algorithm to solve EDP in t which is a contradiction.

That does it I guess.
Lorien Send private email
Thursday, May 20, 2010
 
 
You should also say that even for an array with no dupes (a NO answer to EDP), this problem can be used.

Basically if min difference != 0, then no dupes, else there are.
Anonical
Thursday, May 20, 2010
 
 
Also you need to abs() the result first before you sort because its |x-y|

Thursday, May 20, 2010
 
 
You don't need abs. Once you sort into ascending, a[i+1]-a[i] will be non-negative.
Anonical
Thursday, May 20, 2010
 
 
yes, the words 'same' should not be used above proof that's a mistake
So it becomes,
algorithm A returns x and y such that |x-y| is minimum
A is augmented with the following to get algorithm B:
if (x-y) == 0 return Yes else No
So for all arrays with dups you get yes and for others you get no.
Lorien Send private email
Friday, May 21, 2010
 
 
Finding Max and Min is possible in one pass of the array. So it should be possible in O(n)
Saurabh Send private email
Wednesday, May 26, 2010
 
 
Sorry more correctly finding top 2 maximum numbers can be done in O(n)
Saurabh Send private email
Wednesday, May 26, 2010
 
 
It's trivial with a *sorted* list, of course, and there are many sorting methods that a given interviewer might consider O(n) (but are really O(n * log(k)), where k is a maximum value for all integers in the set), such as a radix or hash sort.

If this is a real interview question, it's either a nasty trick question, or the interviewer is likely looking for a cheater-sort (or he;s just confused).

Wednesday, May 26, 2010
 
 
Hi,
    I'm a newer to this forum and the English is not my first language,  please forgive my poor description.
  I found a O(n) solution (in fact, it's cn, here c is the bit number for an integer, e.g. on 32 bit platform, it's 32).
Here we use a binary probe:
1) compare the highest bit by traversal the integer array (it's n time),  then we get 2 subarrays that one of them include p number of integers which highest bit is 1 and another include q number of integers which highest bit is 0,  here p+q = n
2) Then compare the second highest bit for the 2 subarrays respectively, then get 4 subarrays ... and so on
3) repeat the above steps until we satisfy one of the following conditions:
    a)  there are some integers in the n number items array, they are same,  i.e. all the bits in them are all same
    OR
    b)  there are 2 integers in the array,  they have the most of high bits are same

    Hope I describe my solution clearly,  the basic principle behind it is that the smallest difference pair should be that they satisfy the most of high bits in them are same.
Xiaoyong Feng Send private email
Friday, June 04, 2010
 
 
To xiaoyong:
    nlogn < 32n, if n < 2^32, and if n > 2^32, your method needs lots of space.
Fang
Friday, June 04, 2010
 
 
Practically speaking, it's a bucket sort. Bucket sorts are often the fastest way in practice to sort small integers, but I don't feel that O(n) accurately describes an algorithm whose running time in the unit-cost model depends on the precision of the input numbers.
d Send private email
Saturday, June 05, 2010
 
 
Hi Fang,
    Thanks,  you are right, I need a further thinking about this :)
Xiaoyong Feng Send private email
Monday, June 07, 2010
 
 
1) Sort in O(n) time using radix or counting sort.
2) Take the pairwise difference of all consecutive elements in the sorted array and find the minimum amonst all the differences computed. This also takes O(n) time.

The assumption is that we can sort in O(n) time.
Apoorv Bansal Send private email
Tuesday, July 06, 2010
 
 

This topic is archived. No further replies will be accepted.

Other recent topics Other recent topics
 
Powered by FogBugz