百度面試題目總結

8月28號下午電面百度，分享一下所有的題目吧，一共面2輪，offer還不知道，自我感覺面的很一般。

一面
1. linux進程通信的方法
2. 線程同步（我扯到了 signal 和 criticalsection 的區別那些）
3. 二叉樹，找到最大距離的兩個節點的距離
4. 瘋子上飛機： http://www.linuxidc.com/Linux/2012-10/72409.htm
5. 如何給網頁歸類（我回答的是基於關鍵詞庫，然後kmp檢索，後來又扯一會kmp）

第二題編碼：
int longest_road(node_t *root){
    if(root == NULL)return 0;
    int left_depth = longest_road(root->lc);
    int right_depth = longest_road(root->rc);
    longest = max(longest, left_depth + right_depth);
   
    return max(left_depth + right_depth) + 1;
}

二面
1. 自我介紹
2. 自己說自己做的比較好的項目
3. 介紹一個你最熟悉的排序算法,我說堆排序，然後如何構建，如何排序，舉例說明何時不是穩定的
4. 堆，棧，全局數據的區別（包括生命周期，分配規則等）
5. 證明n 可以表示成  n = 3^k +/- 3^x .. n可以表示成 3 的冪的組合。
    例如 4 = 3^1 + 3^0    5 = 3^2 - 3^1 - 3^0.  就是說系數只能是1或者-1， 不能是其他的。
    寫給出算法，然後證明這種表示的唯一性。
6. n個數，最少用多少次比較可以找到最大的兩個數 http://www.linuxidc.com/Linux/2012-10/72408.htm
7. 10億 大小的url集合 a和b 如何求 a - b（ 我只是給出哈希算法的大概實現，感覺他不是很滿意）
8. 開放題，如果給網站做內容質量評價，例如評定網站的健康度。

再補充一個同學面過的：

給出一個數組，判定這個數組內的元素，是不是BST後根遍歷的結果。很經典 代碼如下：

1. bool PostOrderTraversal(int data[], int low, int high) 
2. { 
3.      if(low >= high) 
4.      { 
5.           return true; 
6.      } 
7.      int split = -1; 
8.      int i; 
9.      bool found = false; 
10.      //to see if the data can be splited as ABC where c is the last one, all members in A < c, B > c  
11.      for( i = low; i < high; i++) 
12.      { 
13.           if(data[i] > data[high] ) 
14.           { 
15.                if(split == -1) 
16.                { 
17.                    split = i; 
18.                    found = true; 
19.                } 
20.                
21.           } 
22.           if(data[i] < data[high] && split != -1) 
23.           { 
24.               return false; 
25.           } 
26.      } 
27.      if(! found )//only A < c or B > c;   
28.      { 
29.          return PostOrderTraversal(data, low, high-1); 
30.      } 
31.      else //recursive way   
32.      { 
33.          return PostOrderTraversal(data, low, split - 1) && PostOrderTraversal(data, split, high-1); 
34.      } 
35.        
36.        
37.        
38. }