2010百度校園招聘試題 R D-C-2
第一題 簡答 （30分）
1， 定義棧的數據結構，要求添加一個min函數，能夠得到棧的最小元素，要求min、push以及pop的時間復雜度都是0(1)，請簡要描述你的思路。 （10分）
2， 閱讀代碼，說明輸出的含義并挑錯 （10分）
問題1. 寫出下列代碼的運行結果的前7行并說明數列的含義。
問題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， 分別才要線性表、二叉平衡樹和哈希表存儲數據，請分析它們各有什么優劣？（10分）
第二題 算法與程序設計（40分）
1， 有一串首尾相連的珠子，總共m顆，每顆珠子都有自己的顏色，全部顏色總共有n（n<=10）種。現在要在里面截取一段，要求包含所有不同的顏色，并且長度越短越好。求如何截取。
請詳細描述你的算法思路（如需要，可給出偽代碼來輔助描述），并分析其時間復雜度和空間復雜度。（20分）
2， 設計一個strnumcmp函數，對比普通的strcmp函數，差別在于，當字符串中遇到數字時，以數字大小為準。對于只有其中一個字符串為數字的情況，仍然沿用原來的strcmp方式。 （20分）
舉例說
strnumcmp的判定結果：”abc”<”abc#”<”abc1”<”abc2”<”abc10”<”abcd”
一般的strcmp的判定結果：”abc”<”abc#”<”abc1”<”abc10”<”abc2”<”abcd”
要求：請給出完整代碼，在達到目標的情況下盡量高效，簡潔。
第三題 系統設計題（30分）
在大規模數據處理中經常會用到大規模字典。現需要處理一個詞搭配的字典。條件為：
1） 字典中存在的項是兩個詞的搭配，例如：字典中有“今天”和“晚上”是兩個詞，那么它們組成的搭配為“今天|晚上”和“晚上|今天”
2） 詞的集合很大，約為10萬量級
3） 一個詞并不會和其他所有詞搭配，通常只會和不超過1萬個其他此搭配
4） 對字典的使用讀操作很大，通常每秒有上千次請求，幾乎沒有寫入需求。
請設計一個字典服務系統，當請求是兩個詞的搭配時，能夠快速返回搭配的相關信息。請使用盡可能少的資源，并估算出需要使用的機器資源。