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).

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 &lt; nums.length; i++){
int a = nums[i];
int target = sum - a;

for(int j = 0; j &lt; nums.length; j++){
if(nums[ j ] == target){
pair = new int;
pair = a;
pair = 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) &amp;&amp; (hash[sum-i]&gt;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 &gt; 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 &gt; 1 and then reduce the occurrences by 2 instead.

Shards on Apr 24, 2010