百度校園招聘筆試題目

百度校園招聘筆試題目

百度校內(nèi)聘請(qǐng)筆試題目共享：

1、找到滿(mǎn)意條件的數(shù)組

給定函數(shù)d(n)=n+n的各位之和，n為正整數(shù)，如d(78)=78+7+8=93。這樣這個(gè)函數(shù)可以看成一個(gè)生成器，如93可以看成由78生成。

定義數(shù)A：數(shù)A找不到一個(gè)數(shù)B可以由d(B)=A，即A不能由其他數(shù)生成?，F(xiàn)在要寫(xiě)程序，找出1至10000里的全部符合數(shù)A定義的數(shù)。

回答：

申請(qǐng)一個(gè)長(zhǎng)度為10000的bool數(shù)組，每個(gè)元素代表對(duì)應(yīng)的值是否可以有其它數(shù)生成。開(kāi)頭時(shí)將數(shù)組中的值都初始化為false。

由于大于10000的數(shù)的生成數(shù)必定大于10000，所以我們只需遍歷1到10000中的數(shù)，計(jì)算生成數(shù)，并將bool數(shù)組中對(duì)應(yīng)的值設(shè)置為true，表示這個(gè)數(shù)可以有其它數(shù)生成。

最終bool數(shù)組中值為false的位置對(duì)應(yīng)的整數(shù)就是不能由其它數(shù)生成的。

2、實(shí)現(xiàn)一個(gè)函數(shù)，對(duì)一個(gè)正整數(shù)n，算得到1需要的最少操作次數(shù)。操作規(guī)章為：假如n為偶數(shù)，將其除以2；假如n為奇數(shù)，可以加1或減1；始終處理下去。

例子：

func(7)=4，可以證明最少需要4次運(yùn)算

n=7

n-16

n/23

n-12

n/21

要求：實(shí)現(xiàn)函數(shù)(實(shí)現(xiàn)盡可能高效)intfunc(unsignintn)；n為輸入，返回最小的運(yùn)算次數(shù)。給出思路(文字描述)，完成代碼，并分析你算法的時(shí)間簡(jiǎn)單度。

答：

假設(shè)n表示成二進(jìn)制有xbit，可以看出計(jì)算簡(jiǎn)單度為O(2^x)，也就是O(n)。

將n轉(zhuǎn)換到二進(jìn)制空間來(lái)看（比如7為111，6為110）：

-假如最終一位是0，則對(duì)應(yīng)于偶數(shù)，直接進(jìn)行除2操作。

-假如最終一位是1，狀況則有些簡(jiǎn)單。

**假如最終幾位是???01，則有可能為???001，???1111101。在第一種狀況下，明顯應(yīng)當(dāng)-1；在其次種狀況下-1和+1最終需要的步數(shù)相同。所以在???01的狀況下，應(yīng)當(dāng)選擇-1操作。

**假如最終幾位是???011，則有可能為???0011，???11111011。在第一種狀況下，+1和-1最終需要的步數(shù)相同；在其次種狀況下+1步數(shù)更少些。所以在???011的狀況下，應(yīng)當(dāng)選擇+1操作。

**假如最終有更多的連續(xù)1，也應(yīng)當(dāng)選擇+1操作。

假如最終剩下的各位都是1，則有11時(shí)應(yīng)當(dāng)選擇-1；111時(shí)+1和-1相同；1111時(shí)應(yīng)選擇+1；大于四個(gè)1時(shí)也應(yīng)當(dāng)選擇+1；

由以上的分析可知，奇數(shù)的時(shí)候加1或減1，完全取決于二進(jìn)制的后兩位，假如后兩位是10、00那么確定是偶數(shù)，選擇除以2，假如后兩位是01、11，那么選擇結(jié)果會(huì)不一樣的，假如是*****01，那么選擇減1，假如是*****11，那么選擇加1，特別狀況是就是n是3的時(shí)候，選擇減1操作。

3、一個(gè)大的含有50M個(gè)URL的記錄，一個(gè)小的含有500個(gè)URL的記錄，找出兩個(gè)記錄里相同的URL。

回答：

首先使用包含500個(gè)url的文件創(chuàng)建一個(gè)hash_set。

然后遍歷50M的url記錄，假如url在hash_set中，則輸出此url并從hash_set中刪除這個(gè)url。

全部輸出的url就是兩個(gè)記錄里相同的url。

4、海量日志數(shù)據(jù)，提取出某日訪(fǎng)問(wèn)百度次數(shù)最多的那個(gè)IP。

回答：

假如日志文件足夠的大，大到不能完全加載到內(nèi)存中的話(huà)。

那么可以考慮分而治之的策略，根據(jù)IP地址的hash(IP)%1024值，將海量日志存儲(chǔ)到1024個(gè)小文件中。每個(gè)小文件最多包含4M個(gè)IP地址。

對(duì)于每個(gè)小文件，可以構(gòu)建一個(gè)IP作為key，消失次數(shù)作為value的hash_map，并記錄當(dāng)前消失次數(shù)最多的1個(gè)IP地址。

有了1024個(gè)小文件中的消失次數(shù)最多的IP，我們就可以輕松得到總體上消失次數(shù)最多的IP。

5、螞蟻爬桿問(wèn)題

有一根27厘米長(zhǎng)的細(xì)木桿，在第3厘米，7厘米，11厘米，17厘米，23厘米這五個(gè)位置上各有一只螞蟻，木桿很細(xì)，不能同時(shí)通過(guò)兩只螞蟻，開(kāi)頭時(shí)，螞蟻的頭朝向左還是右是任意的，他們只會(huì)朝前走或掉頭，但不會(huì)后退，當(dāng)兩只螞蟻相遇后，螞蟻會(huì)同時(shí)掉頭朝反方向走，假設(shè)螞蟻們每秒鐘可以走1厘米的距離。求全部螞蟻都離開(kāi)木桿的最小時(shí)間和最大時(shí)間。

答案：

兩只螞蟻相遇后，各自掉頭朝相反方向走。假如我們不考慮每個(gè)螞蟻的詳細(xì)身份，這和兩只螞蟻相遇后，打個(gè)招呼連續(xù)向前走沒(méi)有什么區(qū)分。

全部螞蟻都離開(kāi)木桿的最小時(shí)間為

max(min(3,27-3),min(7,27-7),min(11,27-11),min(17,27-17),min(23,27-23))=11

全部螞蟻都離開(kāi)木桿的最大時(shí)間為

max(max(3,27-3),max(7,27-7),max(11,27-11),max(17,27-17),max(23,27-23))=24

6、有10個(gè)文件，每個(gè)文件1G，每個(gè)文件的每一行都存放的是用戶(hù)的query，每個(gè)文件的query都可能重復(fù)。如何根據(jù)query的頻度排序？

回答：

1）讀取10個(gè)文件，根據(jù)hash(query)%10的結(jié)果將query寫(xiě)到對(duì)應(yīng)的文件中。這樣我們就有了10個(gè)大小約為1G的文件。任意一個(gè)query只會(huì)消失在某個(gè)文件中。

2）對(duì)于1）中獲得的10個(gè)文件，分別進(jìn)行如下操作

-利用hash_map（query，query_count）來(lái)統(tǒng)計(jì)每個(gè)query消失的次數(shù)。

-利用