86      汽車大全

百度2012-筆試麵試題目匯總

從互聯網來，返回之！

//csdn博客目前暫時不再更新了，有興趣請訪問我的技術博客-曉的博客：zhangxiaolong.org 

研發

1.第一大題要求用二分查找在一個序列裏查找一個key。這題實際包含兩個小題。第一個小題它給出的函數原型是:
int f1(int* array,int size,int key);
具體要求大概是：array是個有序序列，要求用二分查找找出指定的key，如果key在序列中，返回序列的位置，如果key不在序列中，則返回key應當被插入的位置。
第二小題給出的原型也是一樣：
int f2(int* array,int size,int key);
不過要求卻不同。array是個先增後減的序列，臨界值mid的位置是不確定的。同樣的要求查找指定的key，如果key在序列中，則返回key的位置，如果不在，則直接返回-1（不必指出key應當插入的位置）。

2. 第二大題考的是“左孩子右兄弟”的樹結構，具體要求記不清了，大概是這棵樹共右N個結點，在v和m之間….之類的。
第三道大題考的是係統設計題。大概是有一批老數據要導入到新的機器上，這批數據是大小相當的總數為10萬個的二進製文件，導入時間與文件大小成線性關係， 一個500K的文件需要3秒的導入時間，文件的平均大小是1000K。用以轉換函數也已經有，不過這些函數存在不少問題，譬如會產生數組越界等等，然後時 間又不允許你重寫一套函數…，然後就要你設計一個方案來實現…大概就是問的這個方向，要你用文字表述清楚你的方案。

1 簡要說明樹的深度優先、廣度優先遍曆算法擠特點
2 一個複數相加的編碼挑錯題
3 告訴內存大小和cpu速度，計算可能的程序運行最長時間
4 複雜項目的組件編譯依賴，設計一個快速算法並計算複雜度

5 寫個c程序，返回字符串中最長數字字符串的長度和地址，不能用標準庫函數
6 設計個係統，存儲100億個url和屬性信息，並可以更改屬性信息和查找url，快速搜索站點的所有url及信息

算法

第一題：某個公司舉行一場羽毛球賽，有1001個人參加，現在為了評比出“最厲害的那個人”，進行淘汰賽，請問至少需要進行多少次比賽。
第二題：一百個燈泡排成一排，第一輪將所有燈泡打開；第二輪每隔一個燈泡關掉一個。即排在偶數的燈泡被關掉，第三輪每隔兩個燈泡，將開著的燈泡關掉，關掉的燈泡打開。依次類推，第n輪結束的時候，還有幾盞燈泡亮著。
第三題：有20個數組，每個數組裏麵有500個數組，降序排列，每個數字是32位的unit,求出這10000個數字中最大的500個

其他：

1、實現一個函數，對一個正整數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
要求：實現函數(實現盡可能高效)> · return 0;
·> · return 1 + func(n/2);
·> · int y = func(n – 1);
· if(x > y)
· return y+1;
· else
· return x+1;
· }

假設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；
·> · return 0;
·> · return 1 + func(n/2);
·> · return 2;
· if(n&2)
· return 1 + func(n+1);
· else
· return 1 + func(n-1);
· }

2、找到滿足條件的數組
給定函數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的位置對應的整數就是不能由其它數生成的。
3、一個大的含有50M個URL的記錄，一個小的含有500個URL的記錄，找出兩個記錄裏相同的URL。
回答：
首先使用包含500個url的文件創建一個hash_set。
然後遍曆50M的url記錄，如果url在hash_set中，則輸出此url並從hash_set中刪除這個url。
所有輸出的url就是兩個記錄裏相同的url。
4、海量日誌數據，提取出某日訪問百度次數最多的那個IP。
回答：
IP地址最多有2^32=4G種取值可能，所以不能完全加載到內存中。
可以考慮分而治之的策略，按照IP地址的hash(IP)%1024值，將海量日誌存儲到1024個小文件中。每個小文件最多包含4M個IP地址。
對於每個小文件，可以構建一個IP作為key，出現次數作為value的hash_map，並記錄當前出現次數最多的1個IP地址。
有了1024個小文件中的出現次數最多的IP，我們就可以輕鬆得到總體上出現次數最多的IP。
5、有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個文件進行歸並排序，並將最終結果輸出到文件中。
6、螞蟻爬杆問題
有一根27厘米長的細木杆，在第3厘米，7厘米，11厘米，17厘米，23厘米這五個位置上各有一隻螞蟻，木杆很細，不能同時通過兩隻螞蟻，開始時，螞蟻的頭朝向左還是右是任意的，他們隻會朝前走或掉頭，但不會後退，當兩隻螞蟻相遇後，螞蟻會同時掉頭朝反方向走，假設螞蟻們每秒鍾可以走1厘米的距離。求所有螞蟻都離開木杆的最小時間和最大時間。
答案：
兩隻螞蟻相遇後，各自掉頭朝相反方向走。如果我們不考慮每個螞蟻的具體身份，這和兩隻螞蟻相遇後，打個招唿繼續向前走沒有什麼區別。
所有螞蟻都離開木杆的最小時間為
max(min(3,27-3),min(7,27-7),> 所有螞蟻都離開木杆的最大時間為
max(max(3,27-3),max(7,27-7),> 7、當在瀏覽器中輸入一個url後回車，後台發生了什麼？比如輸入url後，你看到了百度的首頁，那麼這一切是如何發生的呢？
回答：
簡單來說有以下步驟：
1、查找域名對應的IP地址。這一步會依次查找瀏覽器緩存，係統緩存，路由器緩存，ISPDNS緩存，根域名服務器。
2、向IP對應的服務器發送請求。
3、服務器響應請求，發回網頁內容。
4、瀏覽器解析網頁內容。
當然，由於網頁可能有重定向，或者嵌入了圖片，AJAX，其它子網頁等等，這4個步驟可能反複進行多次才能將最終頁麵展示給用戶。
8、判斷兩棵樹是否相等，請實現兩棵樹是否相等的比較，相等返回1，否則返回其他值，並說明算法複雜度。
數據結構為：
[cpp]
·> 遞歸方法：
[cpp]
·> · return true;
·> · return false;
·> · return false;
· if( (CompTree(tree1->leftchild, tree2->leftchild) && CompTree(tree1->rightchild, tree2->rightchild)) || CompTree(tree1->leftchild, tree2->rightchild) && CompTree(tree1->rightchild, tree2->leftchild))
· return true;
· }

時間複雜度：
在樹的第0層，有1個節點，我們會進行1次函數調用；
在樹的第1層，有2個節點，我們可能會進行4次函數調用；
在樹的第2層，有4個節點，我們可能會進行16次函數調用；
….
在樹的第x層，有2^x個節點，我們可能會進行(2^x)^2次函數調用；
所以假設總節點數為n，則算法的複雜度為O(n^2)。
騰訊麵試題：求一個論壇的在線人數，假設有一個論壇，其注冊ID有兩億個，每個ID從登陸到退出會向一個日誌文件中記下登陸時間和退出時間，要求寫一個算法統計一天中論壇的用戶在線分布，取樣粒度為秒。
回答：
一天總共有3600*24=86400秒。
定義一個長度為86400的整數數組intdelta[86400]，每個整數對應這一秒的人數變化值，可能為正也可能為負。開始時將數組元素都初始化為0。
然後依次讀入每個用戶的登錄時間和退出時間，將與登錄時間對應的整數值加1，將與退出時間對應的整數值減1。
這樣處理一遍後數組中存儲了每秒中的人數變化情況。
定義另外一個長度為86400的整數數組intonline_num[86400]，每個整數對應這一秒的論壇在線人數。
假設一天開始時論壇在線人數為0，則第1秒的人數online_num[0]=delta[0]。第n+1秒的人數online_num[n]=online_num[n-1]+delta[n]。
這樣我們就獲得了一天中任意時間的在線人數。
9、三個警察和三個囚徒的過河問題
三個警察和三個囚徒共同旅行。一條河擋住了去路，河邊有一條船，但是每次隻能載2人。存在如下的危險：無論在河的哪邊，當囚徒人數多於警察的人數時，將有警察被囚徒殺死。問題：請問如何確定渡河方案，才能保證6人安全無損的過河。
回答：警察囚徒過去，警察回來
囚徒囚徒過去，囚徒回來
警察警察過去，警察囚徒回來
警察警察過去，囚徒回來
囚徒囚徒過去，囚徒回來
囚徒囚徒過去
10、從300萬字符串中找到最熱門的10條
搜索的輸入信息是一個字符串，統計300萬輸入信息中的最熱門的前10條，我們每次輸入的一個字符串為不超過255byte，內存使用隻有1G。請描述思想，寫出算法（c語言），空間和時間複雜度。
答案：
300萬個字符串最多（假設沒有重複，都是最大長度）占用內存3M*1K/4=0.75G。所以可以將所有字符串都存放在內存中進行處理。
可以使用key為字符串（事實上是字符串的hash值），值為字符串出現次數的hash來統計每個每個字符串出現的次數。並用一個長度為10的數組/鏈表來存儲目前出現次數最多的10個字符串。
這樣空間和時間的複雜度都是O(n)。
11、如何找出字典中的兄弟單詞。給定一個單詞a，如果通過交換單詞中字母的順序可以得到另外的單詞b，那麼定義b是a的兄弟單詞。現在給定一個字典，用戶輸入一個單詞，如何根據字典找出這個單詞有多少個兄弟單詞？
答案：
使用hash_map和鏈表。
首先定義一個key，使得兄弟單詞有相同的key，不是兄弟的單詞有不同的key。例如，將單詞按字母從小到大重新排序後作為其key，比如bad的key為abd，good的key為dgoo。
使用鏈表將所有兄弟單詞串在一起，hash_map的key為單詞的key，value為鏈表的起始地址。
開始時，先遍曆字典，將每個單詞都按照key加入到對應的鏈表當中。當需要找兄弟單詞時，隻需求取這個單詞的key，然後到hash_map中找到對應的鏈表即可。
這樣創建hash_map時時間複雜度為O(n)，查找兄弟單詞時時間複雜度是O(1)。
12、找出數組中出現次數超過一半的數，現在有一個數組，已知一個數出現的次數超過了一半，請用O(n)的複雜度的算法找出這個數。
答案1：
創建一個hash_map，key為數組中的數，value為此數出現的次數。遍曆一遍數組，用hash_map統計每個數出現的次數，並用兩個值存儲目前出現次數最多的數和對應出現的次數。
這樣可以做到O(n)的時間複雜度和O(n)的空間複雜度，滿足題目的要求。
但是沒有利用“一個數出現的次數超過了一半”這個特點。也許算法還有提高的空間。
答案2：
使用兩個變量A和B，其中A存儲某個數組中的數，B用來計數。開始時將B初始化為0。
遍曆數組，如果B=0，則令A等於當前數，令B等於1；如果當前數與A相同，則B=B+1；如果當前數與A不同，則令B=B-1。遍曆結束時，A中的數就是要找的數。
這個算法的時間複雜度是O(n)，空間複雜度為O(1)。
13、找出被修改過的數字
n個空間（其中n<1M），存放a到a+n-1的數，位置隨機且數字不重複，a為正且未知。現在第一個空間的數被誤設置為-1。已經知道被修改的數不是最小的。請找出被修改的數字是多少。
例如：n=6，a=2，原始的串為5,3,7,6,2,4。現在被別人修改為-1,3,7,6,2,4。現在希望找到5。
回答：
由於修改的數不是最小的，所以遍曆第二個空間到最後一個空間可以得到a的值。
a到a+n-1這n個數的和是total=na+(n-1)n/2。
將第二個至最後一個空間的數累加獲得sub_total。
那麼被修改的數就是total-sub_total。
14、設計DNS服務器中cache的數據結構。
要求設計一個DNS的Cache結構，要求能夠滿足每秒5000以上的查詢，滿足IP數據的快速插入，查詢的速度要快。（題目還給出了一係列的數據，比如：站點數總共為5000萬，IP地址有1000萬，等等）
回答：
DNS服務器實現域名到IP地址的轉換。
每個域名的平均長度為25個字節（估計值），每個IP為4個字節，所以Cache的每個條目需要大概30個字節。
總共50M個條目，所以需要1.5G個字節的空間。可以放置在內存中。（考慮到每秒5000次操作的限製，也隻能放在內存中。）
可以考慮的數據結構包括hash_map，字典樹，紅黑樹等等。
15、找出給定字符串對應的序號。
序列Seq=[a,b,…z,aa,ab…az,ba,bb,…bz,…,za,zb,…zz,aaa,…]類似與excel的排列，任意給出一個字符串s=[a-z]+(由a-z字符組成的任意長度字符串），請問s是序列Seq的第幾個。
回答：
注意到每滿26個就會向前進一位，類似一個26進製的問題。
比如ab，則位置為26*1+2；
比如za，則位置為26*26+1；
比如abc，則位置為26*26*1+26*2+3；
16、找出第k大的數字所在的位置。寫一段程序，找出數組中第k大小的數，輸出數所在的位置。例如{2，4，3，4，7}中，第一大的數是7，位置在4。第二大、第三大的數都是4，位置在1、3隨便輸出哪一個均可。
答案：
先找到第k大的數字，然後再遍曆一遍數組找到它的位置。所以題目的難點在於如何最高效的找到第k大的數。
我們可以通過快速排序，堆排序等高效的排序算法對數組進行排序，然後找到第k大的數字。這樣總體複雜度為O(NlogN)。
我們還可以通過二分的思想，找到第k大的數字，而不必對整個數組排序。從數組中隨機選一個數t，通過讓這個數和其它數比較，我們可以將整個數組分成了兩部分並且滿足，{x,xx,…,t}<{y,yy,…}。
在將數組分成兩個數組的過程中，我們還可以記錄每個子數組的大小。這樣我們就可以確定第k大的數字在哪個子數組中。
然後我們繼續對包含第k大數字的子數組進行同樣的劃分，直到找到第k大的數字為止。
平均來說，由於每次劃分都會使子數組縮小到原來1/2，所以整個過程的複雜度為O(N)。
17、給40億個不重複的unsigned> 18、在一個文件中有10G個整數，亂序排列，要求找出中位數。內存限製為2G。
回答：
不妨假設10G個整數是64bit的。
2G內存可以存放256M個64bit整數。
我們可以將64bit的整數空間平均分成256M個取值範圍，用2G的內存對每個取值範圍內出現整數個數進行統計。這樣遍曆一邊10G整數後，我們便知道中數在那個範圍內出現，以及這個範圍內總共出現了多少個整數。
如果中數所在範圍出現的整數比較少，我們就可以對這個範圍內的整數進行排序，找到中數。如果這個範圍內出現的整數比較多，我們還可以采用同樣的方法將此範圍再次分成多個更小的範圍（256M=2^28，所以最多需要3次就可以將此範圍縮小到1，也就找到了中數）。
19、時分秒針在一天之內重合多少次？（24小時）
2次
而時針和分針重合了22次。
20、將多個集合合並成沒有交集的集合。
給定一個字符串的集合，格式如：{aaabbbccc}，{bbbddd}，{eeefff}，{ggg}，{dddhhh}要求將其中交集不為空的集合合並，要求合並完成後的集合之間無交集，例如上例應輸出{aaabbbcccdddhhh}，{eeefff}，{ggg}。
（1）請描述你解決這個問題的思路；
（2）請給出主要的處理流程，算法，以及算法的複雜度
（3）請描述可能的改進。
回答：
集合使用hash_set來表示，這樣合並時間複雜度比較低。
1、給每個集合編號為0，1，2，3…
2、創建一個hash_map，key為字符串，value為一個鏈表，鏈表節點為字符串所在集合的編號。遍曆所有的集合，將字符串和對應的集合編號插入到hash_map中去。
3、創建一個長度等於集合個數的int數組，表示集合間的合並關係。例如，下標為5的元素值為3，表示將下標為5的集合合並到下標為3的集合中去。開始時將所有值都初始化為-1，表示集合間沒有互相合並。在集合合並的過程中，我們將所有的字符串都合並到編號較小的集合中去。
遍曆第二步中生成的hash_map，對於每個value中的鏈表，首先找到最小的集合編號（有些集合已經被合並過，需要順著合並關係數組找到合並後的集合編號），然後將鏈表中所有編號的集合都合並到編號最小的集合中（通過更改合並關係數組）。
4、現在合並關係數組中值為-1的集合即為最終的集合，它的元素來源於所有直接或間接指向它的集合。
算法的複雜度為O(n)，其中n為所有集合中的元素個數。
題目中的例子：
0:{aaabbbccc}
1:{bbbddd}
2:{eeefff}
3:{ggg}
4:{dddhhh}
生成的hash_map，和處理完每個值後的合並關係數組分別為
aaa:0。[-1,-1,-1,-1,-1]
bbb:0,1。[-1,0,-1,-1,-1]
ccc:0。[-1,0,-1,-1,-1]
ddd:1,4。[-1,0,-1,-1,0]
eee:2。[-1,0,-1,-1,0]
fff:2。[-1,0,-1,-1,0]
ggg:3。[-1,0,-1,-1,0]
hhh:4。[-1,0,-1,-1,0]
所以合並完後有三個集合，第0，1，4個集合合並到了一起。

軟件工程師

一 簡答：
1 說明數據庫和線程死鎖的原理和必要條件，如何防止死鎖。
2 麵向對象開發的三要素和五個基本原則。
3 Windows下內存管理敘述，並說明其優缺點。

二 算法和程序設計
1 某公司舉行羽毛球大賽，共1001人，采用淘汰製，至少需要多少場比賽？用程序模擬實現。
2 100盞燈，第一輪操作：全部亮燈；第二輪，隔一個滅一個燈，即第偶數盞等滅掉；第三輪：隔兩盞燈，如果是亮著的，滅掉，如果沒亮，則打開；以此類推，進行到第100輪操作的時候，有多少盞燈是亮著的？
3 20個數組，每個數組有500個數，都按照降序排列，而且每個數組中保存的是uint 類型的數，32位。問如何選擇其中的最大的500個數。

4 係統設計：太長了記不太清楚了，大意就是手機輸入法，數字2和字母abc在一個鍵上，3和def…9和wxyz。針對輸入法做了一下改進，聯係人保存在UserList中，現在輸入數字字符串NumStr“926”，則一下兩種情況可以返回：
1 手機號碼為13792611111等連續包含“926”的聯係人會返回；
2 萬年曆，王小二。。。等會返回；因為“926”對應的一種拚音組合是“WAN”，這樣wannianli,wangxiaoer等中包含wan，符合結果。
依據以上，寫出程序。
輸入：UserList,NumStr,和漢字拚音映射表Dir；
輸出：ResultList

我感覺自己是盡力答了。可能結果不盡如人意。
死鎖問題基本上差不多
麵向對象三要素：封裝繼承多態；五個原則不會。
內存管理答非所問，我寫的是堆啊棧啊常量區啊什麼的，問的實際不是這個！！！！應該是虛擬內存啊什麼的。要不為啥強調Windows下呢？

算法問題

100盞燈，剛開始毫無思路，後來忽然想到把每一盞燈變化的次數求出來不久行了嗎？這樣一看，題目 很明了，實際上就是告訴你有一百次操作，第 i 次操作就是把第 i*1,i*2…i*n(要小於等於100)個燈的狀態改變，這樣再看，那麼第1盞燈值變一次，第2，3，5…隻變了2次，第4盞燈隻變了3 次…瞬間明白，分解因數。。。但是樂極生悲，我當時想當然的認為隻要分解成1，本身，和其他素因子的個數就行了，在出考場的那一瞬間，我想到，其實不是素因子也可以。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。天哪！！！！！！！！！！！！！！！！！！！

20個數組問題：我感覺這道題應該不太難，可能是想讓我進行一些優化什麼的吧，提出一些高級的算法，不過我隻想到最簡單的情況，就是比較20個數組的第一個數，找最大的‘。假設第i組第一個最大，則這個數在10000個數中最大，保留，然後用剩餘19個數字和第i組第二個數比較，找最大，找到剩餘9999中最大的數字。。。依次，但是我一直不明白為啥要告訴32位。。。。。。應該是我有什麼沒想到的地方。。。

係統涉及題目，開始感覺不是特別難吧，但是把算法全部實現，我覺得我是難以完成，什麼字符串匹配了，都忘了，之好用JAVA中的String來投機取巧，但是這樣一來，還是有問題，怎樣把你輸入的StrNum轉化成所有拚音組合並且排除其中一些不可能的組合。我估計在短時間內寫不出來，而且實在惡心的不想繼續再大體，所以瞎寫幾行，草草交了，抬頭一看，偌大的中心考場，本來一人愛著一人，全部坐滿，現在考場隻剩下十幾個了。。。

滿分100 時間2小時
一.問答題
1.寫出幾個經典的哈希算法，哈希算法的作用是什麼
2.OSI網絡通信協議有哪7層，HTTP協議在哪層運行
3.C語言代碼運行起來的代碼要求和執行過程
二.算法或程序設計題
1. 有一車蘋果，先對其包裝，一個袋子放3個最後剩2個，一個袋子放5個最後剩3個，一個袋子放7個最後剩2個。請找出N個符合這種條件的蘋果個數，寫出該算法（可用偽代碼）
2.用遞歸函數實現求一個字符串相同字符連續的最大個數，如字符串aaabbcc 相同字符連續最多數為3.
3.有一個超過100億個數據元素的數組，按從小到大排序。現將它分為若幹個數組，每個數組的元素少於20個。現把這些數組重新排序，試寫出時間效率最高的算法，並寫出時間複雜度分析。
三.一道很長的數據庫題，數據關係類的。完全不會，所以也記不住了。就記得是一個社交網站，記錄某人配偶，子女，父母，兄弟，朋友這些社會關係，並且假如你是某人的兒子，則你父母的數據將自動生成他們的兒子是…而你的朋友是D，則D的朋友自動生成你的名字…..
定義數據庫……

最後更新：2017-04-03 18:51:55

  上一篇： poj 1613 Cave Raider 最短路

  下一篇： centos 6.3 安裝svn服務端 window客戶端 Linux客戶端應用