原文: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条数据;若内存装不下,则同上几个问题一样采用分治的原则,将数据分开处理,最后再合并。