悬赏大牛解答求职难题， 100 块给你（ 1 月 6 日更新）

[nowcoder]

我们做了一个专门面向IT互联网行业程序员的求职笔试面试备考的题库网站
牛客网 http://www.nowcoder.com?from=v2ex
里面积累了谷歌、腾讯、百度等几十家互联网公司的笔试面试题目。但网站当前有部分题目还没有楼主觉得认可的最佳答案和解释，为了更好的服务程序猿们，我们做了一个活动，悬赏大牛解答，每道题目根据难度对应一定的现金奖励，最高一道题目奖励100元，还有iPhone6、移动硬盘、小米手环等众多好礼相送。

从今天开始到1月29日，我们会在论坛持续更新本贴，每天放出1-3道题目，欢迎大家跟帖解答，最先正确解答出来的朋友将会获得话费充值、笔记本等礼物。获奖的朋友名单会在第二天公布。

今日题目来自百度，答题正确奖金100，任性～：

有1000亿条记录，每条记录由url,ip,时间组成，设计一个系统能够快速查询以下内容
1.给定url和时间段（精确到分钟）统计url的访问次数
2.给定ip和时间段（精确到分钟）统计ip的访问次数

更多有奖答题： http://www.nowcoder.com/activity/challenge?from=v2ex

欢迎大家关注我们，活动结束后我们会把面试题整理成PDF分发给参与的用户
微博 http://www.weibo.com/nowcoder
微信 www_nowcoder_com
技术QQ群 157594705
邮件 [e-mail]
如果你手里有更多的笔试面试题，也欢迎联系我们，重金求购哦~

昨日答题话费由 @omegaga，@sleeperqp，@xcv58 斩获。恭喜！
附昨日帖子地址 http://www.v2ex.com/t/159296

[nowcoder]

v2exer们，这题是太难了吗，求讨论！参与讨论获取v2ex金币(手工点感谢实现) -。-

[xcv58]

貌似这个要用 Hadoop 跑一遍，分别拿 URL+分钟 和 IP+分钟 当 key，出现次数是 value。 和 word count 的应用场景简直一模一样。

[rainday]

@xcv58 Hadoop根据时间片分区思路挺好的，作为校招的题目应该主要是考察学生分区归并思路。

[xcv58]

@rainday 这个数据量已经到 PB 级了，应该要用分布式的方案。其实难的地方在于如何 scale up

[wgwang]

1.给定url和时间段（精确到分钟）统计url的访问次数
2.给定ip和时间段（精确到分钟）统计ip的访问次数

使用场景是什么？ 时间范围是什么？ unique的url有多少的量？ unique的ip有多少的量？
这些数据的量不一样， 决定了处理方法完全不一样。

比如， 1000亿的数据中，unique 的url数量有100个，时间范围是1天， unique的ip数为1万个，那流式扫描原始数据，统计出结果后直接扔个数据库就行了。

反过来，如果1000亿中，qunique的(url, 时间）组合接近1000亿，那要统计精确数量，只能用hadoop等工具，写个简单的mr，跑一段时间就出来了。估计的话，那么大概就1呗。

[cxe2v]

有这种查询要求的话，要根据时间段来分表吧？每隔一段时间或者超过多少数据就分表出来，这样，根据时间段就可以直接找到相应表来进行单条件查询了

[rainday]

@wgwang 这些提问真好，考虑问题很周全。在实际的开发过程中，根据具体的数据特性做优化往往能达到意想不到的好效果～

[rainday]

@cxe2v 我知道一家上亿用户的app，他们的feed流技术是根据时间分表的。

[exch4nge]

其实前面几楼说的都差不多了。

记录的处理与存储：将这1000亿条数据，根据时间段来进行分区，每段存在一个server里，时间段的长度，得根据具体的数据情况进行分析了。在这个过程中顺便对url进行一个hash处理并存储，hash算法的选择跟hash值的长短，可以sha-1，但是吧，虽然需求没讲，还有可能根据url的hostname之类的需求，如果考虑的话，那就自己设计个hash算法，前几位是hostname的hash值之类的……。ip的话，本身就是32位(ipv4)的数。

查询：两种查询都是带时间段的，所以得去存储了那个时间段的servers(可能不止一个)，他们自己再去算统计次数，最后将结果合并返回。

PS：有关按时间段的分区策略：最简单当然是按照连续的一段时间都分配给一个server了。但是这样的方法在查询的时候就比较蛋疼，忙的忙，闲的闲。如果不冗余存储的话，那就连续的时间段的数据依次轮回存储在server中，每个server存储的是不连续的时间段的数据。考虑冗余的话，可以一段数据存在多个地方，计算的时候都一起帮忙算。

哦，还是觉得麻烦那就上Hadoop工具吧……

[d0a1ccec]

100块都不给我。

[xylophone21]

除了上面的讨论,是否还要看你肯付出的资源的情况?

@exch4nge说的分区策略只在每台server都不能容忍完全存储数据并且不允许使用跨server存储的前提下有效.
否则每个server存一份,外加各种粒度的索引是不是时间更优(但存储空间更劣,内存空间差不多),因为无论如何分布,大家可以一起工作.

另外, Hadoop算作弊吧,这是面试题,不是实际解决问题啊.

[Raindai]

单机算法：KMP或者BM或者KR，对要查询的url或者IP进行预处理，复杂度O(n),n为
记录长度

集群算法：MapReduce果断的

[moonshile]

同BM算法，如果文件长度为n，每条记录长度平均为l，模式串（url或者IP）长度为k，对一条记录查询，复杂度为O(l/k)，总复杂度为O(n/k)。

如果不匹配模式串的记录占多数，可以在每次匹配失败时之间跳过若干字节(时间字符串的长度)，则还可以优化常系数。

[ruoyu0088]

下面是单机处理方案：

每个IP和每个URL一个文件，如果文件数太多，可以用子目录对文件进行分级。
子目录名可以通过简单的hash函数计算。

每个文件中保存以4个字节二进制数据表示的时间。如果原始数据中时间不是递增的，
在拆分完毕文件之后需要对每个文件中的时间进行排序。

如果文件过大无法载入内存，可以考虑基数外部排序。

以上准备工作完成之后，通过指定的URL或者IP计算出文件路径，然后对该文件进行
两次二分查找，查找时间段的起点和终点的偏移量。根据偏移量的差可以计算出
该区间的访问次数。

[pright]

刚从知乎过来，结果看到类似的题了

[nowcoder]

@pright 知乎上什么答案，请发下链接。。

[lsylsy2]

1000亿条记录 每条1K 总数据=100TB
肯定要上集群 Hadoop Spark之类的；
然后基本思想类似wordcount，楼上已经说了；
要做优化的话，就分别按照url和ip做hash，分组；（应该会导致需要双倍的存储空间，分别处理url和ip的问题）
分组之后，因为query都是ip或url精确等于某个值，对其hash之后只需要查找对应的组即可。

[wenbinwu]

收藏一下，学习知识 :)

[sumhat]

这种题目还粗糙了，各种背景都没有介绍，比如时间跨度、每分钟最大访问量、URL分布等等，出题者的初衷可能和答题人的理解相差得十万八千里。

前几年去百度面试的时候碰到过类似的题目，我把各种单机算法都说了一遍，然后面试官一个劲地在暗示“桶排序”。尽管我已经说了分目录存储，和桶排序也类似，但看上去他一直都不满意我的答案。所以这类问题拿来面试通常得不好结果。

[nowcoder]

@sumhat 面试官如果只是想着桶排序这种书面答案那当然得不到结果。 这些开放性的题目面试的好可以考察更多的能力。 只要你说的在理，解决合理，更能了解一个人对问题的思考性。 我们在工程中碰到条件也是千变万化的，根本没有千篇一律的书面答案，都是根据具体情况具体分析做解决方案的。