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 编辑过
400 186 1886
