title: Interview - find all pairs of array elements whose sum is known
body: <p>I was asked this question:
  given an array of size <code>n</code> of <code>int</code>s and <code>int sum</code>, I need to return all pairs of the array's elements whose sum is equal to <code>sum</code></p>
  
  <pre><code>std::vector&lt; std::pair&lt;int,int&gt; &gt; find(int* arr,size_t n,int sum)
  </code></pre>
  
  <p>The arrays is not sorted.
  I have proposed an O(n) time solution using a hash table:</p>
  
  <pre><code>traverse the arr 
    if arr[i] is in the hash 
         vector.push_back (make_pair(arr[i],sum-arr[i]));
    else
         insert to the hash sum - arr[i]
  </code></pre>
  
  <p>The solution requires extra space for the hash.... What size should be chosen for the hash? Which hash function?</p>
  
  <p>What do you think about that? Is there a better way to solve this?</p>
  
  <p>P.S.
  I know an additional solution exists: sort the array; traverse it with two pointers from the end and begining, based if current sum is greater or smaller than <code>sum</code></p>
  
  <p><strong>Upd.</strong>
  It is not the same question for which answers exists  - I am interested in the correct implementation of the hash.</p>