CareerCup

I am assuming that duplication does not matter: say
list1 = 10, 10
list2 = 20
target N = 30,
then we only need to output (10, 20). We do not need to output (10, 20), (10, 20)

If the list sizes are small, everyone knows the solution based on hash_set. The tricky part here is the list size (billions of integers). There are 4 billion integers, which requires 16GB memory if we store them in the memory ---- too large.

We can play the trick if bitmap encoding: we use 4 billion bits to represent the integers, which takes 512MB (much more reasonable now). If an integer appears in list1, we set the corresponding bit. The mapping is like this: calculate the byte offset using the first 29 bits, then calculate the bit to set using the last 3 bits (an integer has 32 bits in total).

After we store list1 using this compact way, we can check every element in list2 to see if there is an element in list1 to make the sum equal to N.

This is a linear time solution.

Sort L1 increasing and L2 decreasing.(order of nlogn)
Start two pointer from the head of L1 and L2.
step 1::find sum if 20 make pair ..
if less than 20 increase L1 pointer
else increase L2 and repeat step 1.

Put the first list in a hash map.
Then for each node in second list search (x = Sum - Node) in the map.
If you got this value in map, you got your pair.
Complexity O(n)

If the input list list size is huge (in TB) then it’s totally unrealistic to put all the nodes in a hash map.
In such cases you can go for the algo suggested by 'MI' above solution, but performance is a concerned there n log (n) for search and same for sorting.

If you are lucky and have a cluster of nodes then you can divide the first list data on cluster nodes, and sort using merge sort. Complexity n log (n). Remember its one time job.
Then divide the sorted data among nodes in the cluster and put on hash map.
Create a range based index map, for finding which node can possibly contain searched value.
Then for each node in the second list we need to search (X = Sum - Node), in the range index map and followed by cluster node map, if value found on map then we got our pair.
Complexity O(n).

step 1 loop through L1 and for each value in L1 do a simple math. p = N - L1[i] and push in hash map.
so for the example above values will be.
28= -8
-7=27
0 =20
56=-36
6 =14
-8 =28
0 =20
72 =-52
1000 =-980
-33 =53
so far O(n) space and O(n) time

loop through the L2 and for each L2[i] check in the Hashmap if exists then print N - L2[i] and L2[i]
O(m) time

hence big O is O(n)

public class ListPair {

// Returns list of the pairs
// with the addition equal to
// the sum mentioned.
public List<Pair> getPair(int sum, LinkedList<Integer> l1, LinkedList<Integer> l2) {
List<Pair> res = new ArrayList<Pair>();
Collections.sort(l1);
Collections.sort(l2, new MyComparator());
int oneIndex=0, twoIndex=0;
Pair pair = null;
while(oneIndex<l1.size() && twoIndex<l2.size()) {
if(l1.get(oneIndex)+l2.get(twoIndex)==sum) {
pair = new Pair(l1.get(oneIndex),l2.get(twoIndex));
res.add(pair);
twoIndex++;
oneIndex++;
} else if (l1.get(oneIndex)+l2.get(twoIndex)>sum) {
twoIndex++;
} else {
oneIndex++;
}
}
return res;
}

public static void main(String[] args) {
LinkedList<Integer> l1 = new LinkedList<>();
LinkedList<Integer> l2 = new LinkedList<>();
l1.add(1);
l1.add(2);
l1.add(6);
l1.add(-4);
l1.add(-2);
l1.add(4);
l1.add(5);
l1.add(-7);
l2.add(1);
l2.add(3);
l2.add(6);
l2.add(-4);
l2.add(-3);
l2.add(2);
l2.add(5);
l2.add(-7);
List<Pair> list = new ListPair().getPair(3, l1, l2);
for(Pair pair : list) {
System.out.println(pair.getV1() +" :: "+pair.getV2());
}
}

}


class MyComparator implements Comparator<Integer> {

@Override
public int compare(Integer o1, Integer o2) {
if(o1.intValue() < o2.intValue()) {
return 1;
} else {
return -1;
}
}

}

class Pair {
private int v1;
private int v2;

public Pair(int v1, int v2) {
this.v1 = v1;
this.v2 = v2;
}

public int getV1() {
return v1;
}
public void setV1(int v1) {
this.v1 = v1;
}
public int getV2() {
return v2;
}
public void setV2(int v2) {
this.v2 = v2;
}
}

1.create a heap of l1 with top bieng the smallest element. -nlogn time
2. traverse through each element of l2. say if first element is 10 and N=20. So the element in l2 should be 10. find it if its there.(logn time.)
we get the pairs.

int list1[] = {-1,3,4,5,-6,-7,-8};
int list2[] = {11,53,74,85,16,17,18};
int NUMBER = 10;(Suppose)
String pair = "";
for(int i=0;i<list1.length;i++){
for(int j=0;j<list2.length;j++){
if(list2[j]+list1[i]==NUMBER) {
pair=pair+"("+list1[i]+","+list2[j]+")";

}
System.out.println("pairs are "+pair);
}
}

create a BST from first linked-list (nlogn - worst case)
traverse second linked list, for each value i, search for n-i in the BST. nlogn (worst case n^2).

Step 1:sort L! in increasing order and L2 decreasing order.
Step2:-strat pointer from L1 is i and and L2 is j
where m is smallest arrey length;
while(j<m)
{
if(a[i]+b[j]==sum)
{ cout<<a[i]<<b[j]<<endl;i++;j++;}
else
{ if(a[i]+b[j]>sum) j++;
else
i++;
}
}
our program time complexity is O(nlog n);

If we can sort both lists in memory, in takes n lg(n).
But if we can sort both lists in memory, we can sort just one list, and for the other list, for each number, just look up its complement. So, it pays to first check the list sizes and then sort the smaller one. But if neither fits in our memory of size m, we can process the shorter list in chunks of size m, each time sorting m numbers, and for each chunk of size m, process the 2nd list. This takes:

iterations * (sorting + searching)
    n/m               (m lg(m)  + n lg(m))  =  n/m * (n+m) lg(m)

If we use a hash lookup, which is sufficient, we get: n/m (m + n)

So this seems to be a win. And, we can ensure there's no bad behavior in the hash, if we write our own which throws an exception when there are too many conflicts. At this point we can stop filling the hash, run the second list through it, and then iterate again.

Note that it also makes sense to ensure our hash is good for this case. I'd start out making the conflict list a linked list, then perhaps sort long ones into arrays before running the n numbers through it... On the other hand, maybe it's not worth the effort...