LOGO OA教程 ERP教程 模切知识交流 PMS教程 CRM教程 开发文档 其他文档  
 
网站管理员

腾讯PHP面试题

admin
2012年4月3日 23:4 本文热度 2562

pwd: test2


intro: Hello world!


4)包含以下COOKIE信息:


cur_query: you&me


说明:


1)如果,你记不得某个HTTP协议中的指令字了,那么,无奈这举是用“汉字”代替。


2)如果,你能记住更多的HTTP协议指令字,那么多写几句,总是没坏处,对吧?


3)最关键的,只需要画出正确的“轮廓”(还记得httpwatch等工具打印出来的头部吗?那就是“轮廓”的含义),也会有分数,但如果,连“轮廓”都写错了,那么就很遗憾了。



请写出HTTP头,并符合以下要求:
POST /test HTTP/1.1
HOST:www.example.com
User-Agent: ...
Cookie:cur_query=you%26me

username=test&pwd=test2&intro=Hello world!


这个不知道对不对


设计任务:


1、最近总有人骚扰我们的投票模块,需要你来设计一个投票限制的东东


要求如下:


1)要求每个QQ号码(假设此QQ号码在UNIT32内可以表示)10分钟这内只能投5票。


2)我们的用户很踊跃,平均每天要有2000万人左右通过此程序投票。


说明:


1)无需写代码,只需要图跟文字即可。


2)对于关键逻辑,请用图加代码表示出来,这也是对你文字表达能力的一个考验。


3)对你能想到的所有的边界条件列出来,这是对你逻辑思维全面与敏捷性的考验。


4)存储部分,尽你所能吧。如果,你需要一个自己设计的存储层,那么把这个存储层的实现,用文字+图片方式描述清楚,要是设计合理,你会获得华丽的奖分。


答案一


核心问题:如何统计10分钟之内投了5票?


首先:以分钟为键切分数据集,
然后:每个数据集内,以qq号码为键,vote次数为值
OK,已经成功转换为key-value方式存储,2000万的日投票,除以86400秒,并发231.48rps,使用memcache能够轻松胜任。


数据集ID:201006072134
【QQ号码:Vote次数】

201006072134 | 201006072135 | 201006072136
【12345:3】 | 【12345:3】 | 【12345:3】
【88888:2】 | 【88888:3】 | 【88888:3】

数据模型:
$data[ 201006072134时间分钟 ][ qq号码 ] = vote次数;


A.统计10分钟内投了多少票
$votes = 0;
for($i = 0; $i < 10; $i++ ){
$votes += $data[ $minute-$i ][ $qq ];
}


B.桶内投票数+1
$data[ $minute ][ $qq ]++;


C.过期统计数据,垃圾清理
unset($data[ $minute ]);


答案二


核心问题:如何统计10分钟之内投了5票?


首先:以秒为键切分数据集,10*60=600个时间戳桶,并添加一个Forbid令牌桶
然后:每个数据集内,以qq号码为键,vote次数为值
OK,已经成功转换为key-value方式存储,2000万的日投票,除以86400秒,并发231.48rps,使用memcache能够轻松胜任。


数据集ID:201006072134
【QQ号码:Vote次数】


201006072134 | 201006072135 | 201006072136
【12345:3】 | 【12345:3】 | 【12345:3】
【88888:2】 | 【88888:3】 | 【88888:3】


把下一秒钟不能投票的同学 生成一个令牌桶Forbid。
—————-
Forbid令牌桶
【12345】
【55555】
【66666】
【77777】
【99999】
—————-
if(in_array($uid,$not_vote))
{
$flag = ‘不能投票’;
}
else
{
$flag = ‘可以投票’;
//insert 新时间戳桶
}


定时任务
1、unset(10分钟前的时间戳桶)
2、重新生成令牌桶


编程任务:


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++] 4.1


分析问题:
典型的字典算法,或是分词算法,好在是英文圣经程序可以少些几行代码
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树的基本思想了,我如果有时间的话,会写一个中文分词的例子.
欢迎拍砖


该文章在 2012/4/3 23:04:02 编辑过
关键字查询
相关文章
正在查询...
点晴ERP是一款针对中小制造业的专业生产管理软件系统,系统成熟度和易用性得到了国内大量中小企业的青睐。
点晴PMS码头管理系统主要针对港口码头集装箱与散货日常运作、调度、堆场、车队、财务费用、相关报表等业务管理,结合码头的业务特点,围绕调度、堆场作业而开发的。集技术的先进性、管理的有效性于一体,是物流码头及其他港口类企业的高效ERP管理信息系统。
点晴WMS仓储管理系统提供了货物产品管理,销售管理,采购管理,仓储管理,仓库管理,保质期管理,货位管理,库位管理,生产管理,WMS管理系统,标签打印,条形码,二维码管理,批号管理软件。
点晴免费OA是一款软件和通用服务都免费,不限功能、不限时间、不限用户的免费OA协同办公管理系统。
Copyright 2010-2024 ClickSun All Rights Reserved