2012百度實習招聘簡答題 算法設計

1、給一個單詞a，如果通過交換單詞中字母的順序可以得到另外的單詞b，那麼b是a的兄弟單詞，比如單詞army和mary互為兄弟單詞。

現在要給出一種解決方案，通過使用者輸入的單詞，根據給定的字典找出輸入單詞有哪些兄弟單詞。請具體說明資料結構和查詢流程，要求時間和空間效率盡可能地提高。

2、線程和程序的差別及聯系？如何了解“線程安全”問題？

3、C和C++中如何動态配置設定和釋放記憶體？他們的差別是什麼？

1、網頁爬蟲在抓取頁面時，從指定的url站點入口開始爬取這個站點上的所有url link，抓取到下一級link對應的頁面後，同樣對該頁面上的link進行抓取進而完成深度周遊。為簡化問題，我們假設每個頁面上至多隻有一個 link，如從www.baidu.com/a.html連結到www.baidu.com/b.html再連結到www.baidu.com /x.html，當爬蟲抓取到某個頁面時，有可能再連結回www.baidu.com/b.html，也可能爬取到一個不帶任何link的終極頁面。當抓 取到相同的url或者不包含任何link的終極頁面時即完成爬取。爬蟲在抓取到這些頁面後會建立一個單向連結清單，用來記錄抓取到的頁面。 如：a.html->b.html->x.html...->NULL.

問：對于爬蟲分别從www.baidu.com/x1.html和www.baidu.com/x2.html兩個入口開始獲得兩個單向連結清單，得到這兩個 單向連結清單後，如何判斷他們是否抓取到了相同的url？（假設頁面url上百億，存儲資源受限，無法用hash方法判斷其是否包含相同的url）

請先描述相應的算法，再給出相應的代碼實作。（隻需給出判斷方法代碼，無需爬蟲代碼）

2、數組al[0,mid-1]和al[mid,num-1]是各自有序的，對數組al[0,num-1]的兩個子有序段進行merge，得到al[0,num-1]整體有序。要求空間複雜度為O(1)。注：al[i]元素是支援'<'運算符的。

系統設計

兩個200G大小的檔案A和B，AB檔案裡内容均為無序的一行一個正整數字（不超過2^63），請設計方案，輸出兩個檔案中均出現過的數字，使用一台記憶體不超過16G、磁盤充足的機器。

方案中指明使用java程式設計時使用到的關鍵工具類，以及為什麼?

來源：http://blog.csdn.net/mishifangxiangdefeng/article/details/8018629

本文轉自夏雪冬日部落格園部落格，原文連結：http://www.cnblogs.com/heyonggang/archive/2013/03/28/2986843.html，如需轉載請自行聯系原作者