腾讯php程序员面试题目答案――编程任务 -- 算法 -- IT技术博客大学习 -- 共学习共进步！

您现在的位置：首页 --> 算法 --> 腾讯php程序员面试题目答案――编程任务

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

浏览:3231次出处信息

编程任务：
１、我们碰到了大麻烦，一个新来的传教士惹恼了上帝，上帝很愤怒，要求我们把圣经（bbe.txt）背熟，直至他说哪个单词，我们就要飞快的回答出这个单词在第几行第几个单词位置。听说你是个优秀的程序员，那么髟助我们完成这个不可能的任务吧。
要求如下：
１）/myworks /example/bbe.txt，98版本英文圣经一本
２）输入部分要求如下：php ./example.php [单词]
３）输出部分如下：[单词] 1,2 2,4 5,6　表示：此单词在1行2列（第二个单词），2行4列…
说明：
１）此文本 4MB之巨…
２）单词的含义：由英文字母（大小写），数字（0-9）组成的串
３）提供给你的机器OS为ubuntu 9.10，内存只有1G，而且，很不幸的，其中700M用来做了别的
４）上机考试不允许上网，但我装了man文档以及读取CHM以及PDF的阅读器，在电脑的桌面的CHM文件夹中，有相应的PHP参考手册
５）算法复杂度要求不能大于O（N^2）（就是N的平方）
６）什么？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树的基本思想了，我如果有时间的话，会写一个中文分词的例子.
欢迎拍砖

建议继续学习：

QQ技术交流群：445447336，欢迎加入！
扫一扫订阅我的微信号：IT技术博客大学习

<< 前一篇：腾讯php程序员面试题目答案

后一篇：递归字符转义 >>

文章信息

作者：排头兵来源：排头兵 @ Talk
标签：分词字典
发布时间：2010-07-21 23:51:09

建议继续学习

近3天十大热文