Facebook Interview Question
Software Engineer / Developersnegative will be the same, if the input array allows it. just put all the value to the hashmap.
Try with Hash table.
Put all the array elements in Hash table.
Search for first array element in hash table and then x-a[0] value in hash table.
If it exists, return true.
else do this for other array elements present in hash table.
Complexity - O(n)
It can be implemented w/o any additional DS's in O(n Log n) time and with O(1) storage.
The below code and the driver app will find all the valid pairs, also included are the inlined comments:
#include <stdio.h>
#include <algorithm>
/*
Given an array of integers in the range INT_MIN to INT_MAX,
find all the pairs of elements that sum up to the given number @sum
Algorithm:
- Sort the input array
- Keep summing up the elements at the lowest and the highest current indices
- If the sum is > than the result, decrement the upper index
- If the sum is < than the result, increment the lower index
- If the sum = result, then
- found a valid pair; print the numbers
- converge the lower and upper indices (++lower, --upper)
- Loop until both indices meet
The above algorithm will find all the valid pairs, including positive,
negative and 0.
*/
bool find_sum(int arr[], int cnt, int sum)
{
int l, u, k;
bool bret = false;
/* Sort the input array */
std::sort(&arr[0], &arr[cnt]);
u = cnt - 1;
l = 0;
while (l < u) {
k = arr[l] + arr[u];
if (k == sum) { // found the two elements
printf("SUM: %-3d ELEMENTS (%d %d): %d %d\n",
sum, l, u,
arr[l], arr[u]);
bret = true;
l++;
u--;
}
else if (k < sum)
++l;
else
--u;
}
return bret;
}
int main(int argc, char* argv[])
{
int arr[] = {7, -4, 1, 0, -2, 3, 8, -9, 10, 1, 0, 20, 2};
int cnt = sizeof(arr)/sizeof(arr[0]);
for (int i = -10; i < 20; i++)
find_sum(arr, cnt, i);
return 0;
}
}}}
Use a hash map.
Suppose array is arr = {2,8,3,6,4,7,9}
Now use a hash map
key = arr[i]
value = sum - arr[i]
The idea here is that suppose we want sum 5
- Gamodg October 20, 2010now map will be
2,3
No entry for 8 as value >0
3,2 -> Here the value i.e. 2 exists as key -> 2,3 hence we have the sum 5