百度面試題及答案

1、百度技術(shù)研發(fā)筆試題目/* 百度面試題*有一根 27厘米的細木桿，在第 3厘米、 7厘米、 11厘米、 17厘米、 23厘米 這五個 位置上各有一只螞蟻。* 木桿很細，不能同時通過一只螞蟻。開始時，螞蟻的頭朝左還是朝右是任意的，它們只會朝前走或調(diào)頭，* 但不會后退。當任意兩只螞蟻碰頭時，兩只螞蟻會同時調(diào)頭朝反方向走。假設(shè)螞蟻們每秒鐘可以走一厘米的距離。*編寫程序，求所有螞蟻都離開木桿的最小時間和最大時間。*分析: 題目中的螞蟻只可能相遇在整數(shù)點，不可以相遇在其它點，比如3.5cm 處 之類的，也就是可以讓每只螞蟻走 1 秒，然后* 查看是否有相遇的即可 .*這樣我的程序?qū)崿F(xiàn)思路就是，初始化 5

2、只螞蟻，讓每只螞蟻走 1 秒，然后看是否 有 相遇的 ,如果有則做相應處理 . 當每只螞蟻都*走出木桿時，我就記錄當前時間 . 這樣就可以得到當前狀態(tài)情況下，需要多久可以走出木桿 , 然后遍歷所有狀態(tài)則可以得到所胡*可能.*/package baidu;public class Ant (step 表示螞蟻每一個單位時間所走的長度*/ private final static int step = 1;/1* position 表示螞蟻所處的初始位置*/private int position;/*1,異常* direction 表示螞蟻的前進方向，如果為 1 表示向 27 厘米的方向走，如果

3、為 則表示往 0 的方向走。*/private int direction = 1;/*此函數(shù)運行一次，表示螞蟻前進一個單位時間，如果已經(jīng)走下木桿則會拋出*/public void walk() (if(isOut() (throw new RuntimeException("the ant is out");position = position + this.direction * step;；public boolean isOut() (return position <= 0 II position >= 27;1檢查螞蟻是否已經(jīng)走出木桿，如果走出返回

4、true*/2檢查此螞蟻是否已經(jīng)遇到另外一只螞蟻* param ant* ?return 如果遇到返回 true*/public boolean isEncounter(Ant ant) (return ant.position = this.position;/*改變螞蟻的前進方向*/public void changeDistation() (direction = -1 3 direction;1. 這樣可以方this.direction = -1;方向設(shè)置初始位置 ,比如為 0時, 也將其設(shè)置為 便后面的處理 else (this.direction = 1; llllllllllll

5、lllllllllllllllllllllllllllllllllllllllllllll*/public Ant(int position, int direction) ( this.position = position;if (direction != 1) (3構(gòu)造函數(shù)，設(shè)置螞蟻的初始前進方向，和初始位置* param position* param directionpackage baidu;public class Controller (public static void main(String args) (int time = 0;for (int i = 0; i &

6、lt; 32; i+) (Ant antArray = getAntList(getPoistions(), getDirections(i);while (!isA110ut(antArray) (for (Ant ant: antArray) (if (!ant.isOut() (ant.walk();time+;System.out.println(time);/ 將時間歸 0,這樣可以重新設(shè)置條件 , 再次得到全部走完所需要的時間 time = 0;/*這個函數(shù)的算法很亂，但暫時能解決問題* param list*/public static void dealEncounter(An

7、t antArray) (int num_ant = antArray.length;for (int j = 0; j < num_ant; j+) (for (int k = j + 1; k < num_ant; k+) (if (antArrayj .isEncounter(antArrayk) ( antArrayj .changeDistation(); antArray k .changeDistation();則表示 Ant 往 0的方向走 如果為 1,則表示往 27的方向走* 注: 在通過 Ant 的構(gòu)造函數(shù)設(shè)置初始值時，通過過濾把 0 修改成了 -1. */pu

8、blic static int getDirections(int seed) (int result = new int5;resultO = seed % 2;resultl = seed / 2 % 2;result2 = seed / 4 % 2;result3 = seed / 8 % 2;result4 = seed / 16 % 2;System.out.println("directions is " + result0 + 'T' + resultl + T + result2 + T + result3 + T + result4);re

9、turn result;/*批量設(shè)置 Ant 的初始位置，這樣設(shè)置不是十分必要，可以直接在代碼中設(shè)置* ?return*/public static int getPoistions() (return new int ( 3, 7, 11, 17, 23 );取得設(shè)置好初始值的 5只 Ant* param positions* param directions* ?return*/public static Ant getAntList(int positions, int directions) (Ant ant3 = new Ant(positions0, directions 0);A

10、nt ant7 = new Ant(positionsl, directionsl);Ant antll = new Ant(positions2, directions2);Ant ant 17 = new Ant(positions3, directions3);Ant ant23 = new Ant(positions4, directions 4);return new Ant ( ant3, ant7, antll, antl7, ant23 );/*判斷是否所有的 Ant 都已經(jīng)走出了木桿 , 也就是設(shè)置退出條件* param antArray* ?return*/public s

11、tatic boolean isA110ut(Ant antArray) (for (Ant ant: antArray) ( if (ant.isOut() = false) ( return false;return true;編程：用C語言實現(xiàn)一個revert函數(shù)，它的功能是將輸入的字符串在原串上倒序后返回2 編程：用 C 語言實現(xiàn)函數(shù) void * memmove （void *dest, const void *src, size_t n）。 memmove函數(shù)的功能是拷貝src所指的內(nèi)存內(nèi)容前n個字節(jié)到dest所指的地址上。3英文拼寫糾錯：在用戶輸入英文單詞時，經(jīng)常發(fā)生錯誤，我們需

12、要對其進行糾錯。假設(shè)已經(jīng)有一 個包含了正確英文單詞的詞典，請你設(shè)計一個拼寫糾錯的程序。（1）請描述你解決這個問題的思路；（2）請給出主要的處理流程，算法，以及算法的復雜度；（3）請描述可能的改進（改進的方向如效果，性能等等，這是一個開放問 題）詢串4 尋找熱門查詢： 搜索引擎會通過日志文件把用戶每次檢索使用的所有檢索串都記錄下來，每個查 的長度為 1 -255 字節(jié)。假設(shè)目前有一千萬個記錄， 這些查詢串的重復度比較高，雖然總數(shù)是 1 千萬，但如果除去重復后，不超過 3 百萬個。一個查詢串的重復度越高，說明查詢它的用戶越多， 也就是越熱門。請你統(tǒng)計最熱門的 10 個查詢串，要求使用的內(nèi)存不能超過

13、 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) 請描述可能的改進 ( 改進的方向如效果，性能等等，這是一個開放問題)。/I1題char *reve

14、rt(char * str)int n=strlen(str);int i=0;char c; for(i=0;i c=str;str=strn-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 N;I+) *temp+=*ss+;return temp;/3題 思路： 字典以字母鍵

15、樹組織，在用戶輸入同時匹配 流程 : 每輸入一個字母： 沿字典樹向下一層，a) 若可以順利下行，則繼續(xù)至結(jié)束，給出結(jié)果；b) 若該處不能匹配，糾錯處理，給出拼寫建議，繼續(xù)至a)；算法：1. 在字典中查找單詞字典采用 27 叉樹組織，每個節(jié)點對應一個字母，查找就是一個字母 一個字母匹配 . 算法時間就是單詞的長度 k.可能以有2. 糾錯算法 情況：當輸入的最后一個字母不能匹配時就提示出錯，簡化出錯處理，動態(tài)提示 處理方法：(a) 當前字母前缺少了一個字母：搜索樹上兩層到當前的匹配作為建議；(b) 當前字母拼寫錯誤：當前字母的鍵盤相鄰作為提示； ( 只是簡單的描述，可 更多的 )根據(jù)分析字典特征和

16、用戶單詞已輸入部分選擇(a), (b)處理復雜性分析：影響算法的效率主要是字典的實現(xiàn)與糾錯處理(a)字典的實現(xiàn)已有成熟的算法，改進不大，也不會成為瓶頸；(b)糾錯策略要簡單有效，如前述情況，是線性復雜度；(3) 改進策略選擇最是重要，可以采用統(tǒng)計學習的方法改進。/4題思路：用哈希做(2)首先逐次讀入查詢串，算哈希值，保存在內(nèi)存數(shù)組中，同時統(tǒng)計頻度( 注意值與日志項對應關(guān)系 )選出前十的頻度，取出對應的日志串，簡單不過了哈希的設(shè)計是關(guān)鍵。/5題(1) 思路: 先將集合按照大小排列后，優(yōu)先考慮小的集合是否與大的集合有交集。有就合并，如果小集合與所有其他集合都沒有交集，則獨立。獨立的集合在下一輪 的

17、比 較中不用考慮。這樣就可以盡量減少字符串的比較次數(shù)。當所有集合都獨立的時 候，就終止。(2) 處理流程：1. 將集合按照大小排序，組成集合合并待處理列表2. 選擇最小的集合，找出與之有交集的集合，如果有，合并之； 如果無，則與其它集合是獨立集合，從待處理列表中刪除。3. 重復直到待處理列表為空算法： 1。將集合按照大小從小到大排序，組成待處理的集合列表。2o 取出待處理集合列表中最小的集合，對于集合的每個元素，依次在其他集合 中搜索 是否有此元素存在：1若存在，則將此小集合與大集合合并，并根據(jù)大小插入對應的位置。轉(zhuǎn)3O2若不存在，則在該集合中取下一個元素。如果無下一個元素，即所有元素都不存在于其他集合。則表明此集合獨立，從待處理集合列表中刪除。并加入結(jié)果集合列表。轉(zhuǎn) 3。3o 如果待處理集合列表不為空，轉(zhuǎn) 2。 如果待處理集合列表為空，成功退出，則結(jié)果集合列表就是最終的輸出。算法復雜度分析：假設(shè)集合的個數(shù)為n,最大的集合元素為m排序的時間復雜度可以達到 n*log(n) 然后對于元素在其他集合中查找，最壞情況下為 (n-1) *m