pwd: test2
intro: Hello world!
4）包含以下COOKIE信息：
cur_query: you&me
說明：
1）如果，你記不得某個(gè)HTTP協(xié)議中的指令字了，那么，無奈這舉是用“漢字”代替。
2）如果，你能記住更多的HTTP協(xié)議指令字，那么多寫幾句，總是沒壞處，對(duì)吧？
3）最關(guān)鍵的，只需要畫出正確的“輪廓”（還記得httpwatch等工具打印出來的頭部嗎？那就是“輪廓”的含義），也會(huì)有分?jǐn)?shù)，但如果，連“輪廓”都寫錯(cuò)了，那么就很遺憾了。
請(qǐng)寫出HTTP頭，并符合以下要求：
POST /test HTTP/1.1
HOST:www.example.com
User-Agent: ...
Cookie:cur_query=you%26me
username=test&pwd=test2&intro=Hello world!
這個(gè)不知道對(duì)不對(duì)
設(shè)計(jì)任務(wù)：
1、最近總有人騷擾我們的投票模塊，需要你來設(shè)計(jì)一個(gè)投票限制的東東
要求如下：
1）要求每個(gè)QQ號(hào)碼（假設(shè)此QQ號(hào)碼在UNIT32內(nèi)可以表示）10分鐘這內(nèi)只能投5票。
2）我們的用戶很踴躍，平均每天要有2000萬人左右通過此程序投票。
說明：
1）無需寫代碼，只需要圖跟文字即可。
2）對(duì)于關(guān)鍵邏輯，請(qǐng)用圖加代碼表示出來，這也是對(duì)你文字表達(dá)能力的一個(gè)考驗(yàn)。
3）對(duì)你能想到的所有的邊界條件列出來，這是對(duì)你邏輯思維全面與敏捷性的考驗(yàn)。
4）存儲(chǔ)部分，盡你所能吧。如果，你需要一個(gè)自己設(shè)計(jì)的存儲(chǔ)層，那么把這個(gè)存儲(chǔ)層的實(shí)現(xiàn)，用文字＋圖片方式描述清楚，要是設(shè)計(jì)合理，你會(huì)獲得華麗的獎(jiǎng)分。
答案一
核心問題：如何統(tǒng)計(jì)10分鐘之內(nèi)投了5票？
首先：以分鐘為鍵切分?jǐn)?shù)據(jù)集，
然后：每個(gè)數(shù)據(jù)集內(nèi)，以qq號(hào)碼為鍵，vote次數(shù)為值
OK，已經(jīng)成功轉(zhuǎn)換為key-value方式存儲(chǔ)，2000萬的日投票，除以86400秒，并發(fā)231.48rps，使用memcache能夠輕松勝任。
數(shù)據(jù)集ID:201006072134
【QQ號(hào)碼:Vote次數(shù)】
201006072134 | 201006072135 | 201006072136
【12345:3】 | 【12345:3】 | 【12345:3】
【88888:2】 | 【88888:3】 | 【88888:3】
數(shù)據(jù)模型：
$data[ 201006072134時(shí)間分鐘 ][ qq號(hào)碼 ] = vote次數(shù);
A.統(tǒng)計(jì)10分鐘內(nèi)投了多少票
$votes = 0;
for($i = 0; $i < 10; $i++ ){
$votes += $data[ $minute-$i ][ $qq ];
}
B.桶內(nèi)投票數(shù)+1
$data[ $minute ][ $qq ]++;
C.過期統(tǒng)計(jì)數(shù)據(jù)，垃圾清理
unset($data[ $minute ]);
答案二
核心問題：如何統(tǒng)計(jì)10分鐘之內(nèi)投了5票？
首先：以秒為鍵切分?jǐn)?shù)據(jù)集，10*60=600個(gè)時(shí)間戳桶，并添加一個(gè)Forbid令牌桶
然后：每個(gè)數(shù)據(jù)集內(nèi)，以qq號(hào)碼為鍵，vote次數(shù)為值
OK，已經(jīng)成功轉(zhuǎn)換為key-value方式存儲(chǔ)，2000萬的日投票，除以86400秒，并發(fā)231.48rps，使用memcache能夠輕松勝任。
數(shù)據(jù)集ID:201006072134
【QQ號(hào)碼:Vote次數(shù)】
201006072134 | 201006072135 | 201006072136
【12345:3】 | 【12345:3】 | 【12345:3】
【88888:2】 | 【88888:3】 | 【88888:3】
把下一秒鐘不能投票的同學(xué) 生成一個(gè)令牌桶Forbid。
—————-
Forbid令牌桶
【12345】
【55555】
【66666】
【77777】
【99999】
—————-
if(in_array($uid,$not_vote))
{
$flag = ‘不能投票’;
}
else
{
$flag = ‘可以投票’;
//insert 新時(shí)間戳桶
}
定時(shí)任務(wù)
1、unset(10分鐘前的時(shí)間戳桶)
2、重新生成令牌桶
編程任務(wù)：
1、我們碰到了大麻煩，一個(gè)新來的傳教士惹惱了上帝，上帝很憤怒，要求我們把圣經(jīng)（bbe.txt）背熟，直至他說哪個(gè)單詞，我們就要飛快的回答出
這個(gè)單詞在第幾行第幾個(gè)單詞位置。聽說你是個(gè)優(yōu)秀的程序員，那么髟助我們完成這個(gè)不可能的任務(wù)吧。
要求如下：
1）/myworks/example/bbe.txt，98版本英文圣經(jīng)一本
2）輸入部分要求如下：php ./example.php [單詞]
3）輸出部分如下：[單詞] 1,2 2,4 5,6表示：此單詞在1行2列（第二個(gè)單詞），2行4列...
說明：
1）此文本4MB之巨...
2）單詞的含義：由英文字母（大小寫），數(shù)字（0-9）組成的串
3）提供給你的機(jī)器OS為ubuntu 9.10，內(nèi)存只有1G，而且，很不幸的，其中700M用來做了別的
4）上機(jī)考試不允許上網(wǎng)，但我裝了man文檔以及讀取CHM以及PDF的閱讀器，在電腦的桌面的CHM文件夾中，有相應(yīng)的PHP參考手冊(cè)
5）算法復(fù)雜度要求不能大于O（N^2）（就是N的平方）
6）什么？PHP低效且用起來不順手，好的，你可以用別的語言來實(shí)現(xiàn)。但注意：提供給你的機(jī)器上只有python 2.4/perl 5.8/gcc[g++] 4.1
分析問題：
典型的字典算法，或是分詞算法，好在是英文圣經(jīng)程序可以少些幾行代碼
1、建立字典，也就是要找的詞，比如 fuck,baby,come,on -_- 估計(jì)BBE里少有這樣的很黃很暴力的詞匯
2、因?yàn)閷?duì)內(nèi)存有要求，其實(shí)這個(gè)時(shí)候可以分章節(jié)查找，就是載入內(nèi)存允許的章節(jié)
3、算法時(shí)間度o(n)吧，可以一次查找多個(gè)詞匯
貼我的代碼：
以下是代碼片段：
< ?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
{
//判斷詞結(jié)束
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找詞出現(xiàn)的位置
*
* @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;//回溯參數(shù),當(dāng)詞典ab,在字符串a(chǎn)ab中，需要把$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’));
寫的比較亂，代碼應(yīng)該還有很大的優(yōu)化余地，不過足以說明Trie樹的基本思想了，我如果有時(shí)間的話，會(huì)寫一個(gè)中文分詞的例子.
歡迎拍磚
400 186 1886
