Find common elements from two very large Arrays

Question

There are two integer arrays ,each in very large files (size of each is larger than RAM). How would you find the common elements in the arrays in linear time.

I cant find a decent solution to this problem. Any ideas?

Answer 1

One pass on one file build a bitmap (or a Bloom filter if the integer range is too large for a bitmap in memory).

One pass on the other file find the duplicates (or candidates if using a Bloom filter).

If you use a Bloom filter, the result is probabilistic. New passes can reduce the false positive (Bloom filters don't have false negative).