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

[chenbojian]

吐槽下原来测试校招都不面算法。。。
问题是这样，一个文件有几十亿条商品的名称，要从中查找是否包含iphone这件商品有什么好的方法？
可以改数据存储方式，有什么好的方案吗？

[kenneth]

问这种问题的人，一般喜欢装逼，所以不要理他。聊点别的。。。

[chenbojian]

@kenneth 。。。哈哈，那样会挂的更快的，虽然确实挂了。

[imn1]

向这几十亿条商家公布联络方式，如果没一个来推销 iphone，那就是不包含

[EPr2hh6LADQWqRVH]

告诉他没有什么好的方案
no magic

[chenbojian]

@avastms 我觉得他是一只想问我分布式存储的东西，但是我确实不是很了解，所以没往这方面说。

[nolouch]

阿里现在还有校招？

[ziyuan]

分布式计算，合并结果，hadoop hdbase之类的

[angeloce]

这就是简单的倒排吧。 商品名称， 描述分词， 以词建索引。 按hash查， 保证iphone不被分词开就行了。 什么分布式计算啥的， 随便扯扯。

[chenbojian]

@nolouch 两三个星期前吧，可能算补招，是我9月份时候投的简历，当时觉得测试要求低就投了结果把自己坑了

[chenbojian]

@angeloce 这种方案我知道，当时被他那种不把问题说清楚的问问题方式给唬住了(最开始还不说可以改数据结构，然后问他他说随便，随便设计。。。汗)，说了个文件里面建字典的方式，比如第一行存储i开头的字符串在哪一行。。。

[spacewander]

丢数据库去

[spacewander]

这个远远不算大数据吧

[chenbojian]

@spacewander 我也很想跟他这么说。。。。但是我以为他要考我大数据算法什么的。。。然后想想只找一个和找前几个这种不一样。。。没遇到过会面设计数据存储方案的

[takato]

扔进Hadoop+Hive去跑就是了。。。不慢的。。。以前我的部门就是那么搞的。。

[paulw54jrn]

突然想起以前老师上课讲的东西..
文件经过一次O(n)的转换后,可以进行O(m)时间复杂度的字符串检索..
这里的m与检索字符(不是待检索字符)长度正相关... 同时可以与RLE+LZW结合在一起..

http://alexbowe.com/fm-index/
http://www.cs.jhu.edu/~langmea/resources/bwt_fm.pdf

[sampeng]

不是慢不慢的问题。。这个数据量，不是非常懂算法的，有经验的。都不会扔hadoop+hive。。那点硬件成本和维护成本，还不够程序员写个程序来干的呢。。

个人想法，纯文件+字符串查找的各种算法+分一下线程/进程.满足业务需求，简单可依赖。。你还想咋样= =！

[heimonsy]

字典树