Finding the first duplicate in an int array, java

Question

Here is a common interview question i came across, however i failed to improve it in the way it demands.

assume we have an int array int[] A, we want to find the first duplicate entry. 

1. almost everyone can think of using a HashSet, and add to it while parsing.this will lead to O(n) time and O(n) space. After this I was asked to solve it without other data structures. I said the dumbest idea will be comparing each one in O(n^2) time. And then I was asked to improve the O(n^2) time.

2. And to improve it, i thought of using a fixed size array(assuming the maximum number is n), boolean[] b = new boolean[n]; however I was not allowed to use this method.

3. Then I thought of using an int variable, using bit manipulation, if the maximum number is smaller than 32, then for n we can push 1 to n bits left and | to a checker, then & the checker to the next entry in the array to check if it's > 0. e.g.:

   int c = A[i];
   if(check & (1 << c) > 0) return false;
   check |= 1 << c;
   

however this is not allowed either.

So there was an hint that I can use the array itself as hashset/hashtable, and "linear hashing"?

any help ? thanks

Answer 1

I have this one idea: as you progress down the array, you sort the part that you have visited. By employing binary search you'll improve time; space is 0. The sort itself is... insertion sort? You're basically running the sort as normal, but as you search for the place to insert the new numeber, if you hit the number itself, you shout "bingo". That's an improvement over zero space + O(n²) time.

Answer 2

I was presented this with the additional restriction of no additional memory, only the registers. This was what I came up with:

outer: for (i = 0; i < arr.length - 1; i++)
 for (j = i+1; j < arr.length; j++)
   if (arr[i] == arr[j])
     break outer;

If i and j are < arr.length, the are the indices of the first duplicate value and it's match.

It's just a little better than O(n^2) since j never cover the entire length of arr

Answer 3

well, you give the answer yourself: linear hashing does exist. it has complexity o(1)/o(1) according to http://cgi.di.uoa.gr/~ad/MDE515/e_ds_linearhashing.pdf so you'd take out elements from the array one after the other while using the first few as memory for the hash map.
but really, it's a datastructure that you implement yourself.

either the interview didn't say you'd have to solve it "without other data structures" or the interviewer did in fact not understand that a datastructure is a datastructure even if you implement it yourself.

rofls anyways, mostly because it's the kind of question that you either know, or you don't. there's no way to come up with this during an interview. i hope you won't work for them.