2010百度校園招聘試題 R D-C-2
第一題 簡答 （30分）
1， 定義棧的數(shù)據(jù)結(jié)構(gòu)，要求添加一個(gè)min函數(shù)，能夠得到棧的最小元素，要求min、push以及pop的時(shí)間復(fù)雜度都是0(1)，請簡要描述你的思路。 （10分）
2， 閱讀代碼，說明輸出的含義并挑錯(cuò) （10分）
問題1. 寫出下列代碼的運(yùn)行結(jié)果的前7行并說明數(shù)列的含義。
問題2. 代碼中是否有不安全的隱患？原因是？
#include <stdio.h>
#include <string.h>
const int MAX_LEN = 128;
const int MAX_LINE = 20;
int main(int argc, char* argv[])
{
char str[MAX_LEN] = "1";
char tmp_str[MAX_LEN] = "";
char buf[MAX_LEN] = "";
printf("%s\n",str);
for (int line = 1;line <= MAX_LINE;++line)
{
strcpy(tmp_str,str);
str[0] = '\0';
for (int i=0;tmp_str[i] != 0;++i)
{
char ch = tmp_str[i];
int count = 1;
for (;tmp_str[i+1] == tmp_str[i];++i)
{
++count;
}
sprintf(buf,"%d%c",count,ch);
strcat(str,buf);
}
printf("%s\n",str);
}
return 0;
}
3， 分別才要線性表、二叉平衡樹和哈希表存儲(chǔ)數(shù)據(jù)，請分析它們各有什么優(yōu)劣？（10分）
第二題 算法與程序設(shè)計(jì)（40分）
1， 有一串首尾相連的珠子，總共m顆，每顆珠子都有自己的顏色，全部顏色總共有n（n<=10）種。現(xiàn)在要在里面截取一段，要求包含所有不同的顏色，并且長度越短越好。求如何截取。
請?jiān)敿?xì)描述你的算法思路（如需要，可給出偽代碼來輔助描述），并分析其時(shí)間復(fù)雜度和空間復(fù)雜度。（20分）
2， 設(shè)計(jì)一個(gè)strnumcmp函數(shù)，對(duì)比普通的strcmp函數(shù)，差別在于，當(dāng)字符串中遇到數(shù)字時(shí)，以數(shù)字大小為準(zhǔn)。對(duì)于只有其中一個(gè)字符串為數(shù)字的情況，仍然沿用原來的strcmp方式。 （20分）
舉例說
strnumcmp的判定結(jié)果：”abc”<”abc#”<”abc1”<”abc2”<”abc10”<”abcd”
一般的strcmp的判定結(jié)果：”abc”<”abc#”<”abc1”<”abc10”<”abc2”<”abcd”
要求：請給出完整代碼，在達(dá)到目標(biāo)的情況下盡量高效，簡潔。
第三題 系統(tǒng)設(shè)計(jì)題（30分）
在大規(guī)模數(shù)據(jù)處理中經(jīng)常會(huì)用到大規(guī)模字典。現(xiàn)需要處理一個(gè)詞搭配的字典。條件為：
1） 字典中存在的項(xiàng)是兩個(gè)詞的搭配，例如：字典中有“今天”和“晚上”是兩個(gè)詞，那么它們組成的搭配為“今天|晚上”和“晚上|今天”
2） 詞的集合很大，約為10萬量級(jí)
3） 一個(gè)詞并不會(huì)和其他所有詞搭配，通常只會(huì)和不超過1萬個(gè)其他此搭配
4） 對(duì)字典的使用讀操作很大，通常每秒有上千次請求，幾乎沒有寫入需求。
請?jiān)O(shè)計(jì)一個(gè)字典服務(wù)系統(tǒng)，當(dāng)請求是兩個(gè)詞的搭配時(shí)，能夠快速返回搭配的相關(guān)信息。請使用盡可能少的資源，并估算出需要使用的機(jī)器資源。