techInterview Discussion 

A part of techInterview.org: answers to technical interview questions.
Your host: Michael Pryor 
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.
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
You don't need abs. Once you sort into ascending, a[i+1]a[i] will be nonnegative.
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 xy is minimum A is augmented with the following to get algorithm B: if (xy) == 0 return Yes else No So for all arrays with dups you get yes and for others you get no.
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 cheatersort (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.
To xiaoyong:
nlogn < 32n, if n < 2^32, and if n > 2^32, your method needs lots of space.
Fang Friday, June 04, 2010 
Powered by FogBugz