扫码关注公众号
给定a、b两个文件,各存放50亿个url,每个url各占64字节,内存限制是4G,找出a、b文件共同的url
思路:先计算总的数据大小,看能不能一次性放到内存里 ·50亿=5,000,000,000≈5G, 
从2.5亿个整数中找出不重复的整数,内存不足以容纳这2.5亿个整数
思路:思路一:使用例一的思路,切分成小文件,后面对每个小文件逐一比较思路二:对整数,可以考虑用位图法,因为本题需要辨别不存在、出现一次和出现
一个分布式系统的海量数据分布在100台服务器中,怎么统计出这些数据的TOP10
思路:先对每台服务器的数据求得各自的TOP10,然后把100*10=1000个数据求得TOP10即可。对每台服务器,按例一的方法切分成小文件
要从1000个数据元素中选五个最小的,下面排序算法中,那个算法最快?()
正确答案是C简单选择排序,每轮选出最小的一个元素,那么5轮就完成了任务,比较次数为1000+999+998+997+996=5000-10=4990次。而C选项,堆排序,首先需要建堆,建堆时间复杂度是O(n),根据《算法导论》上chap6的公式推导,建堆时间的上界是O(2n),那么需要2000次比较。接下来依次挑选最小的元素,每次挑选完一个元素,都需要重新调整堆,调整堆的时间复杂度为O(logn)。根据《算法导论》的推导是T(n)<=T(2n/3)+O(1),把n=1024带入,发现对调整时间大约为10次,并且推导中的O(1)时间是用于调整根节点、左儿子、右儿子这3个节点的时间,显然时间开销小于10次,那么5次取最小元素的时间开销就小于5*10*10=500,所以总时间开销不足2500次。