看到一哥们发的面试题,我突然想起来,刚毕业那会找工作有人问过我这个一个问题:
现有10+位数(9,999,999,999)的关键字组成的一个词典
用户输入(n)个字数,要求使用纯 php(不可以使用php内置函数,不可以使用c语言扩展) 逐字匹配,词典内的关键字,效率应低于30毫秒以内。
然后,我想了很久,就说只能把常见关键词做一个热度顺序,用贝叶斯方法去实现,但是效率。。。
然后,我就问正确的方法是什么啊,然后,被鄙视了一番,然后也没有告诉我正确的方法,然后就被 pass了
后来lz成了c/cpp程序员,然后这么多年过去了,我到现在也没明白这个问题用纯 php 应该怎么解决
哈哈哈
1
omengye 2015-05-16 00:27:11 +08:00 via Android
单词查找树?
|
2
whatisnew OP @omengye 当时一下子紧张的不得了,尼玛刚毕业就问我这么高深的问题,我在脑海里先把他的要求过了一遍,然后,突然想到贝叶斯的算法(其实很多垃圾邮件的过滤算法也是基于贝叶斯),就抛出来了这么一句。其实被鄙视完了之后,我本来要求实习工资5k的,他说我基础差3k就很高了,然后,我就说这个大家都是5k,然后就被拒绝了,后来楼主去了当时最火的一个游戏公司做了 c/cpp 程序员,工资5k,哈哈哈
|
3
b821025551b 2015-05-16 00:33:51 +08:00
foreach ($array as $k => $v){
if($v==='xxx'){ result[$k] = $v; } return result; |
4
whatisnew OP @b821025551b 亲。。。你这个明显不行啊
我举个例子,用户输入10位数的中文字,字典里有10位数的中文字,复杂程度是 O(n) 的99999999/2*999999999倍,这样的话 foreach 是找死啊 |
5
messyidea 2015-05-16 00:38:42 +08:00 via Android
我想到了ac自动机
|
6
omengye 2015-05-16 00:39:54 +08:00 via Android
@whatisnew 哈哈 楼主当年运气不错。现在找工作啥的先看算法好不好,不好就没个好印象了,其他问题也懒得问。。。
|
7
whatisnew OP @omengye 其实工作这么多年,我也问过几个高级php工程师,他们都说不太可能的。我估计当时面试的人就是为了压低的的实习工资。。。
|
8
b821025551b 2015-05-16 00:46:24 +08:00
@whatisnew 如果是我去做那个面试,我就会这么回答;这道题考的不是算法,而是情商。
|
10
shiny 2015-05-16 01:19:05 +08:00
记得有人用 trie 树来做过,不过是扩展,不知道纯 PHP 效果如何。
|
11
laoyuan 2015-05-16 08:22:20 +08:00
php 又没有词典,这些关键字是保存在文本文件里么?怎么也得几十G,内存装不下啊
|
12
laoyuan 2015-05-16 09:47:24 +08:00
就算关键字数据总共100G,对关键字取MD5,存3层文件夹,每层256个,总共256^3 个文件,每个文件就不到6K了,目标关键字取MD5,直接定位文件,肯定30毫秒以内
|
13
zhangcc 2015-05-17 15:10:21 +08:00
我觉得问这样的问题就是脑残,如果能用php内置函数或者c扩展来写算法(能试算法更优),那谁几把实际开发中用纯php啊
|
14
whahuzhihao 2015-05-22 21:39:16 +08:00
匹配 是指判断字典里有没有这个数字吗?
如果是的话,用trie树呀,10位数字而已 |
15
whatisnew OP @whahuzhihao 亲 是任意长度的字符串
|