百度校園招聘筆試題目分享：
1、找到滿足條件的數組
給定函數d(n)=n+n的各位之和，n為正整數，如d(78)=78+7+8=93。這樣這個函數可以看成一個生成器，如93可以看成由78生成。
定義數A：數A找不到一個數B可以由d(B)=A，即A不能由其他數生成。現在要寫程序，找出1至10000里的所有符合數A定義的數。
回答：
申請一個長度為10000的bool數組，每個元素代表對應的值是否可以有其它數生成。開始時將數組中的值都初始化為false。
由於大於10000的數的生成數必定大於10000，所以我們只需遍歷1到10000中的數，計算生成數，並將bool數組中對應的值設置為true，表示這個數可以有其它數生成。
最後bool數組中值為false的位置對應的整數就是不能由其它數生成的。
2、實現一個函數，對一個正整數n，算得到1需要的最少操作次數。操作規則為：如果n為偶數，將其除以2；如果n為奇數，可以加1或減1；一直處理下去。
例子：
func(7) = 4，可以證明最少需要4次運算
n = 7
n-1 6
n/2 3
n-1 2
n/2 1
要求：實現函數(實現儘可能高效) int func(unsign int n)；n為輸入，返回最小的運算次數。給出思路(文字描述)，完成代碼，並分析你算法的時間複雜度。
答：
假設n表示成二進制有x bit，可以看出計算複雜度為O(2^x)，也就是O(n)。
將n轉換到二進制空間來看（比如7為111，6為110）：
- 如果最後一位是0，則對應於偶數，直接進行除2操作。
- 如果最後一位是1，情況則有些複雜。
**如果最後幾位是???01，則有可能為???001，???1111101。在第一種情況下，顯然應該-1；在第二種情況下-1和+1最終需要的步數相同。所以在???01的情況下，應該選擇-1操作。
**如果最後幾位是???011，則有可能為???0011，???11111011。在第一種情況下，+1和-1最終需要的步數相同；在第二種情況下+1步數更少些。所以在???011的情況下，應該選擇+1操作。
**如果最後有更多的連續1，也應該選擇+1操作。
如果最後剩下的各位都是1，則有11時應該選擇-1；111時+1和-1相同；1111時應選擇+1；大於四個1時也應該選擇+1；
由以上的分析可知，奇數的時候加1或減1，完全取決於二進制的後兩位，如果後兩位是10、00那麼肯定是偶數，選擇除以2，如果後兩位是01、11，那麼選擇結果會不一樣的，如果是*****01，那麼選擇減1，如果是*****11，那麼選擇加1，特殊情況是就是n是3的時候，選擇減1操作。
3、一個大的含有50M個URL的記錄，一個小的含有500個URL的記錄，找出兩個記錄里相同的URL。
回答：
首先使用包含500個url的文件創建一個hash_set。
然後遍歷50M的url記錄，如果url在hash_set中，則輸出此url並從hash_set中刪除這個url。
所有輸出的url就是兩個記錄里相同的url。
4、海量日誌數據，提取出某日訪問百度次數最多的那個地址。
回答：
如果日誌文件足夠的大，大到不能完全加載到內存中的話。
那麼可以考慮分而治之的策略，按照IP位址的hash(地址)%1024值，將海量日誌存儲到1024個小文件中。每個小文件最多包含4M個IP位址。
對於每個小文件，可以構建一個地址作為key，出現次數作為value的hash_map，並記錄當前出現次數最多的1個IP位址。
有了1024個小文件中的出現次數最多的地址，我們就可以輕鬆得到總體上出現次數最多的地址。
5、螞蟻爬杆問題
有一根27厘米長的細木桿，在第3厘米，7厘米，11厘米，17厘米，23厘米這五個位置上各有一隻螞蟻，木桿很細，不能同時通過兩隻螞蟻，開始時，螞蟻的頭朝向左還是右是任意的，他們只會朝前走或掉頭，但不會後退，當兩隻螞蟻相遇後，螞蟻會同時掉頭朝反方向走，假設螞蟻們每秒鐘可以走1厘米的距離。求所有螞蟻都離開木桿的最小時間和最大時間。
答案：
兩隻螞蟻相遇後，各自掉頭朝相反方向走。如果我們不考慮每個螞蟻的具體身份，這和兩隻螞蟻相遇後，打個招呼繼續向前走沒有什麼區別。
所有螞蟻都離開木桿的最小時間為
max(min(3,27-3),min(7,27-7), min(11,27-11), min(17,27-17),min(23,27-23))=11
所有螞蟻都離開木桿的最大時間為
max(max(3,27-3),max(7,27-7), max(11,27-11), max(17,27-17),max(23,27-23))=24
6、有10個文件，每個文件1G，每個文件的每一行都存放的是用戶的query，每個文件的query都可能重複。如何按照query的頻度排序？
回答：
1）讀取10個文件，按照hash(query)%10的結果將query寫到對應的文件中。這樣我們就有了10個大小約為1G的文件。任意一個query只會出現在某個文件中。
2）對於1）中獲得的10個文件，分別進行如下操作
-利用hash_map（query，query_count）來統計每個query出現的次數。
-利用堆排序算法對query按照出現次數進行排序。
-將排序好的query輸出的文件中。
這樣我們就獲得了10個文件，每個文件中都是按頻率排序好的query。
3）對2）中獲得的10個文件進行歸併排序，並將最終結果輸出到文件中。
1、找到滿足條件的數組
給定函數d(n)=n+n的各位之和，n為正整數，如d(78)=78+7+8=93。這樣這個函數可以看成一個生成器，如93可以看成由78生成。
定義數A：數A找不到一個數B可以由d(B)=A，即A不能由其他數生成。現在要寫程序，找出1至10000里的所有符合數A定義的數。
回答：
申請一個長度為10000的bool數組，每個元素代表對應的值是否可以有其它數生成。開始時將數組中的值都初始化為false。
由於大於10000的數的生成數必定大於10000，所以我們只需遍歷1到10000中的數，計算生成數，並將bool數組中對應的值設置為true，表示這個數可以有其它數生成。
最後bool數組中值為false的位置對應的整數就是不能由其它數生成的。
2、實現一個函數，對一個正整數n，算得到1需要的最少操作次數。操作規則為：如果n為偶數，將其除以2；如果n為奇數，可以加1或減1；一直處理下去。
例子：
func(7) = 4，可以證明最少需要4次運算
n = 7
n-1 6
n/2 3
n-1 2
n/2 1
要求：實現函數(實現儘可能高效) int func(unsign int n)；n為輸入，返回最小的運算次數。給出思路(文字描述)，完成代碼，並分析你算法的時間複雜度。
答：
假設n表示成二進制有x bit，可以看出計算複雜度為O(2^x)，也就是O(n)。
將n轉換到二進制空間來看（比如7為111，6為110）：
- 如果最後一位是0，則對應於偶數，直接進行除2操作。
- 如果最後一位是1，情況則有些複雜。
**如果最後幾位是???01，則有可能為???001，???1111101。在第一種情況下，顯然應該-1；在第二種情況下-1和+1最終需要的步數相同。所以在???01的情況下，應該選擇-1操作。
**如果最後幾位是???011，則有可能為???0011，???11111011。在第一種情況下，+1和-1最終需要的步數相同；在第二種情況下+1步數更少些。所以在???011的情況下，應該選擇+1操作。
**如果最後有更多的連續1，也應該選擇+1操作。
如果最後剩下的各位都是1，則有11時應該選擇-1；111時+1和-1相同；1111時應選擇+1；大於四個1時也應該選擇+1；
由以上的分析可知，奇數的時候加1或減1，完全取決於二進制的後兩位，如果後兩位是10、00那麼肯定是偶數，選擇除以2，如果後兩位是01、11，那麼選擇結果會不一樣的，如果是*****01，那麼選擇減1，如果是*****11，那麼選擇加1，特殊情況是就是n是3的時候，選擇減1操作。
3、一個大的含有50M個URL的記錄，一個小的含有500個URL的記錄，找出兩個記錄里相同的URL。
回答：
首先使用包含500個url的文件創建一個hash_set。
然後遍歷50M的url記錄，如果url在hash_set中，則輸出此url並從hash_set中刪除這個url。
所有輸出的url就是兩個記錄里相同的url。
4、海量日誌數據，提取出某日訪問百度次數最多的那個地址。
回答：
如果日誌文件足夠的大，大到不能完全加載到內存中的話。
那麼可以考慮分而治之的策略，按照IP位址的hash(地址)%1024值，將海量日誌存儲到1024個小文件中。每個小文件最多包含4M個IP位址。
對於每個小文件，可以構建一個地址作為key，出現次數作為value的hash_map，並記錄當前出現次數最多的1個IP位址。
有了1024個小文件中的出現次數最多的地址，我們就可以輕鬆得到總體上出現次數最多的地址。
5、螞蟻爬杆問題
有一根27厘米長的細木桿，在第3厘米，7厘米，11厘米，17厘米，23厘米這五個位置上各有一隻螞蟻，木桿很細，不能同時通過兩隻螞蟻，開始時，螞蟻的頭朝向左還是右是任意的，他們只會朝前走或掉頭，但不會後退，當兩隻螞蟻相遇後，螞蟻會同時掉頭朝反方向走，假設螞蟻們每秒鐘可以走1厘米的距離。求所有螞蟻都離開木桿的最小時間和最大時間。
答案：
兩隻螞蟻相遇後，各自掉頭朝相反方向走。如果我們不考慮每個螞蟻的具體身份，這和兩隻螞蟻相遇後，打個招呼繼續向前走沒有什麼區別。
所有螞蟻都離開木桿的最小時間為
max(min(3,27-3),min(7,27-7), min(11,27-11), min(17,27-17),min(23,27-23))=11
所有螞蟻都離開木桿的最大時間為
max(max(3,27-3),max(7,27-7), max(11,27-11), max(17,27-17),max(23,27-23))=24
6、有10個文件，每個文件1G，每個文件的每一行都存放的是用戶的query，每個文件的query都可能重複。如何按照query的頻度排序？
回答：
1）讀取10個文件，按照hash(query)%10的結果將query寫到對應的文件中。這樣我們就有了10個大小約為1G的文件。任意一個query只會出現在某個文件中。
2）對於1）中獲得的10個文件，分別進行如下操作
-利用hash_map（query，query_count）來統計每個query出現的次數。
-利用堆排序算法對query按照出現次數進行排序。
-將排序好的query輸出的文件中。
這樣我們就獲得了10個文件，每個文件中都是按頻率排序好的query。
3）對2）中獲得的10個文件進行歸併排序，並將最終結果輸出到文件中。
收藏