title: Finding the first duplicate in an int array, java
body: <p>Here is a common interview question i came across, however i failed to improve it in the way it demands.</p>
  
  <pre><code>assume we have an int array int[] A, we want to find the first duplicate entry. 
  </code></pre>
  
  <ol>
  <li><p>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.</p></li>
  <li><p>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.</p></li>
  <li><p>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 &amp; the checker to the next entry in the array to check if it's > 0.
  e.g.:</p>
  
  <pre><code>int c = A[i];
  if(check &amp; (1 &lt;&lt; c) &gt; 0) return false;
  check |= 1 &lt;&lt; c;
  </code></pre></li>
  </ol>
  
  <p>however this is not allowed either.</p>
  
  <p>So there was an hint that I can use the array itself as hashset/hashtable, and "linear hashing"? </p>
  
  <p>any help ? thanks</p>