技术头条 - 一个快速在微博传播文章的方式     搜索本站
您现在的位置首页 --> 算法 --> 腾讯php程序员面试题目答案――编程任务

腾讯php程序员面试题目答案――编程任务

浏览:3225次  出处信息

编程任务:
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树的基本思想了,我如果有时间的话,会写一个中文分词的例子.
欢迎拍砖

建议继续学习:

  1. 一个简单的中文分词程序    (阅读:4523)
  2. 漫话中文分词算法    (阅读:3980)
  3. 漫话中文自动分词和语义识别(下):句法结构和语义结构    (阅读:3438)
  4. Levenshtein distance相似度算法    (阅读:3103)
  5. 基于trie数据字典的php中文分词    (阅读:3027)
  6. 排头兵PHP中文分词,纯PHP版实现    (阅读:2687)
  7. Mysql+sphinx+中文分词简介(ubuntu)    (阅读:2333)
  8. Mysql+sphinx+中文分词简介(ubuntu)    (阅读:1949)
  9. 利用新词统计特征进行中文分词    (阅读:1614)
  10. 用MeCab打造一套实用的中文分词系统    (阅读:1228)
QQ技术交流群:445447336,欢迎加入!
扫一扫订阅我的微信号:IT技术博客大学习
© 2009 - 2024 by blogread.cn 微博:@IT技术博客大学习

京ICP备15002552号-1