Google Interview Question: Find if there are two members... | Glassdoor

Interview Question

Software Engineer Interview London, England (UK)

Find if there are two members of an array that sum to

  10 (10 and 0 count, but 10 alone does not).
Answer

Interview Answer

4 Answers

1

My first guess is something like the following, where 10 would be passed as the sum parameter:

int[] findSum(int[] nums, int sum){
  int[] pair = null;

  for(int i = 0; i < nums.length; i++){
    int a = nums[i];
    int target = sum - a;

    for(int j = 0; j < nums.length; j++){
      if(nums[ j ] == target){
        pair = new int[2];
        pair[0] = a;
        pair[1] = target;
        return pair;
      }
    }
  }

  return pair; // returns null if no suitable pair found
}

}

Justin Beal on Feb 23, 2010
0

I would use a hash to count how often the numbers between 0 and sum/10 show up. then go through the has to see if we have two that match. it is O(n^2) also, and doesn't work if sum is large.

int[] findSum(int[] nums, int sum) {
  int[] hash = new int[sum+1];

  //count how many numbers
  for (int i=0; i 0) && (hash[sum-i]>0)) {
        return new int[] {i, sum-i};
   }
 }
 return null;
}

blakdogg on Mar 1, 2010
3

Basically sort the elements in n log n . Then for every element k search for (Sum - k) in the array using a binary search. Hence total complexity is n log n.

Roark245 on Mar 10, 2010
5

You can use a hashmap from value to # of occurrences of the number in the hashmap. Enter all numbers to a the hashmap (O(n)), go through the array and calculate 10 - n for each member and determine whether that number has occurrences > 0 in the hashmap. If so, you have a match, don't forget to decrease the occurrence by 1 (O(n)). Total O(n).

Note that if duplicate is allowed (such that 5+5=10 is possible), you may need to check whether n = Sum - n, if so you must make sure the # of occurrences is > 1 and then reduce the occurrences by 2 instead.

Shards on Apr 24, 2010

Add Answers or Comments

To comment on this, Sign In or Sign Up.