我们做了一个专门面向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分的钱数也相等,问:可能是多少元?() |