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

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

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

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