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）    對字典的使用讀操作很大，通常每秒有上千次請求，幾乎沒有寫入需求。
請設計一個字典服務系統，當請求是兩個詞的搭配時，能夠快速返回搭配的相關信息。請使用盡可能少的資源，并估算出需要使用的機器資源。