chenbojian
V2EX  ›  问与答

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

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

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

    个人想法,纯文件+字符串查找的各种算法+分一下线程/进程.满足业务需求,简单可依赖。。你还想咋样= =!
    heimonsy
    heimonsy
    Dec 9, 2014
    17
    字典树
    About   ·   Help   ·   Advertise   ·   Blog   ·   API   ·   FAQ   ·   Privacy   ·   Solana   ·   2969 Online   Highest 6679   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 42ms · UTC 05:26 · PVG 13:26 · LAX 21:26 · JFK 00:26
    ♥ Do have faith in what you're doing.