V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
nowcoder
V2EX  ›  程序员

悬赏大牛解答求职难题, 100 块给你( 1 月 6 日更新)

  •  
  •   nowcoder · 2015-01-06 10:21:55 +08:00 · 4699 次点击
    这是一个创建于 3591 天前的主题,其中的信息可能已经有所发展或是发生改变。

    我们做了一个专门面向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

    29 条回复    2015-01-16 23:06:25 +08:00
    nowcoder
        1
    nowcoder  
    OP
       2015-01-06 10:59:47 +08:00
    v2exer们,这题是太难了吗,求讨论!参与讨论获取v2ex金币(手工点感谢实现) -。-
    xcv58
        2
    xcv58  
       2015-01-06 11:04:40 +08:00 via iPhone   ❤️ 1
    貌似这个要用 Hadoop 跑一遍,分别拿 URL+分钟 和 IP+分钟 当 key,出现次数是 value。 和 word count 的应用场景简直一模一样。
    rainday
        3
    rainday  
       2015-01-06 11:08:04 +08:00
    @xcv58 Hadoop根据时间片分区思路挺好的,作为校招的题目应该主要是考察学生分区归并思路。
    xcv58
        4
    xcv58  
       2015-01-06 11:16:51 +08:00 via iPhone
    @rainday 这个数据量已经到 PB 级了,应该要用分布式的方案。其实难的地方在于如何 scale up
    wgwang
        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呗。
    cxe2v
        6
    cxe2v  
       2015-01-06 11:54:20 +08:00   ❤️ 1
    有这种查询要求的话,要根据时间段来分表吧?每隔一段时间或者超过多少数据就分表出来,这样,根据时间段就可以直接找到相应表来进行单条件查询了
    rainday
        7
    rainday  
       2015-01-06 11:56:07 +08:00
    @wgwang 这些提问真好,考虑问题很周全。在实际的开发过程中,根据具体的数据特性做优化往往能达到意想不到的好效果~
    rainday
        8
    rainday  
       2015-01-06 11:57:01 +08:00
    @cxe2v 我知道一家上亿用户的app,他们的feed流技术是根据时间分表的。
    exch4nge
        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工具吧……
    d0a1ccec
        10
    d0a1ccec  
       2015-01-06 13:16:15 +08:00   ❤️ 1
    100块都不给我。
    xylophone21
        11
    xylophone21  
       2015-01-06 13:25:54 +08:00   ❤️ 1
    除了上面的讨论,是否还要看你肯付出的资源的情况?

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

    另外, Hadoop算作弊吧,这是面试题,不是实际解决问题啊.
    Raindai
        12
    Raindai  
       2015-01-06 14:21:26 +08:00   ❤️ 1
    单机算法:KMP或者BM或者KR,对要查询的url或者IP进行预处理,复杂度O(n),n为
    记录长度

    集群算法:MapReduce果断的
    moonshile
        13
    moonshile  
       2015-01-06 14:38:42 +08:00   ❤️ 1
    同BM算法,如果文件长度为n,每条记录长度平均为l,模式串(url或者IP)长度为k,对一条记录查询,复杂度为O(l/k),总复杂度为O(n/k)。

    如果不匹配模式串的记录占多数,可以在每次匹配失败时之间跳过若干字节(时间字符串的长度),则还可以优化常系数。
    ruoyu0088
        14
    ruoyu0088  
       2015-01-06 15:20:08 +08:00   ❤️ 1
    下面是单机处理方案:

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

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

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

    以上准备工作完成之后,通过指定的URL或者IP计算出文件路径,然后对该文件进行
    两次二分查找,查找时间段的起点和终点的偏移量。根据偏移量的差可以计算出
    该区间的访问次数。
    pright
        15
    pright  
       2015-01-06 17:07:55 +08:00   ❤️ 1
    刚从知乎过来,结果看到类似的题了
    nowcoder
        16
    nowcoder  
    OP
       2015-01-06 17:16:13 +08:00
    @pright 知乎上什么答案,请发下链接。。
    lsylsy2
        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之后只需要查找对应的组即可。
    wenbinwu
        18
    wenbinwu  
       2015-01-06 18:07:45 +08:00   ❤️ 1
    收藏一下,学习知识 :)
    sumhat
        19
    sumhat  
       2015-01-06 21:05:25 +08:00   ❤️ 1
    这种题目还粗糙了,各种背景都没有介绍,比如时间跨度、每分钟最大访问量、URL分布等等,出题者的初衷可能和答题人的理解相差得十万八千里。

    前几年去百度面试的时候碰到过类似的题目,我把各种单机算法都说了一遍,然后面试官一个劲地在暗示“桶排序”。尽管我已经说了分目录存储,和桶排序也类似,但看上去他一直都不满意我的答案。所以这类问题拿来面试通常得不好结果。
    nowcoder
        20
    nowcoder  
    OP
       2015-01-06 22:02:19 +08:00
    @sumhat 面试官如果只是想着桶排序这种书面答案那当然得不到结果。 这些开放性的题目面试的好可以考察更多的能力。 只要你说的在理,解决合理,更能了解一个人对问题的思考性。 我们在工程中碰到条件也是千变万化的,根本没有千篇一律的书面答案,都是根据具体情况具体分析做解决方案的。
    sumhat
        21
    sumhat  
       2015-01-06 23:23:54 +08:00
    @nowcoder 据我所知,一些公司(如微软和 Google)已经禁止面试开放性问题了。没有固定答案的问题就没有最优解,面试官面试了 1000 个人可能就有 1000 种不同的答案,每种答案在不同的工程环境中可能各有千秋,无法比较这些答案的好坏,总不能 1000 个人都招进来吧。 面试题不是饭后的闲聊,不是 brain storming。面试题的目标是找出更符合公司需求的员工。固定答案的问题,虽然有些刻板,但是很容易比较出两个求职者孰优孰略。
    nowcoder
        22
    nowcoder  
    OP
       2015-01-06 23:47:52 +08:00
    @sumhat 各有优缺点,固定的话那就容易刷题。
    nowcoder
        23
    nowcoder  
    OP
       2015-01-07 10:03:41 +08:00
    @exch4nge @ruoyu0088 @xylophone21 @wgwang 感谢细心讨论,请大家发手机号码到[email protected] 我们给你充值。
    wgwang
        24
    wgwang  
       2015-01-07 10:58:10 +08:00
    @nowcoder 可以直接给v2ex充值不?
    nowcoder
        25
    nowcoder  
    OP
       2015-01-07 11:02:24 +08:00
    @wgwang v2ex可以转让金币吗?
    lixm
        26
    lixm  
       2015-01-07 18:39:08 +08:00
    如果不要求非常精确, 可以使用基数估计统计算法来实现, 例如 hyperloglog++
    wgwang
        27
    wgwang  
       2015-01-11 15:26:13 +08:00
    @nowcoder 支付宝充值后,直接填入我的帐号就可以了, 参考:
    http://www.v2ex.com/balance/add/alipay
    nowcoder
        28
    nowcoder  
    OP
       2015-01-11 23:44:13 +08:00
    @wgwang v2ex马上就要上线铜币转让功能了,可以等下吗? :-) 到时候我账户内的铜币转让给你。
    Roboo
        29
    Roboo  
       2015-01-16 23:06:25 +08:00
    上去看了下 有些题明显都很旧了
    当然这个题我是半天没看懂
    储蓄盒中2分和5分的硬币的个数相等,2分和5分的钱数也相等,问:可能是多少元?()
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   实用小工具   ·   1245 人在线   最高记录 6679   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 25ms · UTC 23:12 · PVG 07:12 · LAX 15:12 · JFK 18:12
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.