baidu——郁悶的筆試

  百度采用的是網上筆試和電話面試的形式，說實話，我很不适應。再加上投職位時報了營運部，導緻履歷都沒有通過，等到重新投履歷時，已經錯過了最好的機會。不過感覺百度對你重複投履歷也是來者不拒，隻要你有恒心，有實力，去百度還是很有希望的。

下面是我收集的筆試題目：

發信人: sea1 (tian), 信區: Career_Plaza 标 題: 30秒。。。百度測試工程師被拒（附：筆試題） 發信站: 水木社群 (Wed May 17 19:49:32 2006), 站内   說實話，本來就抱什麼希望，隻是想知道自己的實力怎樣。結果。。哎！不過還是要贊一下 百度的相關人員，她們的态度都挺和藹的！！（也挺PP的）   還是具體的說一下吧：   早就從網上了解到百度公司（位于海澱圖書城銀科大廈）很搞笑。上到18層後，先是見到 PP服務台小姐，之後就是左邊的“百度人民很行”，說真的，從遠處看，根本就是“百度人 民銀行”。第一見是就是登記（由PPMM負責，後來知道有兩個PPMM負責前台，我登記時，那 個不在，否則我會“多線程”的）。之後是負責測試的人員MM來給了我筆試題。看完之後我 差點暈了，幾乎不會！！！試題如下： 1、以下符号在LINUX下代表什麼檔案：p , l, c, d, s, -, MS很基本，不過我對LINUX一點 也不感冒！！（結果我瞎寫的，如果有計算機的同學想拍我，一定在站内信箱拍！！） 　　 b 塊裝置檔案   　　 c 字元裝置檔案   　　 d 目錄檔案   　　 p 命名管道（ FIFO ）   　　 f 普通檔案   　　 l 符号連結檔案（ symbolic links ）   　　 s socket 檔案 2、編寫一個SHELL腳本，儲存目錄中的檔案，并存為.bak檔案。（結果還是不會）   3、怎樣在LINUX下測試網絡狀态。不會！ Netstat 4、在LINUX下怎樣查詢CPU，記憶體，硬碟的狀态。不會！ Top Fdisk -l 5、HTTP：？網絡狀态下的常見碼狀态是什麼？ 不會！   6、寫結果： void fun(char *temp,int n) {     char *s1,*s2;     int t;     int i =0;     s1=temp;     s2=s1+n-1;     while(i++<7)     {        t=*s1++;        *s1=*s2--;        *s2=t;     } } void main() {     char p[8]="1234567";     fun(p,strlen(p));     puts(p); }   題目還有問題，結果估計是 1111111   還有一些我答上來了！你猜是什麼題？ 7、為何申請百度？百度成功在與什麼？   8、怎樣才能成為優秀的測試工程師？   9、這類題都可以自己想，我就不多說了！！   最後，說一下，為何30秒就挂了！！！^_^....   她一進門，拿者我的履歷，之後對我說，你畢業比較晚，是吧？ 我說“是”，今年才考上研，得08年才能畢業。 之後，她又說，你打算實習幾個月，我說“二個月吧”。這時，她笑了笑，對我說：“着業 太短了，我們要求盡可能長時間的實習，且，主要面向即将畢業的同學，你看。。。” 這下每戲了，後來我們簡短的談了一下，之後就走了。（她比較和藹，臨走的時候，給我很 好的印象）。   值得一體的是，我筆試在“采雲歸”房間，就我一個人，筆試過程中，哪個為我登記的 PPMM給我那杯水，之後，見屋子裡的兩個椅子多餘，就将它們擡了出去（比較費力），我當 時，被筆試弄暈了，早知道，我就幫她一起擡了^_^!!!如果有高手看到的話，請支一下招， 告訴小弟以後遇到這種事情該怎麼辦？？順便問一下，以後，我和這個MM還有戲嗎？？？   回來後受打擊了，正巧房東養了4個小王八，于是我開始玩王八解悶。。。   1.實作 void delete_char(char * str, char ch);  把str中所有的ch删掉   void delete_char(char * str, char ch) {     char *newstr = (char *)malloc(strlen(str)+1);     char *str_p = str;     char *newstr_p = newstr; // 如果沒有這兩個的話， while 後面的指針就出錯了     while(*str_p)     {        if(*str_p == ch)            str_p++;        else            *newstr_p++ = *str_p++;     }     *newstr_p = '/0';     strcpy(str, newstr);     free(newstr); } 2.把字元串S中所有A子串換成B,這個沒給函數原型   3.搜尋引擎的日志要記錄所有查詢串,有一千萬條查詢,不重複的不超過三百萬  要統計最熱門的10條查詢串. 記憶體<1G. 字元串長 0-255  (1) 主要解決思路 //具體用詞和原題不大一樣  (2) 算法及其複雜度分析   4.有字典,設計一個英文拼寫糾正算法 (1) 思想 (2) 算法及複雜度 (3) 改進   5. { aaa, bb, ccc, dd }, { bbb, ff }, { gg } 等一些字元串的集合  要求把交集不為空的集合并起來,如上例會得到 { aaa, bb, ccc, dd, ff }, {gg} (1)    思想 (2) 算法及複雜度 (3) 改進   下午去百度筆試,考題有二叉搜尋樹和堆   1。程式設計：

用C語言實作一個revert函數，它的功能是将輸入的字元串在原串上倒序後傳回。   void revert(char * str) {     int length = strlen(str);     char temp;     for(int i = 0; i < length/2; i++)     {        temp = *(str + i);        *(str + i) = *(str + length - 1 - i);        *(str + length - 1 - i) = temp;     } }

2 。程式設計：

                  用C語言實作函數void * memmove(void *dest,const void *src,size_t  n)。memmove                   函數的功能是拷貝src所指的記憶體内容前n個位元組 到dest所指的位址上。 void * memmove(void * dest,const void *src,size_t count) {     char *tmp, *s;       if (dest <= src) {//dest 在前面，故 dest 頭不可能覆寫 src 尾        tmp = (char *) dest;        s = (char *) src;        while (count--)            *tmp++ = *s++;     }     else {//dest 在後面， dest 頭可能覆寫 src 尾，造成 src 沒有結束符         tmp = (char *) dest + count;        s = (char *) src + count;        while (count--)            *--tmp = *--s;     }       return dest; }

3 英文拼寫糾錯：

                  在使用者輸入英文單詞時，經常發生錯誤，我們需要對其進行糾錯。假設已經有一個包含了正确英文單詞的詞典，請你設計一個拼寫糾錯的程式。

                  （1）請描述你解決這個問題的思路；

                  （2）請給出主要的處理流程，算法，以及算法的複雜度；

                  （3）請描述可能的改進（改進的方向如效果，性能等等，這是一個開放問題）。                   (1) 思路 :

                   字典以字母鍵樹組織，在使用者輸入同時比對

                  (2)

                   流程 :

                   每輸入一個字母：

                   沿字典樹向下一層，

                  a ）若可以順利下行，則繼續至結束，給出結果；

                  b) 若該處不能比對，糾錯處理，給出拼寫建議 , 繼續至 a ）；                    算法 :

                  1. 在字典中查找單詞

                   字典采用 27 叉樹組織 , 每個節點對應一個字母 , 查找就是一個字母

                   一個字母比對 . 算法時間就是單詞的長度 k.                   2. 糾錯算法

                   情況 : 當輸入的最後一個字母不能比對時就提示出錯 , 簡化出錯處理，動态提示

                   可能 處理方法 :

                  (a) 目前字母前缺少了一個字母：搜尋樹上兩層到目前的比對作為建議；

                  (b) 目前字母拼寫錯誤：目前字母的鍵盤相鄰作為提示；（隻是簡單的描述，可                    以有更多的）

                   根據分析字典特征和使用者單詞已輸入部分選擇 (a),(b) 處理

                   複雜性分析：影響算法的效率主要是字典的實作與糾錯處理

                   （ a ）字典的實作已有成熟的算法，改進不大，也不會成為瓶頸；

                  (b) 糾錯政策要簡單有效 , 如前述情況，是線性複雜度；                   (3) 改進

                   政策選擇最是重要，可以采用統計學習的方法改進。

 4 尋找熱門查詢：

                  搜尋引擎會通過日志檔案把使用者每次檢索使用的所有檢索串都記錄下來，每個查詢串                   的長度為1-255位元組。假設目前有一千萬個記錄，

                  這些查詢串的重複度比較高，雖然總數是1千萬，但如果除去重複後，不超過3百萬個                   。一個查詢串的重複度越高，說明查詢它的使用者越多，

                  也就是越熱門。請你統計最熱門的10個查詢串，要求使用的記憶體不能超過1G。

                  （1）請描述你解決這個問題的思路；

                  （2）請給出主要的處理流程，算法，以及算法的複雜度。 1G就是十億          (1) 思路：

                   用哈希做

                  (2)

                   首先逐次讀入查詢串，算哈希值，儲存在記憶體數組中，同時統計頻度

                   （注意值與日志項對應關系）

                   選出前十的頻度，取出對應的日志串，簡單不過了。                    哈希的設計是關鍵。

5 集合合并：

                  給定一個字元串的集合，格式如：

                  {aaa bbb ccc}， {bbb ddd}，{eee fff}，{ggg}，{ddd hhh}

                  要求将其中交集不為空的集合合并，要求合并完成後的集合之間無交集，例如上例應                   輸出

                  {aaa bbb ccc ddd hhh}，{eee fff}， {ggg}

                  （1）請描述你解決這個問題的思路；

                  （2）請給出主要的處理流程，算法，以及算法的複雜度

                  （3）請描述可能的改進（改進的方向如效果，性能等等，這是一個開放問題）。

        要求将其中交集不為空的集合合并   要求合并完成後的集合無交集 這兩個要求隻要 1 滿足了， 2 就自然滿足了。   方法 1 ：把每個集合用 vector<vector<char> > 表示，比較兩個集合裡面 vector<char> 是否相等 ( 是否交集不為空，有相同元素 ) ，如果有相同集合就合并。這個就是每個集合都和其後面的集合比較，複雜度為 o(n2) 。   方法 2 ：把每個集合都周遊一遍，找出所有集合的所有元素 ( 不重複 ). 然後建立一張表，記錄各個元素在每個集合的出現情況，行代表元素，列代表集合，出現則相應位為 1 ，否則為 0 。表建立完成後，把每行有多個 1 的  1 所在列的集合合并就可以了。   時間複雜度： 周遊 O(n), 寫表 O(n), 最後查表合并 o(n) ，總的複雜度為 O(n) 。             Map的用法     map<string ,int> a;     string b("asdf");     a.insert(map< string,int >::        value_type(b,3));     string c("sdf");     a.insert(map< string,int >::        value_type(c,4));     map<string, int>::iterator i;     for(i = a.begin(); i != a.end(); i++)        cout << (*i).first << " " << (*i).second << endl;     a.erase(b);     for(i = a.begin(); i != a.end(); i++)        cout << (*i).first << " " << (*i).second << endl;   我的方法： 先周遊集合，建立一個 hash 表， hash 表的鍵為集合中的字元串，值表示為包含此字元串的集合的序号，比如說集合 1 和 3 包含此元素，值就是 00001010 ，複雜度為 o （ n ） 然後周遊這個 hash 表，将這些值進行 & 運算，結果為 0 時就跳過，結果不為 0 時儲存此結果，然後從 hash 表中删除這個條目，周遊完一遍後得到第一個合并後的集合的序号，就進行合并。此為 o(m) 然後再次周遊直到 hash 表為空為止。複雜度合并後集合數乘上 hash 表長度 其實也可以通過一次周遊 hash 表來确定，建立一個連結清單， a[0] 為儲存 & 不為 0 的值， a[1] 儲存 & 為 0 的值，然後将 a[] 中的數字都與 hash 表的值做 & 運算，都為 0 時将這個值加傳入連結表，不為 0 時，将結果儲存到 a[i] ，有可能還要合并，不過這樣複雜度也不好算  “已知一個字串由GBK漢字和ansi編碼的數字字母混合組成，編寫C語言函數實作從中去掉所有ansi編碼的的數字和字母（包括大小寫).要求在原字串上傳回結果。int filter_ansi(char* gbk_string);注：漢字的GBK編碼範圍是0x8140 - 0xFEFE。”   char * filter_ansi(char* gbk_string) {     assert(gbk_string!=NULL);     char *src;     char *dst;     src = dst = gbk_string;     while(*src)     {        if(*src & 0x80)        {            *dst++ = *src++;            *dst++ = *src++;        }        else            src++;     }     *dst = '/0';     return gbk_string; }