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