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 O(n^2) 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 O(n) because searching in a hash set or hash map is O(1):

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 O(nlog(n)), 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.

Advertisements
This entry was posted in Algorithms. Bookmark the permalink.

One Response to Google interview question

  1. Balaji Sankar says:

    Hi. You might want hyperlink what hash based structures are… Helpful post nonetheless 🙂

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s