1.給一個單詞a，如果通過交換單詞中字母的順序可以得到另外的單詞b，那么b是a的兄弟單詞，比如單詞army和mary互為兄弟單詞。現在要給出一種解決方案，對于用戶輸入的單詞，根據給定的字典找出輸入單詞有哪些兄弟單詞。請具體說明數據結構和查詢流程，要求時間和空間效率盡可能地高。

解析：仔細研讀本題，我們發現，所謂兄弟單詞就是有相同的字母組成還是有不同的順序的單詞。因此我們可以對所有的單詞做排序（根據字母表中的順序對其排序），排序后的結果作為單詞的唯一“簽名”或者“標志”，例如單詞army和單詞mary的唯一簽名就是“amry”.

如果本題目作為c/c++面試題。那么所用的數據結構可以是“hash_map + 單鏈表”（也可以是hash_map + 二維數組，有些浪費空間，或者是hash_map + list，容器套容器），具體的流程是：對于輸入的單詞列表，先計算單詞的key(排序后的結果)如果key不再hash_map中，那么就將該單詞加入hash_map中。hash——map的key就是單詞的key,value是鏈表（或數組）。如果已經存在該key,那么單詞加入value對應的單鏈表中。查詢一個單詞的所有兄弟單詞的時候就可以簡單滴查詢hash_map，然后掃描相應的單鏈表即可。

另外，字典樹對于求解字符串匹配，前綴，后綴等問題是一個利器。因而本題也可通過字典樹求解。具體的解法可以參考：

http://blog.csdn.net/hackbuteer1/article/details/7542774

本題作為php面試。數據結構可以直接用數組（php中數組真是萬能的數據結構，除了作為普通的數組，還可以做棧，做隊列，做hash_map，實在是太強大了，囧）。

當然思路也是基于單詞排序后的結果。給定一個單詞列表如army,mary,map,pam.則生成的結果數組是這樣的：

$array = array('amry' => array(’army’,’mary’),’amp’=>array(’map’,’pam’));

有了思路，代碼就簡單了：

<?php $dicts = array(’army’, ’mary’, ’are’, ’so’, ’os’, ’test’, ’how’, ’pam’, ’map’,);function getBrother($sea,$needle){//大海撈針 $brother = array(); foreach($sea as $word){$str_array = str_split($word);rsort($str_array);$res = implode(’’,$str_array);//if(!in_array($brother,$res)){ $brother[$res][] = $word;//} } $key_array = str_split($needle); rsort($key_array); $key = implode(’’,$key_array); if(isset($brother[$key])){return $brother[$key]; } return null;}print_r(getBrother($dicts,'map'));

該題目的c++解法可以參考：http://hi.baidu.com/nicker2010/item/295b0e090ac8ddebfe240d84

2.系統中維護了若干數據項，我們對數據項的分類可以分為三級，首先我們按照一級分類方法將數據項分為A、B、C……若干類別，每個一級分類方法產生的類別又可以按照二級分類方法分為a、b、c……若干子類別，同樣，二級分類方法產生的類別又可以按照是三級分類方法分為i、ii、iii……若干子類別，每個三級分類方法產生的子類別中的數據項從1開始編號。我們需要對每個數據項輸出日志，日志的形式是key_value對，寫入日志的時候，用戶提供三級類別名稱、數據項編號和日志的key，共五個key值，例如，write_log（A,a,i,1,key1），獲取日志的時候，用戶提供三級類別名稱、數據項編號，共四個key值，返回對應的所有的key_value對，例如get_log（A,a,i,1,key1），請描述一種數據結構來存儲這些日志，并計算出寫入日志和讀出日志的時間復雜度。

解析：多級分類對應多級hash_map。

作為php面試。多維的map即為一個多維的數組。各維的含義依次是：一級，二級，三級分類，編號，key.

數據存儲形式為：array('A' =>array('a'=>array('i'=>array(1=>array('key1'=>'value1','key2'=>’value2’))),'b'=>array));

查詢的時候根據相應的編號和類別，key直接查詢即可。時間復雜度可以達到O(1).(考慮，如果數據是海量的，應該如何存儲？查詢？)

相應的測試代碼：

<?php class Dictory{private $dict = array( ’class_one_A’ => array(’class_two_a’=>array( ’class_three_i’=>array(1=>array( ’id’=>'test_id', ’name’=>’test’, ’date’=>’2012-07-12’,),2=>array( //..),3=>array( //..), ), ’class_three_ii’=>array( ), ), ’class_two_b’=>array( //... ), ), ’class_one_B’ => array(//... ),//...);public function __construct(){ //也可以在這里傳入dict列表。}public function getItem($class_one,$class_two,$class_three,$num){ $class_one = ’class_one_’.$class_one; $class_two = ’class_two_’.$class_two; $class_three = ’class_three_’.$class_three; $num = intval($num); if(isset($this->dicts[$class_one][$class_two][$class_three][$num])){return $this->dicts[$class_one][$class_two][$class_three][$num]); } return null;}public function setItem($class_one,$class_two,$class_three,$num,$key,$value){ //設置相應的值} } $dict = new Dictory; echo '<pre>'; print_r($dict->getItem(’A’,’a’,’i’,1)); /* * Array * ( * [id] => test_id * [name] => test * [date] => 2012-07-12 * ) */

3.C和C++中如何動態分配和釋放內存？他們的區別是什么？

(不明白為什么php的面試中還有c/c++的基礎題。詭異的很，肯定是有人搞錯了)

解析：c中的動態分配內存相關的函數是：malloc()和relloc().對應的釋放空間的函數是free()

c++中動態分配內存相關的函數是：new().相應的釋放空間的函數是delete（刪除單個變量空間）和delete[](釋放數組空間)

相應的區別有：

相同點：都可用于申請動態內存和釋放內存不同點：(1)操作對象有所不同: malloc 與 free 是 C++/C 語言的標準庫函數，new/delete 是 C++的運算符。對于非內部數據類的對象而言，光用 maloc/free 無法滿足動態對象的要求。對象在創建的同時要自動執行構造函數， 對象消亡之前要自動執行析構函數。由于 malloc/free 是庫函數而不是運算符，不在編譯器控制權限之內，不能夠把執行構造函數和析構函數的任務強加 malloc/free。(2)在用法上也有所不同:函數 malloc 的原型如下： void * malloc(size_t size); 用 malloc 申請一塊長度為 length 的整數類型的內存，程序如下： int *p = (int *) malloc(sizeof(int) * length);我們應當把注意力集中在兩個要素上：“類型轉換”和“sizeof”。 malloc 返回值的類型是 void *，所以在調用 malloc 時要顯式地進行類型轉換，將 void * 轉換成 所需要的指針類型。 malloc 函數本身并不識別要申請的內存是什么類型，它只關心內存的總字節數。函數 free 的原型如下： void free( void * memblock ); 為什么 free 函數不象 malloc 函數那樣復雜呢？這是因為指針p的類型以及它所指的內存的容量事先都是知道的，語句 free(p)能正確地釋放內存。如果 p 是 NULL 指針，那么 free對 p 無論操作多少次都不會出問題。如果p不是NULL 指針，那么 free對p連續操作兩次就會導致程序運行錯誤。new/delete 的使用要點:運算符 new 使用起來要比函數 malloc 簡單得多，例如： int *p1 = (int *)malloc(sizeof(int) * length); int *p2 = new int[length]; 這是因為new內置了sizeof、類型轉換和類型安全檢查功能。對于非內部數據類型的對象而言，new在創建動態對象的同時完成了初始化工作。如果對象有多個構造函數，那么 new 的語句也可以有多種形式。如果用 new 創建對象數組，那么只能使用對象的無參數構造函數。例如 Obj *objects = new Obj[100]; // 創建 100 個動態對象不能寫成 Obj *objects = new Obj[100](1);// 創建 100 個動態對象的同時賦初值 1在用 delete 釋放對象數組時，留意不要丟了符號‘[]’。例如 delete []objects; // 正確的用法delete objects; // 錯誤的用法 后者相當于 delete objects[0]，漏掉了另外 99 個對象。

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

解析：如果只有要求O(1),那么可以簡單的插入排序（從mid開始）。

注意歸并排序是不行的。歸并排序的空間復雜度是O(n)。

題目也可以通過循環移位的方式進行“合并”。

具體的解法也可參考：http://blog.csdn.net/hackbuteer1/article/details/7542774（代碼未經測試）

5.線程和進程的區別及聯系？如何理解“線程安全”問題？

答案：進程和線程都是由操作系統所體會的程序運行的基本單元，系統利用該基本單元實現系統對應用的并發性。1)、簡而言之,一個程序至少有一個進程,一個進程至少有一個線程.2)、進程是資源劃分的最小單位，線程是任務劃分的最小單位。3)、另外，進程在執行過程中擁有獨立的內存單元，而多個線程共享內存（資源），從而極大地提高了程序的運行效率。4)、線程在執行過程中與進程還是有區別的。每個獨立的線程有一個程序運行的入口、順序執行序列和程序的出口。但是線程不能夠獨立執行，必須依存在應用程序中，由應用程序提供多個線程執行控制。5)、從邏輯角度來看，多線程的意義在于一個應用程序中，有多個執行部分可以同時執行。但操作系統并沒有將多個線程看做多個獨立的應用，來實現進程的調度和管理以及資源分配。這就是進程和線程的重要區別。

由于多線程之間共享內存和其他資源，因而就有了一個新的概念：多線程安全。試想，如果多個線程共享同一段代碼，那么同時運行的時候，如果沒有相應的機制（例如鎖機制），就會產生不確定的結果，這就是非線程安全的。因而線程安全就是指多線程之間同步運行的時候不會產生莫名其妙或者不確定的結果（由于多線程執行的順序是不可見和不可預知的），或者，通俗點講，多線程下的線程安全就是多個線程同步工作的情況下，運行的結果和單線程運行的情況下沒有什么區別，大多數情況下，這就是線程安全的。

6.做一個系統來過濾垃圾信息，題目較長，用PHP來編寫，要求消耗內存盡可能少。

解析：參考《集體智慧編程》[下載][購買]中文檔分類一節。

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.有一種結構如下圖所示，它由層的嵌套組成，一個父層中只能包含垂直方向上或者是水平方向上并列的層，例如，層1可以包含2、3、4三個垂直方向上的層，層2可以包含5和6兩個水平方向的層，在空層中可以包含數據節點，所謂的空層是指不包含子層的層，每個空層可以包含若干個數據節點，也可以一個都不包含。

在這種結構上面，我們從垂直方向上劃一條線，我們約定每一個子層中我們只能經過一個數據節點，在這種情況下，每條線可以經過多個數據節點，也可以不經過任何數據節點，例如，線1經過了3、5、8三個數據節點，線2只經過了14個數據節點。（1）給出函數，實現判斷兩個數據節點，是否可能同時被線劃中，給出具體的代碼。

（2）給出函數，輸出所有一條線可以劃中的數據節點序列，

思路：

（1）如果兩個數據節點位于同一個最外層中，那么不能連接（我們約定每一個子層中我們只能經過一個數據節點），然后判斷兩個數所屬的同一層次的相同矩形框的下一層次矩形框是水平排列的還是垂直排列的，垂直排列在能在一條線上，水平排列則不能。

（2）用回溯算法求出所有在一條直線上的字符串，用兩字符串是否在同一直線上進行剪枝操作。（實際上類似于字符串的組合問題）。

1.相信大家都使用過百度搜索框的suggestion功能，百度搜索框中的suggestion提示功能如何實現？請給出實現思路和主要的數據結構、算法。有什么優化思路可以使得時間和空間效率最高？

解析：常見的Ajax提示框的實現是基于字典樹，根據前綴掃出相應的單詞（熱點詞），最后根據top K算法求出前K個熱點詞。并展示給用戶。

參考：http://www.wzsky.net/html/article/php/php2/115202.html

這里是用數據庫保存數據，而查詢的時候是通過數據庫委托的like取相應的前綴查詢，因而掩蓋了很多數據結構和算法的細節。

實際應用中，每個熱詞可能還有相應的計數或者權重，根據權重選取相應的熱詞并取top K進行展示。

2.兩個200G大小的文件A和B，AB文件里內容均為無序的一行一個正整數字（不超過2^63），請設計方案，輸出兩個文件中均出現過的數字，使用一臺內存不超過16G、磁盤充足的機器。

又是海量數據的處理，大型互聯網公司最愛做的面試無非就是這些個問題：top K，求相同，大文件統計ip，統計在線人數。為什么現在硬件大大發展的情況下我們還要談海量數據處理，大概是因為：利用有限的資源處理更多的事情，本身就是一個很有挑戰性的課題。而這些問題，最重要的是思路。關于海量數據的題目，強烈推薦july的這篇文章：

http://blog.csdn.net/v_july_v/article/details/7382693

相信你讀完一定收獲頗豐。

對于本題。由于兩個文件的大小都大大超過了內存的限制。因而不能直接放入內存。可考慮對文件進行hash分為多個小文件（根據每一行的值）。hash的文件由于相同的key都存在一個文件中，因而只需要比較相同的文件中的數字。最后歸并之，得到所有的A文件和B文件中相同的數字。