[转]大数据处理三小题。Can you? ^_^

无挑战，不工作之三 - 开发工程师招聘



1：概述题

都知道数据库使用索引能够提高效率，为什么，用自己的理解简单描述。

这道题是后面n多题的基础。


2：实战题

引用

2.1
借了一道据说是腾讯面试的题目，和我当年在某公司商业分析部招聘的题目几乎一样，这道题很有代表性，拿出来说一下。
现在有个文件里有40亿条无重复整型数，为4字节无符号数，或者说，0 到 2的32次方。下面要求你写一个程序，列出所有 0 -2的32次方里，该文件不存在的整数。注意你的系统可用内存是有限的，也许只有1G或2G。如果这40亿条有重复，有什么区别？

 

引用

2.2
一个很典型常见问题，对用户做地区判定，比如新浪首页，百度新闻首页，会根据不同地区用户显示当地的新闻；比如百度，谷歌搜索结果会根据不同用户地区显示不同广告。这个是基于用户ip地址的，ip地址区间是国际组织分配的，非常散列，并不是严谨的顺序， 现在已知有10万段的ip地址对应段。在高并发情况下，如何在用户访问的时候快速返回该用户对应的地区，给出你的方法和要点。注意，效率是考核的关键，如果一秒钟无法实现超过1000次不同ip的查询结果（单台双至强服务器只做该查询的情况下），效率肯定不行的。

 

引用

2.3
又一个典型问题，目前政府有屏蔽词表，每个网站都要遵守，发帖的时候会自动替换屏蔽词；另一个场景是诸如新浪新闻等媒体往往有商业词表，发新闻的时候会自动建立关键词铆接。这个相当于一个简单的基于词典的分词系统，下面的问题就是，如何实现一个快速有效的，基于自定义词典精确匹配的分词系统，一是要满足每
天几万篇，几十万篇文章发布的要求；另一个必须的要求是，当词库倍增扩展时（比如10万词），效率的影响不允许是线性降低的。

如果您愿意接受挑战，与我们一起创业，创造大局面，欢迎将您的答案发送到 [e-mail]

，谢谢。优秀的答案我会尽可能回复，谢谢。

原文 ： http://hi.baidu.com/caoz/blog/item/2902baa153984b86471064fd.html

 

 

评论

4 楼 liguocai2009 2011-12-15  

ZeaLoVe 写道

ZeaLoVe 写道

第一题用编程珠玑的位图法轻松搞定。。。

定义一个bool数组 a[] 大小就2的32次方+1,然后全部初始化为0， 0表示数字没出现，1表示数字出现了。然后读入文件，出现数字N就把a[N]=1 重复的情况也差不多。读完文件后，扫描一次a数组就行了，输出里面等于0的数字就是文件中没出现的。
时间复杂度 O(2N)因为文件读入可能会有点慢。空间需要2的32次方/8 byte 大约0.5G

大概这样，不知道我的理解OK不？

关键是40亿个整数到内存就是14G+了？
而且存放结果用了2^32/8*2^30 = 0.5G.
如何利用读取和判断成了关键。

前面有提示，说要用到索引的思想哦。

3 楼 ZeaLoVe 2011-12-08  

ZeaLoVe 写道

第一题用编程珠玑的位图法轻松搞定。。。

定义一个bool数组 a[] 大小就2的32次方+1,然后全部初始化为0， 0表示数字没出现，1表示数字出现了。然后读入文件，出现数字N就把a[N]=1 重复的情况也差不多。读完文件后，扫描一次a数组就行了，输出里面等于0的数字就是文件中没出现的。
时间复杂度 O(2N)因为文件读入可能会有点慢。空间需要2的32次方/8 byte 大约0.5G

大概这样，不知道我的理解OK不？

2 楼 liguocai2009 2011-12-08  

看起来哥挺专业的，有什么好的大数据处理资料介绍一下？我们公司现在处理大量数据的时候老是内存溢出，然后宕机。往往都是一个arrayList放了20万+条数据。。。

1 楼 ZeaLoVe 2011-12-05  

第一题用编程珠玑的位图法轻松搞定。。。