## Interview Question

Solutions Engineer Interview

-Menlo Park, CA

Meta## Given a list of integers and a target number, list all pairs that sum up to that number

AnswerAdd Tags

## Interview Answers

9 Answers

▲

0

▼

Not sure what happened above an wrong code got pasted. First one: int main (int argc, char * argv[]) { vector v = {2, 3, 5, 1, 6, 9, 10}; int target = 12; map m; for(auto it = v.begin(); it!= v.end(); it++) { int diff = target - *it; if(m.find(diff) != m.end()) { cout v = {2, 3, 5, 1, 6, 9, 10}; int target = 6; unordered_map m; //essentially a hash table map used; //to make sure we do not print same pair twice as (a,b) and (b,a) for(auto it = v.begin(); it!= v.end(); it++) //just load from vector to hashtable for quick lookup. m[*it]++; for(auto it = v.begin(); it!= v.end(); it++) { int diff = target - *it; auto it2 = m.find(diff); if(it2 != m.end()) { if(used.find(diff) == used.end() && used.find(*it) == used.end()){ //use unused pair cout << *it << ", " << diff << "\n" ; used[diff]++; used[*it]++; } } } return 0; }

Adi on

▲

0

▼

WTH. Something wrong with the interface, I will post one by one. int main (int argc, char * argv[]) { vector v = {2, 3, 5, 1, 6, 9, 10}; int target = 12; map m; for(auto it = v.begin(); it!= v.end(); it++) { int diff = target - *it; if(m.find(diff) != m.end()) { cout << *it << " ," << diff << "\n"; } else{ m[*it]++; } } return 0; }

Anonymous on

▲

0

▼

I think the solution to this problem is pretty easy. We need to take a map that monitors for the difference in it. I got the following code for it: int[] findPairs(int[] numbers, int target){ Map map = new HashMap(); int[] result = new int[2]; for(int i=0;i

Anonymous on

▲

0

▼

I am considering that the above solution is a List of List of integer pairs. Also, I am considering that pair (5,2) and (2,5) are different and are allowed in the solution set. I got the following solution from the problem posted and making the above assumptions. List> findTarget(int[] arr, int target){ List> result = new ArrayList>(); Set set = new HashSet(); for(int i=0;i temp = new ArrayList(); temp.add(target-arr[i]); temp.add(arr[i]); result.add(temp); } set.add(arr[i]); } return result; }

Anonymous on

▲

0

▼

Isn't this famous 2 sum problem?

Anonymous on

▲

0

▼

here is my C# solution: class PairSums { static void Main(string[] args) { // Call numberOfWays() with test cases here int ans = numberOfWays(new int[] { 2, 1, 3, 4, 4, 2, 2 }, 6); Console.WriteLine(ans); } private static int numberOfWays(int[] arr, int k) { Dictionary map = new Dictionary(); for (int i = 0; i distinct = map.Keys.ToList(); distinct.Sort(); int sum = 0; foreach (int i in distinct) { int target = k - i; if (map.ContainsKey(target) && i != target) { sum += map[i] * map[target]; } } sum = sum / 2; if (k % 2 == 0 && map.ContainsKey(k / 2)) { int count = map[k / 2]; sum += factorial(count) / (factorial(count - 2) * 2); } return sum; } private static int factorial(int x) { int product = 1; while (x > 1) { product *= x; x--; } return product; } }

lchun on

▲

0

▼

Could you manage it properly?

Anonymous on

▲

0

▼

I can think of two solutions, one without additional memory and other with additional memory. First: With additional memory using a hash table. Just traverse the array. At each value see if target-value is in the hashtable, if it is print it, else insert the value to the hashtable. Just in one pass you can find the pair. This also prevents writing (a,b) and (b,a) which is essentially same two times. int main (int argc, char * argv[]) { vector v = {2, 3, 5, 1, 6, 9, 10}; int target = 12; map m; for(auto it = v.begin(); it!= v.end(); it++) { int diff = target - *it; if(m.find(diff) != m.end()) { cout v = {2, 3, 5, 1, 6, 9, 10}; int target = 12; std::sort(v.begin(), v.end()); int left = 0; int right = (int)v.size()-1; while(left < right) { if(v[left] + v[right] == target) { cout << v[left] << " ," << v[right] << "\n"; left++; right--; } else if (v[left] + v[right] < target) left++; else right--; } return 0; }

Adi on

▲

5

▼

Could you describe the onsite rounds a little bit more in detail please?? Thank you.

Anonymous on

## Add Answers or Comments

To comment on this, Sign In or Sign Up.