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

解析：仔細研讀本題，我們發(fā)現(xiàn)，所謂兄弟單詞就是有相同的字母組成還是有不同的順序的單詞。因此我們可以對所有的單詞做排序（根據(jù)字母表中的順序?qū)ζ渑判颍判蚝蟮慕Y(jié)果作為單詞的唯一“簽名”或者“標志”，例如單詞army和單詞mary的唯一簽名就是“amry”.

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

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

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

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

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

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

解析：多級分類對應(yīng)多級hash_map。

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

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

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

相應(yīng)的測試代碼：

<?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){ //設(shè)置相應(yīng)的值} } $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++中如何動態(tài)分配和釋放內(nèi)存？他們的區(qū)別是什么？

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

解析：c中的動態(tài)分配內(nèi)存相關(guān)的函數(shù)是：malloc()和relloc().對應(yīng)的釋放空間的函數(shù)是free()

c++中動態(tài)分配內(nèi)存相關(guān)的函數(shù)是：new().相應(yīng)的釋放空間的函數(shù)是delete（刪除單個變量空間）和delete[](釋放數(shù)組空間)

相應(yīng)的區(qū)別有：

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

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

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

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

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

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

5.線程和進程的區(qū)別及聯(lián)系？如何理解“線程安全”問題？

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

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

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

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

1.網(wǎng)頁爬蟲在抓取網(wǎng)頁時，從指定的URL站點入口開始爬取這個站點上的所有URL link，抓取到下一級link對應(yīng)的頁面后，同樣對頁面上的link進行抓取從而完成深度遍歷。為簡化問題，我們假設(shè)每個頁面上至多只有一個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？（假設(shè)頁面URL上百億，存儲資源有限，無法用hash方法判斷是否包含相同的URL）請先描述相應(yīng)的算法，再給出相應(yīng)的代碼實現(xiàn)。（只需給出判斷方法代碼，無需爬蟲代碼）

解析：挖掘問題的本質(zhì)，實質(zhì)上是：給定兩個單鏈表，判斷兩個單向鏈表是否相交的問題。至于如何判斷兩個單鏈表相交，網(wǎng)上答案很多。這里不再贅述（如判斷兩個單鏈表的最后一個指針是否相等，或轉(zhuǎn)換為單鏈表是否有環(huán)的問題。 ）

2.有一種結(jié)構(gòu)如下圖所示，它由層的嵌套組成，一個父層中只能包含垂直方向上或者是水平方向上并列的層，例如，層1可以包含2、3、4三個垂直方向上的層，層2可以包含5和6兩個水平方向的層，在空層中可以包含數(shù)據(jù)節(jié)點，所謂的空層是指不包含子層的層，每個空層可以包含若干個數(shù)據(jù)節(jié)點，也可以一個都不包含。

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

（2）給出函數(shù)，輸出所有一條線可以劃中的數(shù)據(jù)節(jié)點序列，

思路：

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

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

1.相信大家都使用過百度搜索框的suggestion功能，百度搜索框中的suggestion提示功能如何實現(xiàn)？請給出實現(xiàn)思路和主要的數(shù)據(jù)結(jié)構(gòu)、算法。有什么優(yōu)化思路可以使得時間和空間效率最高？

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

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

這里是用數(shù)據(jù)庫保存數(shù)據(jù)，而查詢的時候是通過數(shù)據(jù)庫委托的like取相應(yīng)的前綴查詢，因而掩蓋了很多數(shù)據(jù)結(jié)構(gòu)和算法的細節(jié)。

實際應(yīng)用中，每個熱詞可能還有相應(yīng)的計數(shù)或者權(quán)重，根據(jù)權(quán)重選取相應(yīng)的熱詞并取top K進行展示。

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

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

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

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

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