百度2014校园招聘笔试面试汇总
目 錄
1. 百度筆試 2
1.1百度2014校園招聘筆試題（成都站，軟件研發崗） 2
1.2 ?2013百度校園招聘-機器學習和數據挖掘工程師-筆試題 7
1.3 ?百度2014校園招聘 技術研發題目 8
1.4 ?百度2013校招北京站筆試題 9
1.5 ?2013百度校招杭州站筆試題-軟開與開發測試 11
1.6 ?百度開發類歷年筆試題目集合及解答 12
2. 百度面試 62
2.1 ?2013年9月26日，百度技術類一二面 62
2.2 ?百度軟件開發工程師一面問題 62
2.3 ?百度Android兩輪面試經驗 63
1. 百度筆試
1.1百度2014校園招聘筆試題（成都站，軟件研發崗）
日期：2013.09.21
地點：成都
崗位：軟件研發
一、簡答題（本題共30分）
1. 當前計算機系統一般會采用層次結構來存儲數據，請介紹下典型的計算機存儲系統一般分為哪幾個層次，為什么采用分層存儲數據能有效提高程序的執行效率？（10分）
?
2. Unix/Linux系統中僵尸進程是如何產生的？有什么危害？如何避免？（10分）
?
3. 簡述Unix/Linux系統中使用socket庫編寫服務器端程序的流程，請分別用對應的socket通信函數表示（10分）
?
二、算法與程序設計題（本題共45分）
?
1. 使用C/C++編寫函數，實現字符串反轉，要求不使用任何系統函數，且時間復雜度最小，函數原型：char* reverse_str(char* str)。(15分)
?
2. 給定一個如下格式的字符串，(1,(2,3),(4,(5,6),7))括號內的元素可以是數字，也可以是另一個括號，請實現一個算法消除嵌套的括號，比如把上面的表達式變成：(1,2,3,4,5,6,7)，如果表達式有誤請報錯。(15分)
?
3. （見下圖）
?
?
三、系統設計題（本題共25分）
在企業中，對生產數據進行分析具有很重要的意義，但是生產數據通常不能直接用于數據分析，通常需要進行抽取、轉換和加載，也就是通常說的ETL。
?
為了便于開發和維護，并提高數據實時性，通常將一個完整的ETL過程分為多個任務，組成流水線，如下圖所示：
?
?
?
假設任務定義和任務之間的依賴關系都保存在文件中，文件格式分別如下：
?
?
問題：
1. 下面是ETL調度系統的模塊圖，請描述各個模塊呃主要職責，以及各個線條的 含義。（10分）
?
2. ?添加依賴關系時要避免出現環，假設系統同一個時刻只允許一個人添加任務依賴，請實現一個函數來檢查新的依賴是否導致環，依賴的上游存在環會導致非正常的調度，因此也希望能避免。（10分）
a) ?函數名：checkCycle
b) ?輸入：pairs，已存在的依賴關系((pre,post)……), newPair新的依賴關系(pre,post)
c) ?輸出：True: 不存在環，False: 存在環
?
3. 如果調度時，某個任務在其依賴的任務之前執行，必然導致錯誤，請實現調度算法，確保任務按照依賴順序執行？（10分）
a) ?函數名：schedule
b) ?輸入1：tasks，整數數組；
c) ?輸入2：task-relation，二元組數組，每個二元組表示一組關系；
d) ?輸出：task id序列，并行執行的用","分隔，其他的用";"分隔；
?
4. 給定一個任務，如何計算出他的最晚完成時間？（10分）
a) ?函數名：calMaxEndTime
b) ?輸入1：tasks，3元組數組，（task_id, start_time, max_run_time）；
?
c) ?輸入2：task-relations，二元組數組，每個二元組表示一組關系；
d) ?輸入3：task-id
e) ?輸出：最晚完成時間；
1.2 ?2013百度校園招聘-機器學習和數據挖掘工程師-筆試題
一、簡答題（30分）
1、簡述數據庫操作的步驟（10分）
2、TCP/IP的四層結構（10分）
3、什么是MVC結構，簡要介紹各層結構的作用（10分）
二、算法與程序設計（45分）
1、由a-z、0-9組成3位的字符密碼，設計一個算法，列出并打印所有可能的密碼組合（可用偽代碼、C、C++、Java實現）（15分）
2、實現字符串反轉函數（15分）
3、百度鳳巢系統，廣告客戶購買一系列關鍵詞，數據結構如下：（15分）
User1 手機 智能手機 iphone 臺式機 …
User2 手機 iphone 筆記本電腦 三星手機 …
User3 htc 平板電腦 手機 …
（1）根據以上數據結構對關鍵詞進行KMeans聚類，請列出關鍵詞?
的向量表示、距離公式和KMeans算法的整體步驟
（2）計算給定關鍵詞與客戶關鍵詞的文字相關性，請列出關鍵詞與客戶的表達符號和計算公式
三、系統設計題（25分）
一維數據的擬合，給定數據集{xi,yi}(i=1,…,n)，xi是訓練數據，yi是對應的預期值。擬使用線性、二次、高次等函數進行擬合
線性：f(x)=ax+b
二次：f(x)=ax^2+bx+c
三次：f(x)=ax^3+bx^2+cx+d
（1）請依次列出線性、二次、三次擬合的誤差函數表達式（2分）
（2）按照梯度下降法進行擬合，請給出具體的推導過程。（7分）
（3）下圖給出了線性、二次和七次擬合的效果圖。請說明進行數據擬合時，需要考慮哪些問題。在本例中，你選擇哪種擬合函數。（8分）
（4）給出實驗方案（8分）
1.3 ?百度2014校園招聘 技術研發題目
樓主非985,非211,二本專業一枚，有幸獲得度娘的照顧，有個筆試機會，當然抱著重在參與的心態，把所有題目copy回來了。說來慚愧，做的不好，給需要的同學參考參考吧。
一、簡答題
?
1.靜態鏈接庫和動態鏈接庫的優缺點。
2.輪詢式任務調度和搶占式任務調度的區別
3.數據庫中有哪些鎖，敘述其應用場合。
二、算法與程序設計
1.給定任意一正整數，求大于它的最小非“重復數”。所謂“重復數”是指一個數中相鄰的位相同的狀況，例如“1123”是重復數，“1231”則不是。
2.有一個長度為N(N很大)的字符串，求其最大回文字符串。（好像是回文。。）
3.在數軸上有a[0],a[1],a[2],.....,a[n-1]個點，有一根長度為L 的尺子，最多能覆蓋多少個點？
三、系統設計（題目太長，大意如下）
設計一個分布式緩存系統，滿足一下三個條件：
1.單個緩存服務器故障無法工作，服務器集群可正常工作。
2.充分利用每一個服務器容量，按照比例，均衡負載。
3.如果某一服務器故障，保證遷移的緩存文件數據量最小。
1.4 ?百度2013校招北京站筆試題
一、簡答題（30分）?
1、用簡單語句描述數據庫操作的步驟?
2、寫出TCP/IP的四層結構?
?
3、什么是MVC結構，并描述各層結構的作用?
二、算法與程序設計題（40分）?
1、字母a-z，數字0-9，現需要其中任意3個作為密碼，請輸出所有可能組合。（偽碼\C\C++\JAVA）（10分）?
2、實現字符串反轉函數（10分）?
3、給定字符函數a、插入 b、刪除 c、替換?
例如字符串A=acegf，字符串B=adef，最少需要2步操作將A轉換為B，
即第一步將c替換為d，第二步將g刪除；?
（1）請問將字符串A=gumbo轉換為字符串B=gambol，最少需要幾步操作，列出如何操作（2分）?
（2）任意字符串A和字符串B，如何計算最小操作次數，計算思路，并給出遞歸公式（3分）?
（3）實現代碼（注意代碼風格與效率）(15分)?
點評：請參看上文第38題第4小題：9月26日，百度一二面試題。
三、系統設計題（30分）
RSA SecurID安全系統?
應用場景：這是一種用戶登錄驗證手段，例如銀行登錄系統，這個設備顯示6位數字，每60秒變一次，再經過服務器認證，通過則允許登錄。問How to design this system？?
?
1）系統設計思路？服務器端為何能有效認證動態密碼的正確性？?
2）如果是千萬量級永固，給出系統設計圖示或說明，要求子功能模塊劃分清晰，給出關鍵的數據結構或數據庫表結構。?
考慮用戶量級的影響和擴展性，用戶密碼的隨機性等，如果設計系統以支持這幾個因素.?
3）系統算法升級時，服務器端和設備端可能都要有所修改，如何設計系統，能夠使得升級過程（包括可能的設備替換或重設）盡量平滑？
1.5 ?2013百度校招杭州站筆試題-軟開與開發測試
10月20日 上午9:00-11:00 ?浙大 百度軟件開發和開發測試的筆試題（軟件開發和開發測試的筆試題監考官說是一樣的）
每個地方的考題都不一樣，突擊了一下也沒碰見原題這種好事，練練手吧。
一、簡答題
1. 哈希算法有哪些種，舉例說明。
2. OSI 七層結構分別是什么 ，http協議在哪一層。
3. 一個C程序是如何運行的。
二、程序設計題
1. 一個農夫拉了一車蘋果，現在把這些蘋果裝成小袋，每三個一袋最后剩下兩個，每5個一袋剩下了3個，每7個一袋剩下了（忘了幾?
個）個，問：請列出N種蘋果的總數量。
2. 用遞歸算法計算一個字符串中最大的連續字符個數。比如aaabbcc 輸出3，aabbcc 輸出2，abc輸出1
3. 一個輸入法，從鍵盤上敲擊字幕輸入，會顯示所有待選詞，第一個待選詞是用戶行為學習詞匯（高頻詞），第二個是云計算所得詞匯，每行顯示5個待選詞，可翻頁，請設計測試用例。
三、系統設計題
百度所存儲的網頁上有1kw個安卓.apk安裝軟件，其中只有10w個是有效的。請設計算法（不需要具體代碼實現）抓取這10w個apk。注意要有排除相同的url，排除相同的apk,排除惡性apk。
1.6 ?百度開發類歷年筆試題目集合及解答
①現在有1千萬個隨機數，隨機數的范圍在1到1億之間?，F在要求寫出一種算法，將1到1億之間沒有在隨機數中的數求出來。?
解決辦法：
一）用一個32位的整數32位表示32個數，1億/32 = 3125000，使用3.125 * 4M byte空間即可保存1億個數，即index[3125000].
二）對于數n，(n-1) / 32 為其在數組中的下標，table[(n - 1) % 32]與數組中下標(n-1)/32的值使用或操作。
三）表table中值為 table[ 0 ]=0x00000001,
?
table[ 1 ]=0x00000002,
... ...
table[29]=0x20000000,
table[31]=0x80000000, 等這樣的表示方式，具體的數值使用查表法加快速度。
四）最后算某值是否存在，使用與操作即可計算出。
數據存取比如：
第一個N=30是一個隨機數，則存儲可以表示為：index[(30-1)/32] = index[0] = index[0] || table[(30-1)%32]?
注: /*剛開始時候初始化index[32]={0}*/
= 0 || 0x20000000 = 0x20000000；
第二個N=31是一個隨機數，則存儲可以表示為：index[(31-1)/32] = index[0] = index[0] || table[(31-1)%32]?
注:/*第30位1，其他位為0*/
= 0x20000000 || 0x40000000 = 0x60000000；
... ...
依次類推，即可。?
?
數據驗證比如：
1. 當要查詢30是否存在的時候，由于：(30-1)/32 = 0；(30-1)%32=29；我們只需要計算：index[0] & table[29] 是真還是假，就可以得出30是否存在。
2. 當要查詢31是否存在的時候，由于：(31-1)/32 = 0；(31-1)%32=30；我們只需要計算：index[0] & table[30] 是真還是假，就可以得出31是否存在。
... ...
依次類推，即可。?
小結：
通過分析此題目，首先這種思路和方法，在一定程度上用相對小的空間存儲了大量的數據，節省了比較大的內
存空間；在運算方面，位運算的速度相當來說效率是比較高的，因而也再一定程度上節省了時間復雜。
總之，這種存儲方式和思維方式，在一定方面能夠有效的解決海量數據存儲與運算。基于此題目，凡是大量數據篩選，判斷是否存在等問題，我們都可以借鑒此題目的思維和方法。
?
② 如下，其中每個單元格的長寬均為1。任意給定長x，寬為y的如下形狀，設計算法找出總共有多少個長方形(不計正方形個數)？(百度面試)
? ?
? ?
? ?
[cpp] view plaincopy
1. //算法實現
2. #include <stdio.h>
3.
4. int FindTotalNumOfRectangle(const unsigned int x, const unsigned int y)
5. {
6. unsigned int i, j, sum = 0;
7.
8. for(i = 1; i <= x; ++ i)
9. {
10. for(j = 1; j <= y; ++ j)
11. {
12. if(i != j)
13. {
14. sum += (x - i + 1) * (y - j + 1);
15. }
16. }
17. }
18. return sum;
19. }
20.
21. int main()
22. {
23. printf("%d\n",FindTotalNumOfRectangle(2, 3));
24.
25. return 0;
26. }
[cpp] view plaincopy
1. //算法實現 ?
2. #include <stdio.h> ?
3. ?
4. int FindTotalNumOfRectangle(const unsigned int x, const unsigned int y) ?
5. { ?
6. ? ?unsigned int i, j, sum = 0; ?
7. ? ? ?
8. ? ?for(i = 1; i <= x; ++ i) ?
9. ? ?{ ?
10. ? ? ? ?for(j = 1; j <= y; ++ j) ?
11. ? ? ? ?{ ?
12. ? ? ? ? ? ?if(i != j) ?
13. ? ? ? ? ? ?{ ?
14. ? ? ? ? ? ? ? ?sum += (x - i + 1) * (y - j + 1); ?
15. ? ? ? ? ? ?} ?
16. ? ? ? ?} ?
17. ? ?} ?
18. ? ?return sum; ?
19. } ?
20. ?
21. int main() ?
22. { ?
23. ? ?printf("%d\n",FindTotalNumOfRectangle(2, 3)); ?
24. ?
25. ? ?return 0; ?
26. } ?
③ 十進制轉換為N進制(百度面試)
[cpp] view plaincopy
1. char *simple_itoa(unsigned int i)
2. {
3. /* 21 digits plus null terminator, good for 64-bit or smaller ints
4. * for bigger ints, use a bigger buffer!
5. *
6. * 4294967295 is, incidentally, MAX_UINT (on 32bit systems at this time)
7. * and is 10 bytes long
8. */
9. static char local[22];
10. char *p = &local[21];
11. *p = '\0';
12. do {
13. *--p = '0' + i % 10;
14. i /= 10;
15. } while (i != 0);
16. return p;
17. }
[cpp] view plaincopy
1. char *simple_itoa(unsigned int i) ?
2. { ?
3. ? ?/* 21 digits plus null terminator, good for 64-bit or smaller ints?
4. ? ? * for bigger ints, use a bigger buffer!?
5. ? ? *?
6. ? ? * 4294967295 is, incidentally, MAX_UINT (on 32bit systems at this time)?
7. ? ? * and is 10 bytes long?
8. ? ? */ ?
9. ? ?static char local[22]; ?
10. ? ?char *p = &local[21]; ?
11. ? ?*p = '\0'; ?
12. ? ?do { ?
13. ? ? ? ?*--p = '0' + i % 10; ?
14. ? ? ? ?i /= 10; ?
15. ? ?} while (i != 0); ?
16. ? ?return p; ?
17. } ?
[cpp] view plaincopy
1. #include <stdio.h>
2. #include <string.h>
3.
4. void ReverseString(char *pString)
5. {
6. if(NULL == pString)
7. return ;
8.
9. char *pBegin = pString;
10. char *pEnd = pString + strlen(pString) - 1;
11.
12. while(pBegin < pEnd)
13. {
14. char temp = *pBegin;
15. *pBegin = *pEnd;
16. *pEnd = temp;
17.
18. ++ pBegin;
19. -- pEnd;
20. }
21. }
22.
23. char * FromTenToN (const int num, const unsigned int N)
24. {
25. if(NULL == num || N < 2 || N > 16)
26. return NULL;
27.
28. char *result = new char[];
29.
30. int tmpNum = num;
31. unsigned int nCount = 0;
32.
33. while(tmpNum)
34. {
35. int tmp = tmpNum % N ;
36.
37. if(tmp >= 10)
38. tmp = 'A' + (tmp - 10) - '0';
39.
40. result[ nCount ++] = tmp + '0';
41.
42. tmpNum /= N;
43. }
44. result[ nCount ] = '\0';
45.
46. ReverseString(result);
47.
48. return result;
49. }
50.
51. int main()
52. {
53. printf("the Result is :%s\n",FromTenToN(166, 16));
54.
55. }
[cpp] view plaincopy
1. #include <stdio.h> ?
2. #include <string.h> ?
3. ?
4. void ReverseString(char *pString) ?
5. { ?
6. ? ?if(NULL == pString) ?
7. ? ? ? ?return ; ?
8. ?
9. ? ?char *pBegin = pString; ?
10. ? ?char *pEnd ? = pString + strlen(pString) - 1; ?
11. ?
12. ? ?while(pBegin < pEnd) ?
13. ? ?{ ?
14. ? ? ? ?char temp = *pBegin; ?
15. ? ? ? ?*pBegin = *pEnd; ?
16. ? ? ? ?*pEnd ? = temp; ?
17. ?
18. ? ? ? ?++ pBegin; ?
19. ? ? ? ?-- pEnd; ?
20. ? ?} ?
21. } ?
22. ?
23. char * FromTenToN (const int num, const unsigned int N) ?
24. { ?
25. ? ?if(NULL == num || N < 2 || N > 16) ?
26. ? ? ? ?return NULL; ?
27. ?
28. ? ?char *result = new char[]; ?
29. ?
30. ? ?int tmpNum = num; ?
31. ? ?unsigned int nCount = 0; ?
32. ?
33. ? ?while(tmpNum) ?
34. ? ?{ ?
35. ? ? ? ?int tmp = tmpNum % N ; ?
36. ?
37. ? ? ? ?if(tmp >= 10) ? ? ?
38. ? ? ? ? ? ?tmp = 'A' + (tmp - 10) - '0'; ?
39. ?
40. ? ? ? ?result[ nCount ++] = tmp + '0'; ? ? ??
41. ?
42. ? ? ? ?tmpNum /= N; ?
43. ? ?} ?
44. ? ?result[ nCount ] = '\0'; ?
45. ?
46. ? ?ReverseString(result); ?
47. ?
48. ? ?return result; ?
49. } ?
50. ?
51. int main() ?
52. { ?
53. ? ?printf("the Result is :%s\n",FromTenToN(166, 16)); ?
54. ?
55. } ?
④ 快速排序算法(百度面試)
[cpp] view plaincopy
1. #include <stdio.h>
2.
3. int Partition(int *iArray, int i, int j)
4. {
5. int pivot = iArray[ i ];
6.
7. while(i < j)
8. {
9. while(i < j && iArray[ j ] >= pivot )
10. {
11. j --;
12. }
13.
14. if(i < j)
15. {
16. iArray[ i ++ ] = iArray[ j ];
17. }
18.
19. while(i < j && iArray[ i ] <= pivot)
20. {
21. i ++;
22. }
23.
24. if(i < j)
25. {
26. iArray[ j -- ] = iArray[ i ];
27. }
28. }
29.
30. iArray[ i ] = pivot;
31.
32. return i;
33. }
34.
35. void QuickSort(int *iArray, int low, int high)
36. {
37. if(low < high)
38. {
39. int pivotpos = Partition(iArray, low, high);
40.
41. QuickSort(iArray, low, pivotpos - 1);
42.
43. QuickSort(iArray, pivotpos + 1, high);
44. }
45.
46. }
47. int main()
48. {
49. int iArray[] = {1,0,9,3,7,2,-90,78,45,4,77,79,78,37,0,-1,2,3,6,9,5,4,78,78,78,1,1,1};
50.
51. int len = sizeof(iArray) / sizeof(int);
52.
53. QuickSort(iArray, 0, len - 1);
54.
55. for(int i = 0; i < len; ++ i)
56. {
57. printf("%3d ",iArray[ i ]);
58. }
59.
60. printf("\n");
61. }
[cpp] view plaincopy
1. #include <stdio.h> ?
2. ?
3. int ?Partition(int *iArray, int i, int j) ?
4. { ?
5. ? ?int pivot = iArray[ i ]; ?
6. ?
7. ? ?while(i < j) ?
8. ? ?{ ?
9. ? ? ? ?while(i < j && iArray[ j ] >= pivot ) ?
10. ? ? ? ?{ ?
11. ? ? ? ? ? ?j --; ?
12. ? ? ? ?} ?
13. ?
14. ? ? ? ?if(i < j) ?
15. ? ? ? ?{ ?
16. ? ? ? ? ? ?iArray[ i ++ ] = iArray[ j ]; ?
17. ? ? ? ?} ?
18. ?
19. ? ? ? ?while(i < j && iArray[ i ] <= pivot) ?
20. ? ? ? ?{ ?
21. ? ? ? ? ? ?i ++; ?
22. ? ? ? ?} ?
23. ?
24. ? ? ? ?if(i < j) ?
25. ? ? ? ?{ ?
26. ? ? ? ? ? ?iArray[ j -- ] = iArray[ i ]; ?
27. ? ? ? ?} ?
28. ? ?} ?
29. ?
30. ? ?iArray[ i ] = pivot; ?
31. ?
32. ? ?return i; ?
33. } ?
34. ?
35. void QuickSort(int *iArray, int low, int high) ?
36. { ?
37. ? ?if(low < high) ?
38. ? ?{ ?
39. ? ? ? ?int pivotpos = Partition(iArray, low, high); ?
40. ?
41. ? ? ? ?QuickSort(iArray, low, pivotpos - 1); ?
42. ?
43. ? ? ? ?QuickSort(iArray, pivotpos + 1, high); ?
44. ? ?} ?
45. ?
46. } ?
47. int main() ?
48. { ?
49. ? ?int iArray[] = {1,0,9,3,7,2,-90,78,45,4,77,79,78,37,0,-1,2,3,6,9,5,4,78,78,78,1,1,1}; ?
50. ?
51. ? ?int len = sizeof(iArray) / sizeof(int); ?
52. ?
53. ? ?QuickSort(iArray, 0, len - 1); ?
54. ?
55. ? ?for(int i = 0; i < len; ++ i) ?
56. ? ?{ ?
57. ? ? ? ?printf("%3d ",iArray[ i ]); ?
58. ? ?} ?
59. ?
60. ? ?printf("\n"); ?
61. } ?
⑥查找兄弟字符串(百度筆試)
[cpp] view plaincopy
1. //judge two string is brother string or not
2. bool IsBrotherString(const char *src,const char *dst)
3. {
4. if( strlen(src) != strlen(dst) )
5. return false;
6.
7. //usually we only have 256 chars
8. unsigned int hashTable[256];
9. memset(hashTable,0,sizeof(hashTable));
10.
11. //compute the num of every char in the src
12. const char *pSrc = src;
13. while(*pSrc != '\0')
14. {
15. ++ hashTable[*pSrc ++];
16. }
17.
18. //minus the num of every char in the dst
19. const char *pDest = dst;
20. while(*pDest != '\0')
21. {
22. -- hashTable[*pDest ++];
23. }
24.
25. //at last,if all the num in hashTable is zero, it is brother string.
26. pSrc = src;
27. while(*pSrc != '\0')
28. {
29. if(hashTable[*pSrc ++] != 0)
30. {
31. return false;
32. }
33. }
34. return true;
35. }
[cpp] view plaincopy
1. //judge two string is brother string or not ?
2. bool IsBrotherString(const char *src,const char *dst) ?
3. { ?
4. ? ?if( strlen(src) != strlen(dst) ) ?
5. ? ? ? ?return false; ?
6. ? ? ?
7. ? ?//usually we only have 256 chars ?
8. ? ?unsigned int hashTable[256]; ?
9. ? ?memset(hashTable,0,sizeof(hashTable)); ?
10. ?
11. ? ?//compute the num of every char in the src ?
12. ? ?const char *pSrc = src; ?
13. ? ?while(*pSrc != '\0') ?
14. ? ?{ ?
15. ? ? ? ?++ hashTable[*pSrc ++]; ?
16. ? ?} ?
17. ?
18. ? ?//minus the num of every char in the dst ?
19. ? ?const char *pDest = dst; ?
20. ? ?while(*pDest != '\0') ?
21. ? ?{ ?
22. ? ? ? ?-- hashTable[*pDest ++]; ?
23. ? ?} ?
24. ?
25. ? ?//at last,if all the num in hashTable is zero, it is brother string. ?
26. ? ?pSrc = src; ?
27. ? ?while(*pSrc != '\0') ?
28. ? ?{ ?
29. ? ? ? ?if(hashTable[*pSrc ++] != 0) ?
30. ? ? ? ?{ ?
31. ? ? ? ? ? ?return false; ?
32. ? ? ? ?} ?
33. ? ?} ? ??
34. ? ?return true; ?
35. } ?
⑦×××數組的整合。例如已知數組a前半部分a[0,mid - 1],后半部分a[mid,num-1]，現前半部分和后半部分均已排好序。要求：實現a數組的從小到大排序?？臻g復雜度為O(1).(百度筆試)
[cpp] view plaincopy
1. #include <stdio.h>
2.
3. void MergeIntData(int *a, const unsigned int num, const unsigned int mid)
4. {
5. if(mid < 0 || num < 0 || NULL == a || a[mid - 1] <= a[ mid ])
6. return;
7.
8. unsigned int i,temp, low = 0, high = 0;
9.
10. if(mid <= num / 2)
11. {
12. while(low < mid)
13. {
14. while(a[low] < a[mid + high])//不能加等號,否則如果有連續相等在一起的數據，會出現
15.
16. 錯誤
17. {
18. ++ low;
19. }
20.
21. while(a[mid + high + 1] < a[low])
22. {
23. ++ high;
24.
25. if(high >= num - mid)
26. {
27. high = num - mid - 1;
28. break;
29. }
30. }
31.
32. temp = a[low];
33. for(i = low; i < mid + high; ++ i)
34. {
35. a[i] = a[i + 1];
36. }
37. a[mid + high] = temp;
38. }
39. }
40. else
41. {
42. while(high < num - mid)
43. {
44. while(a[low] < a[mid + high])
45. {
46. ++ low;
47. }
48.
49. temp = a[mid + high];
50. for(i = mid + high; i > low; -- i)
51. {
52. a[i] = a[i - 1];
53. }
54. a[low] = temp;
55.
56. ++ high;
57. }
58. }
59. }
60.
61.
62. int main()
63. {
64.
65. // int a[] = {0,2,4,6,8,9,10,11,12,14,16,18,1,3,5,7};
66. // int a[] = {0,2,4,6,8,8,9,9,1000,1,3,5,7,10,11,12,14,16,18,20,21,23,25,45,68};
67. // int a[] = {100,1,3,5,7,10,11,12,14,16,18,20,21,23,25,45,68};
68. // int a[] = {8,8,8,9,9,1,5,8,9,10,12,13,14};
69. // int a[] = {1,2,3,4,5,6,7,8,9,2,4,5,7,8,9,10};
70. // int a[] = {0,1,2,3,4,5,6,7,8,9,9,17,100,5,5,5,5,9,10,10000};
71.
72. int a[] = {1,2,3,4,5,6,7,100,1000,2,3,5,6,8,1001};
73. int len = sizeof(a) / sizeof(int);
74. int mid = 9;
75. MergeIntData(a, len, mid);
76.
77. for(int i = 0; i < len; ++ i)
78. {
79. printf("%d ", a[i]);
80. }
81.
82. printf("\n");
83. return 0;
84. }
[cpp] view plaincopy
1. #include <stdio.h> ?
2. ?
3. void MergeIntData(int *a, const unsigned int num, const unsigned int mid) ?
4. { ?
5. ? ?if(mid < 0 || num < 0 || NULL == a || a[mid - 1] <= a[ mid ]) ?
6. ? ? ? ?return; ?
7. ?
8. ? ?unsigned int i,temp, low = 0, high = 0; ?
9. ? ? ?
10. ? ?if(mid <= num / 2) ?
11. ? ?{ ?
12. ? ? ? ?while(low < mid) ?
13. ? ? ? ?{ ? ??
14. ? ? ? ? ? ?while(a[low] < a[mid + high])//不能加等號,否則如果有連續相等在一起的數據，會出現 ?
15. ?
16. 錯誤 ?
17. ? ? ? ? ? ?{ ?
18. ? ? ? ? ? ? ? ?++ low; ? ? ? ? ? ? ??
19. ? ? ? ? ? ?} ? ? ? ? ? ??
20. ?
21. ? ? ? ? ? ?while(a[mid + high + 1] < a[low]) ?
22. ? ? ? ? ? ?{ ?
23. ? ? ? ? ? ? ? ?++ high; ?
24. ?
25. ? ? ? ? ? ? ? ?if(high ?>= num - mid) ?
26. ? ? ? ? ? ? ? ?{ ?
27. ? ? ? ? ? ? ? ? ? ?high = num - mid - 1; ?
28. ? ? ? ? ? ? ? ? ? ?break; ?
29. ? ? ? ? ? ? ? ?} ?
30. ? ? ? ? ? ?} ?
31. ?
32. ? ? ? ? ? ?temp = a[low]; ? ? ? ? ? ?
33. ? ? ? ? ? ?for(i = low; i < mid + high; ++ i) ?
34. ? ? ? ? ? ?{ ?
35. ? ? ? ? ? ? ? ?a[i] = ?a[i + 1]; ?
36. ? ? ? ? ? ?} ?
37. ? ? ? ? ? ?a[mid + high] = temp; ?
38. ? ? ? ?} ? ??
39. ? ?} ?
40. ? ?else ?
41. ? ?{ ?
42. ? ? ? ?while(high < num - mid) ?
43. ? ? ? ?{ ? ??
44. ? ? ? ? ? ?while(a[low] < a[mid + high]) ?
45. ? ? ? ? ? ?{ ?
46. ? ? ? ? ? ? ? ?++ low; ? ? ? ? ? ? ??
47. ? ? ? ? ? ?} ? ? ? ? ? ??
48. ?
49. ? ? ? ? ? ?temp = a[mid + high]; ? ? ? ? ? ??
50. ? ? ? ? ? ?for(i = mid + high; i > low; -- i) ?
51. ? ? ? ? ? ?{ ?
52. ? ? ? ? ? ? ? ?a[i] = ?a[i - 1]; ?
53. ? ? ? ? ? ?} ?
54. ? ? ? ? ? ?a[low] = temp; ?
55. ?
56. ? ? ? ? ? ?++ high; ?
57. ? ? ? ?} ? ??
58. ? ?} ?
59. } ?
60. ?
61. ?
62. int main() ?
63. { ?
64. ?
65. // ?int a[] = {0,2,4,6,8,9,10,11,12,14,16,18,1,3,5,7}; ?
66. // ?int a[] = {0,2,4,6,8,8,9,9,1000,1,3,5,7,10,11,12,14,16,18,20,21,23,25,45,68}; ?
67. // ?int a[] = {100,1,3,5,7,10,11,12,14,16,18,20,21,23,25,45,68}; ?
68. // ?int a[] = {8,8,8,9,9,1,5,8,9,10,12,13,14}; ?
69. // ?int a[] = {1,2,3,4,5,6,7,8,9,2,4,5,7,8,9,10}; ?
70. // ?int a[] = {0,1,2,3,4,5,6,7,8,9,9,17,100,5,5,5,5,9,10,10000}; ?
71. ?
72. ? ?int a[] = {1,2,3,4,5,6,7,100,1000,2,3,5,6,8,1001}; ?
73. ? ?int len = sizeof(a) / sizeof(int); ?
74. ? ?int mid = ?9; ?
75. ? ?MergeIntData(a, len, mid); ?
76. ?
77. ? ?for(int i = 0; i < len; ++ i) ?
78. ? ?{ ?
79. ? ? ? ?printf("%d ?", a[i]); ?
80. ? ?} ?
81. ?
82. ? ?printf("\n"); ?
83. ? ?return 0; ?
84. } ?
2012年校園招聘筆試題目
一 簡單題
1. 對遠程Linux/Unix系統進行操作，通常的途徑是采用終端軟件通過SSH登錄遠程系統，進行操作。但是在網絡發生中
斷時，Linux/Unix端運行的程序將會中斷。
請簡述這種問題發生的原來，通過何種途徑避免這種問題，以及該途徑可以避免此問題的原理。?
2.一個最小值堆，同時是一棵完全二叉樹（只有最下面兩次節點的子節點數可以少于2且最下面一層的節點都存儲在最
左面），如圖所示
1
/ \
2 6
/ \ / \
4 3 8 7
/ \
5 9
該堆順序存儲在一個數組a中，1 2 6 4 3 8 7 5 9
1）對于任意節點a[n]，其在二叉樹中左，右子節點訪問方式
2）完成函數，向堆中加入一個元素后仍然滿足堆的原有性質
void add_element(int *a,int size,int val) //a存儲堆是數組，size是數組內的已有元
素個數，val是元素的值，數組內大小不需要考慮
3）完成函數，取出堆頂最小元素后仍然滿足堆的原有性質?
3 通過某種hash算法，可以讓用戶穩定的均勻分布到一個區間內，這個區間的大小為100%，分布的最小粒度為：0.1%，我們把這種區間叫做一層。現在有兩個區間A,B，如何讓層A中的任意子區間都均勻分布到層B的100%中？例如：層A中取10%，這10%會均勻分布到層B中，即：層B的每一個10%區間都會有1%的區間A中的10%，也可以說層B的。如果現在有超過10層，每一層之間都需要有這種關系，又如何解決？?
二 算法與程序設計
1。不知所云
2 。1)給定一個序列s=[a1,a2,a3,...,an]；構造一個函數，生成序列s的全排列；
示例：
>>>permu([1,2,3])
[[ 1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1] ]?
2)構造一個算法，生成序列s的所有組合；
示例：
>>>comb([1,2,3])
[ [ ],[1],[2],[3],[1,2],[1,3],[2,3],[1,2,3] ]
說明：算法均可用偽代碼表示?
三 系統設計題 -全排列算法原理和實現
全排列是將一組數按一定順序進行排列，如果這組數有n個，那么全排列數為n!個?，F以{1, 2, 3, 4, 5}為例說明如何編寫全排列的遞歸算法。
1、首先看最后兩個數4, 5。 它們的全排列為4 5和5 4, 即以4開頭的5的全排列和以5開頭的4的全排列。由于一個數的全排列就是其本身，從而得到以上結果。
2、再看后三個數3, 4, 5。它們的全排列為3 4 5、3 5 4、 4 3 5、 4 5 3、 5 3 4、 5 4 3 六組數。即以3開頭的和4,5的全排列的組合、以4開頭的和3,5的全排列的組合和以5開頭的和3,4的全排列的組合.從而可以推斷，設一組數p = {r1, r2, r3, ... ,rn}, 全排列為perm(p)，pn = p - {rn}。因此perm(p) = r1perm(p1), r2perm(p2), r3perm(p3), ... , rnperm(pn)。當n = 1時perm(p} = r1。為了更容易理解，將整組數中的所有的數分別與第一個數交換，這樣就總是在處理后n-1個數的全排列。
?
百度筆試題目
LINUX和C相關問題：
1. static關鍵字的作用。為什么static變量只初始化一次？說下進程的地址空間（代碼段，數據段，堆，棧等）
2.進程和線程的區別？為什么線程的調度開銷小？
3.說下select機制
4.為什么需要字節對齊？字節對齊的規則？
算法和數據結構
(運氣比較好，面試官沒有要求寫出程序，只要能說出算法思路就可以)：
1.如何將一個字符串中的某一個字符全部刪除，原字符串順序不變？如輸入abcdefbbg，刪除b后得到acdefg，要求時間復雜度O(N),空間復雜度O(1)
2.如果要求對一個集合進行查詢，插入，刪除，你會怎么設計它的數據結構？平衡二叉樹特點？怎么查詢，如果時間復雜度要求比O(logn)更小，采用什么？hash的沖突解決方法有哪些？如果要求有序的輸出，是選二叉樹還是hash？怎么輸出？
3.如何在一個二叉樹中找兩個節點的最近祖先節點?
4.臺階問題：有n個臺階，每次可以踏一個臺階，或2個，問有多少種走法？
（PS:我寫出動態規劃的表達式后，面試官問這個對嗎？我想了半分鐘，覺得有問題，正準備說應該是….,面試官笑著說
哦，別看了，沒問題，倒….）
百度筆試題2005?
題目大致是這樣的：?
第一部分選擇題：
有幾道網絡相關的題目，巨簡單，比如第一題是TCP、RIP、IP、FTP中哪個協議是傳輸層的......。有一道linux的chown使用題目。其他的全是數據結構的題目！什么鏈，表，碼的，不知所云．唉，我可以沒有學過數據結構的人吶！真殘忍！這一部分迅速猜完！
第二部分簡答題：
1、在linux中如何編譯C程序，使之成為可執行文件？如何調試？
答案： 1)檢查程序中.h文件所在的目錄，將其加入系統PATH中；
2)執行C編譯：#gcc [源文件名] -o [目標文件名]
執行C++編譯：#g++ [源文件名] -o [目標文件名]
3)改變目標文件為可執行文件：#chmod +x [目標文件名]
4)如需將多個可執行文件連續執行，可生成批處理文件：
#vi [批處理文件名]
??
可執行文件1?
可執行文件2
.........
最后將該批處理文件屬性該位可執行。
調試：在編譯時使用-g參數，就可以使用gdb進行調試。
2、寫出內存分配和釋放的函數，并指出區別。
答案：
C語言的標準內存分配函數：malloc，calloc，realloc，free等。
malloc與calloc的區別為1塊與n塊的區別：
malloc調用形式為(類型*)malloc(size)：在內存的動態存儲區中分配一塊長度為“size”字節的連續區域，返
回該區域的首地址。
calloc調用形式為(類型*)calloc(n，size)：在內存的動態存儲區中分配n塊長度為“size”字節的連續區域，
返回首地址。
realloc調用形式為(類型*)realloc(*ptr，size)：將ptr內存大?
小增大到size。
free的調用形式為free(void*ptr)：釋放ptr所指向的一塊內存空間。
C++中為new/delete函數。
3、寫出socket函數，并指出其功能。
socket():建立socket通信描述符；
bind()：將套接字和機器上的一定的端口關聯；
connect()：連接到遠程主機；
listen()：使套接字做好連接的準備，規定等待服務請求隊列的長度；
accept()：接受連接，一旦有客戶端發出連接，accept返回客戶地址信息和一個新的sock；
有了這個新的sock，雙方就可以開始收發數據：
send()和recv()：用于流式套接字或者數據套接字的通訊；
sendto()和recvfrom()：用于無連接的數據報套接字；
close()：關閉套接字；
shutdown()：選擇性的關閉套接字，可以只允許某一方向的通訊關閉；
?
getpeername()：返回流式套接字時對端peer信息；
gethostname()：返回程序所運行的機器的主機名字；
gethostbyname()：返回本機IP；
第三部分編程題：
1、從文件中讀取字符串數據，反序顯示并大小寫轉換。
2、給定26字母表以及對應的密碼表，編程實現加密及解密功能。
第四部分思考題(正是傳說中的字典糾錯題)：
用戶在輸入英文單詞時經常出錯，現對其進行就錯。給定一個正確的英文詞典，考慮糾錯實現。1)指出思路。2)流程、算法難易程度及可能的改進策略。
一道算法題目答案
int Replace(Stringtype &S,Stringtype T,Stringtype V);//將串S中所有子串T替換為V,并返回置換次數?
{?
for(n=0,i=1;i〈=Strlen(S)-Strlen(T)+1;i++) //注意i的取值范圍?
if(!StrCompare(SubString(S,i,Strlen(T)),T)) //找到了與T匹配的子串?
{ //分別把T的前面和后面部分保存為head和tail?
?
StrAssign(head,SubString(S,1,i-1));?
StrAssign(tail,SubString(S,i+Strlen(T),Strlen(S)-i-Strlen(T)+1));?
StrAssign(S,Concat(head,V));?
StrAssign(S,Concat(S,tail)); //把head,V,tail連接為新串?
i+=Strlen(V); //當前指針跳到插入串以后?
n++;?
}//if?
return n;?
}//Replace?
分析:i+=Strlen(V);這一句是必需的,也是容易忽略的.如省掉這一句,則在某些情況下,會引起不希望的后果,雖然在大多數情況下沒有影響.請思考:設S='place', T='ace', V='face',則省掉i+=Strlen(V);運行時會出現什么結果? （無限遞歸face）
百度2005年的筆試題
1.實現 void delete_char(char * str, char ch);
把str中所有的ch刪掉
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) 改進?
2006百度筆試題?
一、選擇題：15分 共10題?
1.一個含有n個頂點和e條邊的簡單無向圖，在其鄰接矩陣存儲結構中共有__D__個零元素。?
A．e B．2e C．n2-e D．n2-2e
2.__D__是面向對象程序設計語言中的一種機制。這種機制實現了方法的定義與具體的對象無關，而對方法的調用則可以
?
關聯于具體的對象。?
A．繼承（Inhertance） B．模板（Template）?
C．對象的自身引用（Self-Reference） D．動態綁定（Dynamic Binding）
3.應用層DNS協議主要用于實現網絡服務功能. C
A. IP地址到網絡設備名字的映射 B. IP地址到網絡硬件地址的映射?
C. 網絡設備名字到IP地址的映射 D. 網絡硬件地址到IP地址的映射
補充：ARP協議工作原理：將IP地址映射為MAC地址
4.linux默認情況下，一個進程最多能打開多少文件？A?
A.64 B. 128 C. 512 D. 1024
5.下面結構體?
struct s1 {?
char ch, *ptr;?
union {?
short a, b;?
unsigned int c:2, d:1;?
}?
?
struct s1 *next;?
};?
的大小是__D___：?
A. 12字節 B.16字節 C.20字節 D. 24字節
6.任何一個基于"比較"的內部排序的算法，若對6個元素進行排序，則在最壞情況下所需的比較次數至少為_D___。?
A．10 B．11 C．21 D．36
7.以下不是進程間通訊的是__C_ 補充：ABD+管道
A 共享內存 B 信號量 C線程局部存儲 D 消息隊列
8.下面程序，求count的值 A
int func(x)?
{?
int count= 0;?
x=9999;?
while(x)?
{?
Count ++;?
x = x&(x-1);?
?
}?
return count;?
}
A 8； B 10； C 5； D 11
補充：
#include<iostream.h>
int func(int x)?
{?
int count= 0;?
x=9999;?
while(x)?
{?
count ++;?
x = x&(x-1);?
}?
return count;?
}?
void main()
{
int y,z;
y=func(z);
cout<<y <<endl;
}
9.使用malloc系統調用分配的內存是在__D__ 上分配的？?
A 棧； B bss； C 物理內存； D 堆
10.最壞情況下，合并兩個大小為n的已排序數組所需要的比較次數__B___?
A.2n B.2n-1 C.2n+1 D.2n-2
二、簡答題：20分，共3題
1.（5分）下面這段代碼是把中英文混合字符串(漢字用兩個字節表示，特點是第一個字節的最高位為1)中的大寫字母轉
化為小寫字母，請找出其中的bug，注意各種異常情況。
for (char *piterator = szWord; *piterator != 0; piterator++)?
{?
if (*piterator & 0x80 != 0)?
{?
piterator++;?
}?
else if (*piterator >= 'A' && *piterator <= 'Z')
piterator += 32; // *piterator += 32
}
2.（5分）對給定的上億條無序的url，請按照domain、site以及path分別排序，并請指出排序過程中可能會遇到的哪些
問題？如何提高效率？?
例如：http://www.baidu.com/path/about.html，domain、site以及path的定義分別如下：
Domain:baidu.com?
Site:www.baidu.com?
Path: www.baidu.com/path
可以用索引壓縮排序法
3.（10分）某型CPU的一級數據緩存大小為16K字節，cache塊大小為64字節；二級緩存大小為256K字節，cache塊大小為
4K字節，
采用二路組相聯。經測試，下面兩段代碼運行時效率差別很大，請分析哪段代碼更好，以及可能的原因。?
為了進一步提高效率，你還可以采取什么辦法？?
A段代碼?
int matrix[1023][15];?
const char *str = "this is a str";?
int i, j, tmp, sum = 0;
tmp = strlen(str);?
for(i = 0; i < 1023; i++) {?
for(j = 0; j < 15; j++) {?
sum += matrix[j] + tmp;?
}?
}
B段代碼?
int matrix[1025][17];?
const char *str = "this is a str";?
int i, j, sum = 0;
for(i = 0; i < 17; i++) {?
for(j = 0; j < 1025; j++) {?
sum += matrix[j] + strlen(str);?
}?
}
Ａ段代碼效率會高出很多！首先Ａ中函數strlen(str)只執行了一次，而Ｂ中執行了１７＊１０２５次．
其次是Ａ段代碼的cache塊交換比Ｂ段代碼少，相應的執行時間也少，效率高............
根據一級緩存和二級緩存的大小和chach塊的大小，把數組定義為matrix[1024][16]，外循環為１０２４次，內循環為１
６次，則效率會更高．
A段代碼效率要遠遠高于B段代碼，原因有三：
1、?
B效率低最要命的地方就是每次都要調用strlen()函數，這是個嚴重問題，屬于邏輯級錯誤。假設A的兩層循環都不改變
，僅僅是把A的那個循環
里面的temp換成strlen()調用，在Windows 2000 (Intel 雙) 下測試，竟然是A的執行時間的3.699倍。（這里沒有涉及
不同CPU有不同的Cache
設計）僅僅是這一點就已經說明B段代碼垃圾代碼。
2、
這也是一個邏輯級的錯誤。在這里我們再做個試驗，A、B段代碼分別采用大小一樣的數組[1023][15]、[1023]
[16]、[1023][17]，只是
在循環上采取了不同的方式。兩者在運行時間上也是有很大差異的了。B的運行時間大概是A的1.130倍。
那么這是因為什么呢？其實也很簡單，那就是A段代碼中的循環執行語句對內存的訪問是連續的，而B段代碼中的
循環執行語句對內存
的訪問是跳躍的。直接降低了B代碼的運行效率。
這里不是內層循環執行多少次的問題，而是一個對內存訪問是否連續的問題。
3、
A的二維數組是[1023][15]，B的二維數組是[1027][17],在這里B段代碼有犯了一個CPU級錯誤（或者是Cache級的錯誤）
。
因為在Cache中數據或指令是以行為單位存儲的(也可以說是Cache塊)，一行又包含了很多字。如現在主流的設計是一行
包含64Byte。每一行擁
有一個Tag。因此，假設CPU需要一個標為Tag 1的行中的數據，它會通過CAM對Cache中的行進行查找，一旦找到相同Tag
的行，就對其中的數據
進行讀取。
A的是15 *4B ＝ 60B，一個Cache行剛好可以存儲。B的是17*4B ＝ 68B，超過了一個Cache行所存儲的數據。
很明顯17的時候命中率要低于15的時候。
現在我們先不管A、B的循環嵌套的順序，僅僅拿A段代碼來做個試驗，我們將會分三種情況來進行：
[1023][15] [1023][16] [1023][17]
運行結果并沒有出乎意料之外 17 的時候的運行時間大概是 15 的時候的1.399倍，除去有因為17的時候多執行循環，
17/15 ＝ 1.133 。
進行折算，17的時候大概是15的時候的1.265倍。
16的時候的執行時間要比15的時候的執行時間要短，因為是16的時候，Cache命中率更高。16/15 ＝ 1.066 ，
而15的執行時間卻是16的1.068倍，加上16多執行的消耗，進行折算，15的時候大概是16的時候執行時間的1.134倍。
因為A段代碼是15，而B段代碼是17，在這一點上B段代碼的效率要低于A段代碼的效率。這是一個CPU級的錯誤（或者是
Cache級的錯誤），
這里涉及到Cache的塊大小，也就涉及到Cache命中率，也就影響到代碼效率。
不再假設什么，僅僅對A段和B段代碼進行測試，B段代碼的執行效率將是A段代碼執行效率的3.95倍。
當然最大的罪魁禍首就是B中的重復調用strlen()函數。后面兩個錯誤告訴我們當需要對大量數據訪問的時候，
一定要注意對內存的訪問要盡量是連續而且循環內層的訪問接近Cache的塊大小，以提高Cache的命中率，從而提高程序
的運行效率。?
所以可以對代碼進行一下修改：
#define XX 15?
#define YY 1023
int matrix[XX][YY];
const char *str = "this is a str";
int i, j, tmp, sum = 0;
tmp = strlen(str);
for(i = 0; i < XX; i++)
for(j = 0; j < YY; j++)
sum += matrix[i][j] + tmp;
這個程序僅僅是把數組的聲明給顛倒了一下，循環也顛倒了一下，看起來和運行起來和上面給出的A段代碼沒有多大的區別。
但是如果當XX很小，比如：8，那么這段程序和給出的A段代碼就有區別了。這是因為這樣做可以提高Cache的命中率。
三、編程題：30分 共1題
注意：要求盡可能提供完整代碼，如果可以編譯運行酌情加分。
1.內存中有一個長數組，條目數為10萬，數組單元為結構體struct array，sizeof(struct array)為512字節。
結構有一int型成員變量weight。現需要取得按weight值從大到小排序的前500個數組單元，請實現算法，要求效率盡可能高。
step1. 在內存中建立一個長度為500的緩沖區int型緩沖區
step2.遍歷此長數組，按weight大小順序填充此緩沖區，填入的值為數組的下表，非weight值 (由數組下表訪問weight是O(1)時間)
step3.遍歷完畢以后，按照由大到小的順序輸出數組單元
時間復雜度：O(n) （遍歷為O(n)，每一次操作，即插入一個有序的數組復雜度為O(logm),m最大為500，所以總的時間復雜度是O(n)）?
空間復雜度：O(1)
四、設計題：35分 共1題
注意：請盡可能詳細描述你的數據結構、系統架構、設計思路等，建議多寫一些偽代碼或者流程說明。
1.請設計一個字典。以字符串為索引，存儲用戶定義的定長結構。要求有增、刪、查、改的功能。
已經給定一個函數，可以由字符串映射到一個簽名，每個簽名由兩個unsigned int類型組成。
假設每一個字符串能夠對應唯一的一個簽名，完全沒有重復（或者重復的概率可以忽略），并且簽名分布足夠均勻。
請描述你的數據結構？內存如何申請？增、刪、查、改的功能如何實現？如果操作很頻繁，該如何優化？
2007年百度校園招聘會筆試題
1選錯的
基類public成員在派生類中仍是public
基類protected成員在派生類中仍是protected
基類private成員在派生類中是隱藏
回去想的，我忘了錯的怎么說的來著
2邊長為n的正方形可以分成多個邊長為1的正方形，如邊長為2的正方形有2×2個邊長為1的正方形和1個邊長為2的正方形；問邊長為5的正方形有幾個正方形；
3
public class Person {
public void printValue(int i,int j){
System.out.println("1111111111111");
}
public void printValue(int i){
System.out.println("22222222222");
}
}
public class Teacher extends Person {
public void printValue(){
System.out.println("333333333");
}
public void printValue(int i){
System.out.println("4444444444");
}
public static void main(String[] args) {
Person t=new Teacher();
t.printValue(10);
}
}
輸出結果是：4444444444
4.找錯誤
int tolower(const char *str)
{
if(NULL==str) return 0;
int i=0,iCount=0;
for(;i<strlen(str);i++)
{
if(str[i]<='Z'||str[i]>='A')
{
str[i]+='z'-'Z';
iCount++;
}
}
return iCount;
}
5有個長度為12的無重復有序表，按折半查找法進行查找，在表內各元素等概率情況下，查找成功所需的平均比較（三元比較）的次數為（）
A 35/12 B37/12 C 39/12 D 43/12
6從n個數里面找最大的兩個數理論最少需要比較
A 2logn B 2 logn -1 C n+ logn -2 D 2n-3
7 386781634*234659874= 6（30秒）
8Linux的非root用戶，在自己的目錄中，不可以刪除非空目錄dirs的方法是：
A rm dir dirs B rm-rdirs C mv dirs /dev/null D destroy dirs
9 Shell運算結果是3的是
A echo(9/3)
B echo$[16/5]
C echo$((10-7))
D echo’21/6’|bc
大題：
1 每個整數0-9這10個數組成，如223有2個2 ，和1個3，輸入m和n（0<m<n<10^20）
求出m到n之間所有整數共包含了多少個0，1。。。。9
實現函數void foo(const char*m, const char * n, char * result, size_t len )
result為輸出緩沖，len為result的長度。
要求寫出思路、程序程序效率，計算時間復雜度和空間復雜度
2 linux32位系統下有10個無序文件，各文件大小不一（均小于1G）現在需要將此10個文件歸并為一組，不超過10個有序文件（第一個文件最大數小于或等于第二個文件最小數，依次類推）請選擇你擅長的語言實現說明 文件的每一行最大不超過128位的阿拉伯數字組合，每一行只有一個數字，頭一位不是零
要求寫出思路和程序，計算時間復雜度和空間復雜度
3 網頁3種操作，查詢，刪除，最加到末尾
例如：每頁顯示20個，現在要查第50頁。假如用有序數組，則從下標20×49開始，直接返回后面20個即可，但是當刪除時會有大量數據移動，所以數組對刪除效率低，另外一種方法是，不刪除只作標記，但是查詢時必須又從頭開始計數，數一下應該從哪個位開始返回
設計一種數據結構高效率的完成3種功能
限制：1 操作在硬盤上發生
2 網頁大小不相同
3總數小于10M
4單個小于100K
4數據庫方面，不敢興趣沒記，不過看了下，不是很難
百度0711月4日網上筆試題及答案（僅供參考）?
1 編程：
用C語言實現一個revert函數，它的功能是將輸入的字符串在原串上倒序后返回。
2 編程：
用C語言實現函數void * memmove(void *dest,const void *src,size_t n)。memmove函數的功能是拷貝src所指的
內存內容前n個字節到dest所指的地址上。
3 英文拼寫糾錯：
在用戶輸入英文單詞時，經常發生錯誤，我們需要對其進行糾錯。假設已經有一個包含了正確英文單詞的詞典，請你設計一個拼寫糾錯的程序。
（1）請描述你解決這個問題的思路；
（2）請給出主要的處理流程，算法，以及算法的復雜度；
（3）請描述可能的改進（改進的方向如效果，性能等等，這是一個開放問題）。
4 尋找熱門查詢：
搜索引擎會通過日志文件把用戶每次檢索使用的所有檢索串都記錄下來，每個查詢串的長度為1-255字節。假設目前有一千萬個記錄，這些查詢串的重復度比較高，雖然總數是1千萬，但如果除去重復后，不超過3百萬個。一個查詢串的重復度越高，說明查詢它的用戶越多，也就是越熱門。請你統計最熱門的10個查詢串，要求使用的內存不能超過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 題
char *revert(char * str)
{
int n=strlen(str);
int i=0;
char c;
for(i=0;i {
c=str;
str=str[n-i];
str[n-i]=c;
}
return str;
}
///
2 題
void * memmove(void *dest,const void *src,size_t n)
{
assert((dest!=0)&&(src!=0));
char * temp=(char * )dest;
char * ss=(char * )src;
int i=0;
for(;i {
*temp =*ss ;
}
return temp;
}
/
3 題
(1)思路: 字典以字母鍵樹組織，在用戶輸入同時匹配
(2) 流程:
每輸入一個字母：?
沿字典樹向下一層，
a）若可以順利下行，則繼續至結束，給出結果；
b)若該處不能匹配，糾錯處理，給出拼寫建議,繼續至a）；
算法:
1.在字典中查找單詞
字典采用27叉樹組織,每個節點對應一個字母,查找就是一個字母
一個字母匹配.算法時間就是單詞的長度k.
2.糾錯算法
情況:當輸入的最后一個字母不能匹配時就提示出錯,簡化出錯處理，?
動態提示可能 處理方法:
(a)當前字母前缺少了一個字母：搜索樹上兩層到當前的匹配作為建議；
(b)當前字母拼寫錯誤：當前字母的鍵盤相鄰作為提示；（只是簡單的描述，可 以有更多的）
根據分析字典特征和用戶單詞已輸入部分選擇(a),(b)處理
復雜性分析：影響算法的效率主要是字典的實現與糾錯處理
(a）字典的實現已有成熟的算法，改進不大，也不會成為瓶頸；
(b)糾錯策略要簡單有效 ,如前述情況，是線性復雜度；
(3)改進
策略選擇最是重要，可以采用統計學習的方法改進。
//
4 題
(1)思路：用哈希做
(2) 首先逐次讀入查詢串，算哈希值，保存在內存數組中，同時統計頻度（注意值與日志項對應關系）?
my.chinahrlab.com 選出前十的頻度，取出對應的日志串，簡單不過了。哈希的設計是關鍵。
?
//
5 題
（1）思路：先將集合按照大小排列后,優先考慮小的集合是否與大的集合有交集。有就合并，如果小集合與所有其他集
合都沒有交集，則獨立。獨立的集合在下一輪的比較中不用考慮。這樣就可以盡量減少字符串的比較次數。當所有集合
都獨立的時候，就終止。
（2）處理流程：
1.將集合按照大小排序，組成集合合并待處理列表
2.選擇最小的集合，找出與之有交集的集合，如果有，合并之；如果無，則與其它集合是獨立集合，從待處理列表 中刪
除。
3.重復直到待處理列表為空
算法： 1。將集合按照大小從小到大排序,組成待處理的集合列表。 2。取出待處理集合列表中最小的集合，對于集合的
?
每個元素，依次在其他集合中搜索是否有此元素存在：
1>若存在，則將此小集合與大集合合并，并根據大小插入對應的位置 。轉3。
2>若不存在，則在該集合中取下一個元素。如果無下一個元素，即所有元素都不存在于其他集合。則表明此集合獨立，
從待處理集合列表中刪除。并加入結果集合列表。轉3。
3。如果待處理集合列表不為空，轉2。
如果待處理集合列表為空，成功退出，則結果集合列表就是最終的輸出。
算法復雜度分析：
假設集合的個數為n，最大的集合元素為m 排序的時間復雜度可以達到n*log(n) 然后對于元素在其他集合中查找，最壞情況下為（n-1）*m 查找一個集合是否與其他集合有交集的最壞情況是m*m*(n-1) 合并的時間復雜度不會超過查找集合有交集的最壞情況。所以最終最壞時間復雜度為O(m*m*n*n)
需要說明的是：此算法的平均時間復雜度會很低，因為無論是查找還是合并，都是處于最壞情況的概率很小，而且排序后優先用最小集合作為判斷是否獨立的對象，優先與最大的集合進行比較，這些都最大的回避了最壞情況。
?
?(3)可能的改進：
首先可以實現將每個集合里面的字符串按照字典序進行排列，這樣就可以將查找以及合并的效率增高。另外，可能采取恰當的數據結構也可以將查找以及合并等操作的效率得到提高。
2. 2. 百度面試
2.1 ?2013年9月26日，百度技術類一二面
1、給定一數組，輸出滿足2a=b（a，b代表數組中的數）的數對，要求時間復雜度盡量低。
2、搜索引擎多線程中每個線程占用多少內存？如果搜索引擎存儲網頁內存占用太大怎么解決？
3、有很多url，例如*.baidu.com，*.sina.com ......
現在給你一個sports.sina.com 快速匹配出是*.sina.com。點評：老題，此前blog內曾整理過。
4、找出字符串的編輯距離，即把一個字符串s1最少經過多少步操作變成編程字符串s2，操作有三種，添加一個字符，刪除一個字符，修改一個字符（只要聽過編輯距離，知道往動態規劃上想，很快就可以找到解法）。
5、編程實現memcopy，注意考慮目標內存空間和源空間重疊的時候。
6、實現簡單的一個查找二叉樹的深度的函數。
?
2.2 ?百度軟件開發工程師一面問題
1.有101個數，為[1，100]之間的數，其中一個數是重復的，如何尋找這個重復的數，其時間復雜度和空間復雜度是多少？
2.Java中抽象類與接口的區別。
3.進程與線程之間的聯系與區別。（多家公司都在問，好好研究一下）
4.談談對設計模式的認識與理解，簡單介紹一下你所知道的設計模式。（多家公司都問，Android方向面試必考的）
5.線程、多線程相關（必問）
6.Linux常用的命令，shell編程，grep命令的使用。
7.海量數據查找或者排序，有資源限制要求。（?？嫉?#xff09;
? ? ? ? 建議：簡歷中對自己的專業技能要實事求是的寫，突出自己的重點，不宜托大，面試官面試時提問的依據就是簡歷上的內容。百度的工作環境很好，做技術的員工給人的感覺就是雖然人家的技術水平很高，但是都比較謙遜。百度確實是一個不錯的互聯網公司。
2.3 ?百度Android兩輪面試經驗
百度技術面試分為兩輪：
第一輪基礎技術面試，一般為項目負責人，主要考察基本知識及知識廣度
第二輪面試一般為部門負責 人，主要考察技術深度?；A面試感覺個人答的還不錯，主要詢問了一些關于android基本知識的考察，涉及到Activity之間的跳轉，然后問了一些 關于所參與項目中遇到的?
問題，比如現在做的云信項目中，如何提供傳輸效率等，然后討論了一下關于View刷新機制等問題?？傮w來看一面比較容易，時間差不多一個半小時。
第二輪面試，面試官看起來挺嚴肅的，當然由于是考技術深度，所以難度加大了，當然自己也敗在這里邊了。由于看到簡歷邊有說JNI這塊，他就特地主要文這塊了，所有問題基本都是以C和數據結構為主。
主要問道：
1. 實現Strlen（char* str）
2. 說說常見的兩種數據結構之間的區別，這里邊問道了MAP,TREE,隊列，數據，棧等。并且說說時間復雜度及空間復雜度。
3. 說說地圖定位方式，詳細說說wifi定位是如何實現的。
總體而言，之所以答的不好，對常見的數據結構確實并不是很熟悉，沒有做好充分準備，建議如果去面試，好好復習《劍指名企Offer》。
第三個問題，面試官讓發揮想象去考慮wifi是怎么實現定位的，沒有答出來。
轉自請注明來源：http://www.dy1280.com
轉載于:https://blog.51cto.com/6712754/1549946
總結
以上是生活随笔為你收集整理的百度2014校园招聘笔试面试汇总的全部內容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： 计算机绘图课程绘图模式主要有,关于“计算
- 下一篇： 多媒体文件播放器汇总