## Questions d'entretien

Entretien pour Solutions Engineer

-

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

Répondre

## Réponses aux questions d'entretien

9 réponse(s)

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; }

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; }

Utilisateur anonyme le

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; for(int i=0;i

Utilisateur anonyme le

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; }

Utilisateur anonyme le

0

Isn't this famous 2 sum problem?

Utilisateur anonyme le

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 le

0

Could you manage it properly?

Utilisateur anonyme le

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; }