V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
V2EX 提问指南
chenbojian
V2EX  ›  问与答

阿里测试面试的一个问题求教(大数据相关)

  •  
  •   chenbojian · 2014-12-07 17:44:00 +08:00 · 4572 次点击
    这是一个创建于 3400 天前的主题,其中的信息可能已经有所发展或是发生改变。
    吐槽下原来测试校招都不面算法。。。
    问题是这样,一个文件有几十亿条商品的名称,要从中查找是否包含iphone这件商品有什么好的方法?
    可以改数据存储方式,有什么好的方案吗?
    17 条回复    2014-12-09 10:29:40 +08:00
    kenneth
        1
    kenneth  
       2014-12-07 17:59:28 +08:00
    问这种问题的人,一般喜欢装逼,所以不要理他。聊点别的。。。
    chenbojian
        2
    chenbojian  
    OP
       2014-12-07 18:21:19 +08:00
    @kenneth 。。。哈哈,那样会挂的更快的,虽然确实挂了。
    imn1
        3
    imn1  
       2014-12-07 18:31:38 +08:00
    向这几十亿条商家公布联络方式,如果没一个来推销 iphone,那就是不包含
    EPr2hh6LADQWqRVH
        4
    EPr2hh6LADQWqRVH  
       2014-12-07 18:38:10 +08:00
    告诉他没有什么好的方案
    no magic
    chenbojian
        5
    chenbojian  
    OP
       2014-12-07 19:13:05 +08:00
    @avastms 我觉得他是一只想问我分布式存储的东西,但是我确实不是很了解,所以没往这方面说。
    nolouch
        6
    nolouch  
       2014-12-07 19:57:59 +08:00 via Android
    阿里现在还有校招?
    ziyuan
        7
    ziyuan  
       2014-12-07 20:40:13 +08:00
    分布式计算,合并结果,hadoop hdbase之类的
    angeloce
        8
    angeloce  
       2014-12-07 21:47:52 +08:00
    这就是简单的倒排吧。 商品名称, 描述分词, 以词建索引。 按hash查, 保证iphone不被分词开就行了。 什么分布式计算啥的, 随便扯扯。
    chenbojian
        9
    chenbojian  
    OP
       2014-12-07 23:00:56 +08:00
    @nolouch 两三个星期前吧,可能算补招,是我9月份时候投的简历,当时觉得测试要求低就投了结果把自己坑了
    chenbojian
        10
    chenbojian  
    OP
       2014-12-07 23:10:44 +08:00
    @angeloce 这种方案我知道,当时被他那种不把问题说清楚的问问题方式给唬住了(最开始还不说可以改数据结构,然后问他他说随便,随便设计。。。汗),说了个文件里面建字典的方式,比如第一行存储i开头的字符串在哪一行。。。
    spacewander
        11
    spacewander  
       2014-12-07 23:11:21 +08:00
    丢数据库去
    spacewander
        12
    spacewander  
       2014-12-07 23:11:41 +08:00
    这个远远不算大数据吧
    chenbojian
        13
    chenbojian  
    OP
       2014-12-07 23:13:12 +08:00
    @spacewander 我也很想跟他这么说。。。。但是我以为他要考我大数据算法什么的。。。然后想想只找一个和找前几个这种不一样。。。没遇到过会面设计数据存储方案的
    takato
        14
    takato  
       2014-12-07 23:50:56 +08:00
    扔进Hadoop+Hive去跑就是了。。。不慢的。。。以前我的部门就是那么搞的。。
    paulw54jrn
        15
    paulw54jrn  
       2014-12-08 06:11:51 +08:00
    突然想起以前老师上课讲的东西..
    文件经过一次O(n)的转换后,可以进行O(m)时间复杂度的字符串检索..
    这里的m与检索字符(不是待检索字符)长度正相关... 同时可以与RLE+LZW结合在一起..

    http://alexbowe.com/fm-index/
    http://www.cs.jhu.edu/~langmea/resources/bwt_fm.pdf
    sampeng
        16
    sampeng  
       2014-12-08 22:58:55 +08:00
    不是慢不慢的问题。。这个数据量,不是非常懂算法的,有经验的。都不会扔hadoop+hive。。那点硬件成本和维护成本,还不够程序员写个程序来干的呢。。

    个人想法,纯文件+字符串查找的各种算法+分一下线程/进程.满足业务需求,简单可依赖。。你还想咋样= =!
    heimonsy
        17
    heimonsy  
       2014-12-09 10:29:40 +08:00
    字典树
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   我们的愿景   ·   实用小工具   ·   4183 人在线   最高记录 6543   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 27ms · UTC 10:12 · PVG 18:12 · LAX 03:12 · JFK 06:12
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.