原文：https://blog.nowcoder.net/n/dd52e794d6ba4474b6f9de52f23b16fa

1、现在有1亿个随机数，有重复的，随机数的范围在1到1亿之间，将1到1亿之间没有在随机数中的数求出来。

/**
 * 用位图进行存储，产生随机数存入bitSet中相应的位置，并置1。
 * 如果bitSet中相应位置为1则此数出现过，如果为0则未出现过。
 * */

public static void main(String[] args) {
    BitSet bitSet = new BitSet();
    Random random = new Random();
    for (int i = 1; i <= 100000000; i++) {
        bitSet.set(random.nextInt(100000000));
    }
    for (int i = 1; i <= 100000000; i++) {
        //如果没有出现，就输出该数字
        if (!bitSet.get(i))
            System.out.println(i);
    }
}

2、有a和b两个文件，每个文件中均存放了50亿条url，已知每条url所占内存大约64字节，你在可使用内存在4G的情况下，如何找出a、b文件共同的url。

假如每个url大小为10bytes，那么可以估计每个文件的大小为50G×64=320G，远远大于内存限制的4G，所以不可能将其完全加载到内存中处理，可以采用分治的思想来解决。

首先遍历文件a，对每个url求取url.hashCode()%1000，然后根据所取得的值将url分别存储到1000个小文件(记为a0,a1,...,a999，每个小文件约300M);接着遍历文件b，采取和a相同的方式将url分别存储到1000个小文件(记为b0,b1,...,b999);这样处理后，所有可能相同的url都被保存在对应的小文件(如a0和b0，a1和b1)中，不对应的小文件不可能有相同的url。然后我们只要求出这个1000对小文件中相同的url即可。最后，求每对小文件ai和bi中相同的url时，可以把ai的url存储到HashSet中。然后遍历bi的每个url，看其是否在刚才构建的HashSet中，如果是，那么就是共同的url，存到文件里面就可以了。

3、现有海量日志数据保存在一个超级大的文件中，该文件无法直接读入内存，要求从中提取某天出访问网站次数最多的那个IP。

首先，从这一天的日志数据中把访问百度的IP取出来，逐个写入到一个大文件中;对每个ip求取ip.hashCode()%1000存入1000个小文件中。接着，找出每个小文中出现频率最大的IP(可以采用HashMap进行频率统计，然后再找出频率最大的几个)及相应的频率；最后，在这1000个最大的IP中，找出那个频率最大的IP，即为所求。

4、现在有100万个数字，找出其中最大的100个数。

选前100个数建立一个最小堆，遍历一遍，如果当前数比堆顶大就和堆顶元素交换，接着调整堆，就可以得到最大的100个数。

说明：找最大的N个数用最小堆，找最小的N个数用最大堆，Java中可以使用PriorityQueue。

5、现有上亿条数据（有重复的），统计其中出现次数最多的K条数据。

若内存可以放下则先遍历数据，用HashMap统计此数，接着简历K个数的小顶堆进行遍历替换，如果当前元素大于堆顶元素则替换掉堆顶元素后调整堆，最后就可以找出最多的K条数据；若内存装不下，则同上几个问题一样采用分治的原则，将数据分开处理，最后再合并。