百度校園招聘筆試題目

時間：2022-11-09 07:16:31 面試試題我要投稿

相關(guān)推薦

百度校園招聘筆試題目

　　1、找到滿足條件的數(shù)組

百度校園招聘筆試題目

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

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

　　回答：

　　申請一個長度為10000的bool數(shù)組，每個元素代表對應(yīng)的值是否可以有其它數(shù)生成。開始時將數(shù)組中的值都初始化為false。

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

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

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

　　例子：

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

　　n = 7

　　n-1 6

　　n/2 3

　　n-1 2

　　n/2 1

　　要求：實(shí)現(xiàn)函數(shù)(實(shí)現(xiàn)盡可能高效) int func(unsign int n);n為輸入，返回最小的運(yùn)算次數(shù)。給出思路(文字描述)，完成代碼，并分析你算法的時間復(fù)雜度。

　　答：

　　假設(shè)n表示成二進(jìn)制有x bit，可以看出計(jì)算復(fù)雜度為O(2^x)，也就是O(n)。

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

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

　　- 如果最后一位是1，情況則有些復(fù)雜。

　　**如果最后幾位是???01，則有可能為???001，???1111101。在第一種情況下，顯然應(yīng)該-1;在第二種情況下-1和+1最終需要的步數(shù)相同。所以在???01的情況下，應(yīng)該選擇-1操作。

　　**如果最后幾位是???011，則有可能為???0011，???11111011。在第一種情況下，+1和-1最終需要的步數(shù)相同;在第二種情況下+1步數(shù)更少些。所以在???011的情況下，應(yīng)該選擇+1操作。

　　**如果最后有更多的連續(xù)1，也應(yīng)該選擇+1操作。

　　如果最后剩下的各位都是1，則有11時應(yīng)該選擇-1;111時+1和-1相同;1111時應(yīng)選擇+1;大于四個1時也應(yīng)該選擇+1;

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

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

　　回答：

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

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

　　所有輸出的url就是兩個記錄里相同的url。

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

　　回答：

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

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

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

　　有了1024個小文件中的出現(xiàn)次數(shù)最多的IP，我們就可以輕松得到總體上出現(xiàn)次數(shù)最多的IP。

　　5、螞蟻爬桿問題

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

　　答案：

　　兩只螞蟻相遇后，各自掉頭朝相反方向走。如果我們不考慮每個螞蟻的具體身份，這和兩只螞蟻相遇后，打個招呼繼續(xù)向前走沒有什么區(qū)別。

　　所有螞蟻都離開木桿的最小時間為

　　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都可能重復(fù)。如何按照query的頻度排序?

　　回答：

　　1)讀取10個文件，按照hash(query)%10的結(jié)果將query寫到對應(yīng)的文件中。這樣我們就有了10個大小約為1G的文件。任意一個query只會出現(xiàn)在某個文件中。

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

　　-利用hash_map(query，query_count)來統(tǒng)計(jì)每個query出現(xiàn)的次數(shù)。

　　-利用堆排序算法對query按照出現(xiàn)次數(shù)進(jìn)行排序。