首页 > 网络 > 云计算 >

大数据题的解法总结

2017-04-14

大数据题的解法总结,1 网页黑名单系统,垃圾邮件过滤,爬虫网址判重。

1.网页黑名单系统,垃圾邮件过滤,爬虫网址判重

空间有限制,允许一定的错误率

使用布隆过滤器来做

2.内存限制下,找到很多数中出现次数最多的数

用hash来做,key是数字,value是次数

进阶:将这些数用hash分成若干份,对每一份进行hash计算个数,最后再对每一份的最多的数进行判断,找到全局最多的数。

3.在一堆数中找到没出现的数

用bit数组来做,数组长度就是题目中给的数的范围,遍历,有就标1,最后位置0的就是没出现的。

进阶:内存更少,但只需找到1个

把范围等分成若干区间,第一次遍历,每个区间计数,必然有区间的个数是少于区间长度的,第二次遍历,设一个区间的大小的bit数组,只关心落在该区间的数,有就标1,最后没有的就是的。

4.找出很多数或者其他类似URL之类的,所有重复的

用hash分到不同机器,或者分成小文件。

在每个分区里面找重复的,可以用bitmap来做,遇到已经有标记的就是重复的。

5统计TOPK,热门域名啊,热门单词啊

还是用hash分区,每个分区用map统计单词和个数。每个分区用大小为K的最大堆来排序,得到每个分区的TOPK。然后把每个分区的TOPK组合,再用大小为K的最大堆排序。

6.一堆数,找到所有出现2次的数。

用2个长度为数范围的bit数组,遍历,第一次出现,标01,第二次10,第三次11,再出现就不管了,最后遍历bit数组,是10的就OK了。

7.找中位数,可使用的内存很小

分区,每个分区的范围小于内存,遍历,出现就在对应的位置++,得到每个区间数出现的情况。累加每个区间出现数的个数,就知道中位数落在哪个区间上。再申请一个分区,大小跟原来一样,只关心中位数所在区间,遍历,对该区间做词频统计,该区间找到那个中位数。

相关文章
最新文章
热点推荐