CareerCup

Do we've any more information, like, if the file data sorted or not; or, what is the range of numbers so on; or, does there any duplicate of any value/is each number unique (in either of the files)?

Sort the two lists using external merge sort , then based on the memory restriction for ex if 120 mb memory is allocated load 40mb of first list, 40 mb of second list and next 40 mb for intersection . use merge logic on list1 and list 2 and find common elements , if any of the lists are over load the remaining content in to the memory . if intersection memory becomes full write it to disk . In this way we can find out the intersection of two element array.

1. Calculate the length of both of the lists eg: a.length= l , b.length=m
2. If one list is greater than other calculate the difference in length
3. Traverse the bigger list to the diff = l-m/m-l distance
4. Then traverse both the lists ( in this case as codeninja specified traverse the lists in chunks depending on the memory) and find if two nodes intersect

The above algo takes O(l+m) There is no need to sort the lists. If they are arrays then its even better, you can skip the traversing of diff length

Write a simple map reduce job.
Mapper: emit (element, 1)
Reducer: sum values and output if sum > 1.

Some points are not clear like what are the input to the function? An array or a linked list. What is the return type is it a linked list or an array??

// sort List1 and List 2 --> complexity = O(mlogm + nlogn)
int i, j;
i = 0; i = 0;
while(i < size of List1 and j < size of List 2)
{
if(A[i] == A[j])
{
print(A[i])
}
else if(A[i] > A[j])
{
i++;
}
else{
j++;
}
}

1. Create a hash table from the first list
2. Loop through second list and check if there is corresponding available value.
--> O(m+n)

For the memory limitation, thinking ...

1. Create a B+ Tree from List1, where each leaf is different file(As the list is very large, and can't loaded to whole list to memory at once).
2. For each element in List2, seach it from B+ tree(which is of List1).

T = O(M*Log(N)(of base k) + N*Log(N)(of base k).

N: Number of elements in List1.
M: Number of elements in List2.
k: B+ Tree is k-way tree.

1. Sort both arrays. If the arrays are from huge file sort the file using external merge sort.

2. In a single loop, read contents from each array and find the intersection using the simple algorithm below:

int a[] = {1, 3, 4,5,8,9, 9, 11};
int b[] = {3, 5, 6, 9, 9, 11, 23};


for(int i=0, j=0; i<a.length && j<b.length;) {
if(a[i] == b[j]) {
System.out.println(a[i]);
i++;j++;
}else if(a[i]<b[j]) {
i++;
}else {
j++;
}

}

I don't think any other solution exists.

Does anybody know what is map reduce?