Algorithm

1. How to find common elements in two files that contains million of records.
ans : using B trees ( B+ or B* depending on application)
2. Better algorithms to find Array elements such that sum of 3 numbers will be equal to given number X.
Ans : known answer is O(n^2).
3. How do you find duplicates in the given array of size K and contains number form 0 to n-1. with complexity O(n) and constant space
Ans : very easy :
important step : for i = 1->n a[a[i]] == a[i]; if( a[i] !=i ) ->duplicate
else swap a[i] ,a[a[i]] and go to previous step
3. Now how about if this restriction of intergers from 0 to n-1 are removed.
Ans : tough: ( i will deeply apprecate if anybody comes with better idea)
important step : use unique factorization . define P(x) = y where y is prime number positioned for number x. for example P(1) =2 ; P(2) =3; p(3) =5 ...
factorization_result = 1 ; for i = 1 ->k factorization_result * = P(i) ;
Now factorize : factorization_result = y1 * y2 * ....Yn ; where yi = yi+j for some j
if such j exist then P^-1 (yi) is duplicated.
Note : Partical implementation is not easy. as P(x) itself doesn't work great for large x
Now, there is other solution also suggested:
idea : multiHeader list