腾讯php程序员面试题目答案――编程任务
编程任务:
1、 我们碰到了大麻烦,一个新来的传教士惹恼了上帝,上帝很愤怒,要求我们把圣经(bbe.txt)背熟,直至他说哪个单词,我们就要飞快的回答出这个单词在 第几行第几个单词位置。听说你是个优秀的程序员,那么髟助我们完成这个不可能的任务吧。
要求如下:
1)/myworks /example/bbe.txt,98版本英文圣经一本
2)输入部分要求如下:php ./example.php [单词]
3)输出部分如下:[单词] 1,2 2,4 5,6 表示:此单词在1行2列(第二个单词),2行4列…
说明:
1)此文本 4MB之巨…
2)单词的含义:由英文字母(大小写),数字(0-9)组成的串
3)提供给你的机器OS为ubuntu 9.10,内存只有1G,而且,很不幸的,其中700M用来做了别的
4)上机考试不允许上网,但我装了man文档以及读取CHM以及PDF的 阅读器,在电脑的桌面的CHM文件夹中,有相应的PHP参考手册
5)算法复杂度要求不能大于O(N^2)(就是N的平方)
6)什 么?PHP低效且用起来不顺手,好的,你可以用别的语言来实现。但注意:提供给你的机器上只有python 2.4/perl 5.8/gcc[g++]
题目链接:http://www.xhttp.cn/2010/05/2
――――――――――――――――――――――――――――――――――――――――――――――
分析问题:
典型的字典算法,或是分词算法,好在是英文圣经程序可以少些几行代码
1、建立字典,也就是要找的词,比如 fuck,baby,come,on -_- 估计BBE里少有这样的很黄很暴力的词汇
2、因为对内存有要求,其实这个时候可以分章节查找,就是载入内存允许的章节
3、算法时间度o(n)吧,可以一次查找多个词汇
贴我的代码:
以下是代码片段: < ?php /** * @author shjuto@gmail.com * Trie字典树 * */ class Trie { private $trie; function __construct() { $trie = array(’children’ => array(),’isword’=>false); } /** * 把词加入词典 * * @param String $key */ function &setWord($word=’’) { $trienode = &$this->trie; for($i = 0;$i < strlen($word);$i++) { $character = $word[$i]; if(!isset($trienode[’children’][$character])) { $trienode[’children’][$character] = array(’isword’=>false); } if($i == strlen($word)-1) { $trienode[’children’][$character] = array(’isword’=>true); } $trienode = &$trienode[’children’][$character]; } } /** * 判断是否为词典词 * * @param String $word * @return bool true/false */ function & isWord($word) { $trienode = &$this->trie; for($i = 0;$i < strlen($word);$i++) { $character = $word[$i]; if(!isset($trienode[’children’][$character])) { return false; } else { //判断词结束 if($i == (strlen($word)-1) && $trienode[’children’][$character][’isword’] == true) { return true; } elseif($i == (strlen($word)-1) && $trienode[’children’][$character][’isword’] == false) { return false; } $trienode = &$trienode[’children’][$character]; } } } /** * 在文本$text找词出现的位置 * * @param String $text * @return array array(’position’=>$position,’word’ =>$word); */ function search($text="") { $textlen = strlen($text); $trienode = $tree = $this->trie; $find = array(); $wordrootposition = 0;//词根位置 $prenode = false;//回溯参数,当词典ab,在字符串aab中,需要把$i向前回溯一次 $word = ’’; for ($i = 0; $i < $textlen;$i++) { if(isset($trienode[’children’][$text[$i]])) { $word = $word .$text[$i]; $trienode = $trienode[’children’][$text[$i]]; if($prenode == false) { $wordrootposition = $i; } $prenode = true; if($trienode[’isword’]) { $find[] = array(’position’=>$wordrootposition,’word’ =>$word); } } else { $trienode = $tree; $word = ’’; if($prenode) { $i = $i -1; $prenode = false; } } } return $find; } } $trie = new Trie(); $trie->setWord(’fuck’); $trie->setWord(’you’); $trie->setWord(’come’); $trie->setWord(’on’); var_dump($trie->isWord(’fuck’)); var_dump($trie->isWord(’a’)); var_dump($trie->isWord(’db’)); var_dump($trie->isWord(’comeon’)); var_dump($trie->isWord(’you’)); print_r($trie->search(’hello,tencent,i tell you sonme about bbe, fuck you come on baby,come on,baby,baby,come on,tellgyou fuckdkkdkflsjflsjf’)); |
写的比较乱,代码应该还有很大的优化余地,不过足以说明Trie树的基本思想了,我如果有时间的话,会写一个中文分词的例子.
欢迎拍砖
建议继续学习:
- 一个简单的中文分词程序 (阅读:4553)
- 漫话中文分词算法 (阅读:4005)
- 漫话中文自动分词和语义识别(下):句法结构和语义结构 (阅读:3461)
- Levenshtein distance相似度算法 (阅读:3189)
- 基于trie数据字典的php中文分词 (阅读:3048)
- 排头兵PHP中文分词,纯PHP版实现 (阅读:2708)
- Mysql+sphinx+中文分词简介(ubuntu) (阅读:2352)
- Mysql+sphinx+中文分词简介(ubuntu) (阅读:1969)
- 利用新词统计特征进行中文分词 (阅读:1678)
- 用MeCab打造一套实用的中文分词系统 (阅读:1304)
扫一扫订阅我的微信号:IT技术博客大学习
- 作者:排头兵 来源: 排头兵 @ Talk
- 标签: 分词 字典
- 发布时间:2010-07-21 23:51:09
- [70] Twitter/微博客的学习摘要
- [66] 如何拿下简短的域名
- [65] IOS安全–浅谈关于IOS加固的几种方法
- [64] find命令的一点注意事项
- [63] android 开发入门
- [63] Go Reflect 性能
- [61] 流程管理与用户研究
- [59] 图书馆的世界纪录
- [59] 读书笔记-壹百度:百度十年千倍的29条法则
- [59] Oracle MTS模式下 进程地址与会话信