## Amazon Interview Question

Testing / Quality Assurances**Country:**India

**Interview Type:**Written Test

```
public class PairSum {
public static void printPair(int a[], int b[], int sum){
for(int i = 0; i < a.length; i++)
{
for(int j = 0; j < b.length; j++)
{
if(a[i] + b[j] == sum)
System.out.println("(" + a[i] + "," + b[j] +")");
}
}
}
public static void main(String[] args) {
// TODO Auto-generated method stub
int a[] = {1,2,4,-6,5,7,9};
int b[] = {3, 6, 3, 4, 0};
int sum = 5;
printPair(a, b, sum);
}
}
```

The below logic is O(n logn) and space O(n) but we can reduce space complexity by running sort on the vec2.

```
vector<pair<int, int>> PairSum(vector<int> vec1, vector<int> vec2, int sum) {
vector<pair<int, int>> result;
set<int> tree2(vec2.begin(), vec2.end());
for (auto v1 : vec1) {
int v2 = sum - v1;
if (tree2.find(v2) != tree2.end()) result.push_back(pair<int, int>(v1, v2);
}
return result;
}
```

simple and easy code

```
#include<bits/stdc++.h>
using namespace std;
void print(vector<int>vec1,vector<int> vec2,int sum)
{
unordered_set<int> s;
for(int i=0;i<vec1.size();i++)
s.insert(vec1[i]);
for(int j=0;j<vec2.size();j++)
if(s.find(sum-vec2[j])!=s.end())
cout<<sum-vec2[j]<<" "<<vec2[j]<<endl;
}
int main()
{
int n,m;
cin>>n>>m;
vector<int> vec1(n),vec2(m);
for(int i=0;i<n;i++)
cin>>vec1[i];
for(int i=0;i<m;i++)
cin>>vec2[i];
int sum;
cin>>sum;
print(vec1,vec2,sum);
}
```

// C/C++ program to segregate even and odd nodes in a

// Linked List

#include <stdio.h>

#include <stdlib.h>

#include <string.h>

int main()

{

int a[] = {1,2,3,4,5,6};

int ans = 5;

int i,j,k;

int sum=0;

int count= 0;

i = sizeof(a)/sizeof(a[0]);

for(j=0;j<i;j++)

{ for(k=0;k<i;k++)

{

if(a[j] + a[k] == ans)

{printf("%d %d", a[j], a[k]);

printf("\n");}

}}

}

It can be done in O(N+M) time and O(min(N,M)) space by creating a hash map recording the frequencies of occurrence of each element of the smaller list first. Then we iterate through the other list and for each element x, add H(n-x) to our total count, where H(n-x) obtains the frequency of n-x in the smaller list. This yields the total pair count.

class Pair {

int x ;

int y;

Pair(int x, int y) {

this.x = x;

this.y = y;

}

public String toString() {

return x + "," + y;

}

}

private static List<Pair> uniquePairs(int[] A, int[] B, int n) {

List<Pair> res = new ArrayList<>();

if( A == null || A.length == 0 || B == null || B.length == 0) {

return res;

}

Arrays.sort(A);

Arrays.sort(B);

HashMap<Integer, Integer> map = new HashMap<>();

for(int num : A) {

if(!map.containsKey(num)){

map.put(num, 1);

} else {

map.put(num, map.get(num) + 1);

}

}

for(int num : B) {

if( map.containsKey(n - num)) {

Pair tmp = new Pair(n - num, num);

res.add(tmp);

map.remove(n - num);

}

}

return res;

}

Most of the answers here are either N*M or NlogN in runtime. Even the C++ set solution, because creating it and searching for all elements is NlogN. There's a solution of N+M which is optimal. Build a dictionary from array B (run time M). Search in it the diffrence from n for every element from array A.

Implementation in JavaScript:

- benmeiri84 March 21, 2017