这是一个创建于 3481 天前的主题，其中的信息可能已经有所发展或是发生改变。
看到一哥们发的面试题，我突然想起来，刚毕业那会找工作有人问过我这个一个问题：
现有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 亲 是任意长度的字符串
|
Select Language