这是一个创建于 3607 天前的主题，其中的信息可能已经有所发展或是发生改变。
我们做了一个专门面向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
邮件 [email protected]
如果你手里有更多的笔试面试题，也欢迎联系我们，重金求购哦~
昨日答题话费由 @omegaga，@sleeperqp，@xcv58 斩获。恭喜！
附昨日帖子地址 http://www.v2ex.com/t/159296
 |
1
nowcoder OP v2exer们，这题是太难了吗，求讨论！参与讨论获取v2ex金币(手工点感谢实现) -。-
|
 |
2
xcv58 2015-01-06 11:04:40 +08:00 via iPhone  1
貌似这个要用 Hadoop 跑一遍，分别拿 URL+分钟 和 IP+分钟 当 key，出现次数是 value。 和 word count 的应用场景简直一模一样。
|
|
4
xcv58 2015-01-06 11:16:51 +08:00 via iPhone
@rainday 这个数据量已经到 PB 级了，应该要用分布式的方案。其实难的地方在于如何 scale up
|
 |
5
wgwang 2015-01-06 11:46:47 +08:00 1
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呗。 |
 |
6
cxe2v 2015-01-06 11:54:20 +08:00 1
有这种查询要求的话，要根据时间段来分表吧？每隔一段时间或者超过多少数据就分表出来，这样，根据时间段就可以直接找到相应表来进行单条件查询了
|
 |
9
exch4nge 2015-01-06 12:14:40 +08:00 1
其实前面几楼说的都差不多了。
记录的处理与存储：将这1000亿条数据，根据时间段来进行分区，每段存在一个server里，时间段的长度，得根据具体的数据情况进行分析了。在这个过程中顺便对url进行一个hash处理并存储，hash算法的选择跟hash值的长短，可以sha-1，但是吧，虽然需求没讲，还有可能根据url的hostname之类的需求，如果考虑的话，那就自己设计个hash算法，前几位是hostname的hash值之类的……。ip的话，本身就是32位(ipv4)的数。 查询：两种查询都是带时间段的，所以得去存储了那个时间段的servers(可能不止一个)，他们自己再去算统计次数，最后将结果合并返回。 PS：有关按时间段的分区策略：最简单当然是按照连续的一段时间都分配给一个server了。但是这样的方法在查询的时候就比较蛋疼，忙的忙，闲的闲。如果不冗余存储的话，那就连续的时间段的数据依次轮回存储在server中，每个server存储的是不连续的时间段的数据。考虑冗余的话，可以一段数据存在多个地方，计算的时候都一起帮忙算。 哦，还是觉得麻烦那就上Hadoop工具吧…… |
 |
10
d0a1ccec 2015-01-06 13:16:15 +08:00 1
100块都不给我。
|
 |
11
xylophone21 2015-01-06 13:25:54 +08:00 1
除了上面的讨论,是否还要看你肯付出的资源的情况?
@exch4nge说的分区策略只在每台server都不能容忍完全存储数据并且不允许使用跨server存储的前提下有效. 否则每个server存一份,外加各种粒度的索引是不是时间更优(但存储空间更劣,内存空间差不多),因为无论如何分布,大家可以一起工作. 另外, Hadoop算作弊吧,这是面试题,不是实际解决问题啊. |
 |
12
Raindai 2015-01-06 14:21:26 +08:00 1
单机算法：KMP或者BM或者KR，对要查询的url或者IP进行预处理，复杂度O(n),n为
记录长度 集群算法：MapReduce果断的 |
 |
13
moonshile 2015-01-06 14:38:42 +08:00 1
同BM算法，如果文件长度为n，每条记录长度平均为l，模式串（url或者IP）长度为k，对一条记录查询，复杂度为O(l/k)，总复杂度为O(n/k)。
如果不匹配模式串的记录占多数，可以在每次匹配失败时之间跳过若干字节(时间字符串的长度)，则还可以优化常系数。 |
 |
14
ruoyu0088 2015-01-06 15:20:08 +08:00 1
下面是单机处理方案：
每个IP和每个URL一个文件，如果文件数太多，可以用子目录对文件进行分级。 子目录名可以通过简单的hash函数计算。 每个文件中保存以4个字节二进制数据表示的时间。如果原始数据中时间不是递增的， 在拆分完毕文件之后需要对每个文件中的时间进行排序。 如果文件过大无法载入内存，可以考虑基数外部排序。 以上准备工作完成之后，通过指定的URL或者IP计算出文件路径，然后对该文件进行 两次二分查找，查找时间段的起点和终点的偏移量。根据偏移量的差可以计算出 该区间的访问次数。 |
 |
15
pright 2015-01-06 17:07:55 +08:00 1
刚从知乎过来，结果看到类似的题了
|
 |
17
lsylsy2 2015-01-06 17:19:06 +08:00 1
1000亿条记录 每条1K 总数据=100TB
肯定要上集群 Hadoop Spark之类的； 然后基本思想类似wordcount，楼上已经说了； 要做优化的话，就分别按照url和ip做hash，分组；（应该会导致需要双倍的存储空间，分别处理url和ip的问题） 分组之后，因为query都是ip或url精确等于某个值，对其hash之后只需要查找对应的组即可。 |
 |
18
wenbinwu 2015-01-06 18:07:45 +08:00 1
收藏一下，学习知识 :)
|
 |
19
sumhat 2015-01-06 21:05:25 +08:00 1
这种题目还粗糙了，各种背景都没有介绍，比如时间跨度、每分钟最大访问量、URL分布等等，出题者的初衷可能和答题人的理解相差得十万八千里。
前几年去百度面试的时候碰到过类似的题目，我把各种单机算法都说了一遍，然后面试官一个劲地在暗示“桶排序”。尽管我已经说了分目录存储，和桶排序也类似，但看上去他一直都不满意我的答案。所以这类问题拿来面试通常得不好结果。 |
|
20
nowcoder OP @sumhat 面试官如果只是想着桶排序这种书面答案那当然得不到结果。 这些开放性的题目面试的好可以考察更多的能力。 只要你说的在理，解决合理，更能了解一个人对问题的思考性。 我们在工程中碰到条件也是千变万化的，根本没有千篇一律的书面答案，都是根据具体情况具体分析做解决方案的。
|
|
21
sumhat 2015-01-06 23:23:54 +08:00
@nowcoder 据我所知，一些公司（如微软和 Google）已经禁止面试开放性问题了。没有固定答案的问题就没有最优解，面试官面试了 1000 个人可能就有 1000 种不同的答案，每种答案在不同的工程环境中可能各有千秋，无法比较这些答案的好坏，总不能 1000 个人都招进来吧。 面试题不是饭后的闲聊，不是 brain storming。面试题的目标是找出更符合公司需求的员工。固定答案的问题，虽然有些刻板，但是很容易比较出两个求职者孰优孰略。
|
|
23
nowcoder OP |
 |
26
lixm 2015-01-07 18:39:08 +08:00
如果不要求非常精确， 可以使用基数估计统计算法来实现， 例如 hyperloglog++
|
|
27
wgwang 2015-01-11 15:26:13 +08:00
|
 |
29
Roboo 2015-01-16 23:06:25 +08:00
上去看了下 有些题明显都很旧了
当然这个题我是半天没看懂 储蓄盒中2分和5分的硬币的个数相等，2分和5分的钱数也相等，问：可能是多少元?() |
Select Language