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

V2EX = way to explore

V2EX 是一个关于分享和探索的地方

现在注册

已注册用户请登录

V2EX 提问指南

这是一个创建于 3667 天前的主题，其中的信息可能已经有所发展或是发生改变。

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

大数据

求教

商品

17 条回复 • 2014-12-09 10:29:40 +08:00

kenneth

2014-12-07 17:59:28 +08:00

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

chenbojian

2014-12-07 18:21:19 +08:00

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

imn1

2014-12-07 18:31:38 +08:00

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

EPr2hh6LADQWqRVH

2014-12-07 18:38:10 +08:00

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

chenbojian

2014-12-07 19:13:05 +08:00

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

nolouch

2014-12-07 19:57:59 +08:00 via Android

阿里现在还有校招？

ziyuan

2014-12-07 20:40:13 +08:00

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

angeloce

2014-12-07 21:47:52 +08:00

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

chenbojian

2014-12-07 23:00:56 +08:00

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

chenbojian

2014-12-07 23:10:44 +08:00

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

spacewander

2014-12-07 23:11:21 +08:00

丢数据库去

spacewander

2014-12-07 23:11:41 +08:00

这个远远不算大数据吧

chenbojian

2014-12-07 23:13:12 +08:00

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

takato

2014-12-07 23:50:56 +08:00

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

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

2014-12-08 22:58:55 +08:00

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

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

heimonsy

2014-12-09 10:29:40 +08:00

字典树