Google interview question

Given an array of integers and an integer S, find if there are two numbers X and Y in the array such that X + Y = S. The problem was received by a friend during a phone interview with Google. A naive solution is:

void solutionNaive(vector& inVals, int sum) //O(n^2)
{
 size_t size = inVals.size();
 //naive
 for (int i = 0; i < size-1; i++)
 {
  for (int j = i+1; j < size; j++ )
  {
   if (inVals[i] + inVals[j] == sum)
   {
    printf("Values: %d and %d\n", inVals[i], inVals[j]);
    return;    
   }
  }  
 }
 printf("Not found\n");
}

This is  and its performance definitely not acceptable for large arrays. A faster solution is to use a hash set for storing the elements tested so far, and to test if S minus the current element was already stored in the hash set. More memory is used in this approach, but the complexity in this case is because searching in a hash set or hash map is :

void solutionOk(vector& inVals, int sum) //O(n)
{
 hash_set checkedVals;
 for (vector::iterator it = inVals.begin(); it!= inVals.end(); ++it)
 {
  if (checkedVals.find(sum - (*it)) != checkedVals.end())
  {
   printf("Values: %d and %d\n", sum - (*it), *it);
   return;
  }
  else
  {
   checkedVals.insert(*it);
  }
 }
 printf("Not found\n");
}

An other possible solution, not so efficient but interesting, is to sort te numbers and then for each X in the array to use binary search for searching if S-X is there. The complexity is , and no additional memory is used. An important aspect of this method is the way it handles the case when S-X = X:

void solutionNotSoBad(vector& inVals, int sum) ////O(n log(n))
{
 size_t size = inVals.size(); 
 //sorting is O(n log(n))
 sort(inVals.begin(), inVals.end());
 bool found = false;
 for (vector::iterator it = inVals.begin(); it != inVals.end(); ++it)
 {
  vector::iterator current = it;
  int toFind = sum - (*it);
  if ((toFind <= *it) && (it!= inVals.begin()))
  {
   found = binary_search(inVals.begin(), --current, toFind);
   current = it;
  }
  if ((toFind >= *it) && (it != inVals.end()))
  {
   found = binary_search(++current, inVals.end(), toFind);
   current = it;
  }
  if (found)
  {
   printf("Values: %d and %d\n", (*it), toFind);
   return;  
  }
 }
 printf("Not found\n");

}

As a conclusion, keep in mind that hash based data structures are generally the most appropriate to use when fast search operations are needed.