1、給一個單詞a，如果通過交換單詞中字母的順序可以得到另外的單詞b，那么b是a的兄弟單詞，比如的單詞army和mary互為兄弟單詞。
現(xiàn)在要給出一種解決方案，對于用戶輸入的單詞，根據(jù)給定的字典找出輸入單詞有哪些兄弟單詞。請具體說明數(shù)據(jù)結構和查詢流程，要求時間和空間效率盡可能地高。
字典樹的典型應用，一般情況下，字典樹的結構都是采用26叉樹進行組織的，每個節(jié)點對應一個字母，查找的時候，就是一個字母一個字母的進行匹配，算法的時間復雜度就是單詞的長度n，效率很高。因此這個題目可以定義一個字典樹作為數(shù)據(jù)結構來查詢的，時間效率會很高，這樣就轉化為在一棵字典樹中查找兄弟單詞，只要在字典樹中的前綴中在存儲一個vector結構的容器，這樣查找起來就是常數(shù)級的時間復雜度了，效率很高的。。
數(shù)據(jù)結構可以定義如下：
- struct word
- {
- vector<string> brother; // 用于保存每個單詞的兄弟單詞
- word *next[26]; // 字典樹中每個節(jié)點代表一個字符，并指向下一個字符
- };
這樣建立完字典樹后，查詢兄弟單詞的效率就會很高了，比哈希的效率還要高；查到tops的兄弟的單詞的時候，首先排序，那么就是opts，然后在字典樹中查找opts，在s處將其vector容器brother中的的單詞輸出就是tops的所有兄弟單詞。
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值，返回對應的所有的key_value對，例如get_log（A,a,i,1,key1），
請描述一種數(shù)據(jù)結構來存儲這些日志，并計算出寫入日志和讀出日志的時間復雜度。
3、C和C++中如何動態(tài)分配和釋放內存？他們的區(qū)別是什么？
malloc/free和new/delete的區(qū)別，請參考這里http://blog.csdn.net/hackbuteer1/article/details/6789164
4、數(shù)組al[0,mid-1]和al[mid,num-1]是各自有序的，對數(shù)組al[0,num-1]的兩個子有序段進行merge，得到al[0,num-1]整體有序。要求空間復雜度為O(1)。注：al[i]元素是支持'<'運算符的。
- /*
- 數(shù)組a[begin, mid] 和 a[mid+1, end]是各自有序的，對兩個子段進行Merge得到a[begin , end]的有序數(shù)組。 要求空間復雜度為O(1)
- 方案：
- 1、兩個有序段位A和B，A在前，B緊接在A后面，找到A的第一個大于B[0]的數(shù)A[i]， A[0...i-1]相當于merge后的有效段，在B中找到第一個大于A[i]的數(shù)B[j]，
- 對數(shù)組A[i...j-1]循環(huán)右移j-k位，使A[i...j-1]數(shù)組的前面部分有序
- 2、如此循環(huán)merge
- 3、循環(huán)右移通過先子段反轉再整體反轉的方式進行，復雜度是O(L), L是需要循環(huán)移動的子段的長度
- */
- #include<iostream>
- using namespace std;
-
- void Reverse(int *a , int begin , int end ) //反轉
- {
- for(; begin < end; begin++ , end--)
- swap(a[begin] , a[end]);
- }
- void RotateRight(int *a , int begin , int end , int k) //循環(huán)右移
- {
- int len = end - begin + 1; //數(shù)組的長度
- k %= len;
- Reverse(a , begin , end - k);
- Reverse(a , end - k + 1 , end);
- Reverse(a , begin , end);
- }
-
- // 將有序數(shù)組a[begin...mid] 和 a[mid+1...end] 進行歸并排序
- void Merge(int *a , int begin , int end )
- {
- int i , j , k;
- i = begin;
- j = 1 + ((begin + end)>>1); //位運算的優(yōu)先級比較低，外面需要加一個括號，剛開始忘記添加括號，導致錯了很多次
- while(i <= end && j <= end && i<j)
- {
- while(i <= end && a[i] < a[j])
- i++;
- k = j; //暫時保存指針j的位置
- while(j <= end && a[j] < a[i])
- j++;
- if(j > k)
- RotateRight(a , i , j-1 , j-k); //數(shù)組a[i...j-1]循環(huán)右移j-k次
- i += (j-k+1); //第一個指針往后移動，因為循環(huán)右移后，數(shù)組a[i....i+j-k]是有序的
- }
- }
-
- void MergeSort(int *a , int begin , int end )
- {
- if(begin == end)
- return ;
- int mid = (begin + end)>>1;
- MergeSort(a , begin , mid); //遞歸地將a[begin...mid] 歸并為有序的數(shù)組
- MergeSort(a , mid+1 , end); //遞歸地將a[mid+1...end] 歸并為有序的數(shù)組
- Merge(a , begin , end); //將有序數(shù)組a[begin...mid] 和 a[mid+1...end] 進行歸并排序
- }
-
- int main(void)
- {
- int n , i , a[20];
- while(cin>>n)
- {
- for(i = 0 ; i < n ; ++i)
- cin>>a[i];
- MergeSort(a , 0 , n - 1);
- for(i = 0 ; i < n ; ++i)
- cout<<a[i]<<" ";
- cout<<endl;
- }
- return 0;
- }
5、線程和進程的區(qū)別及聯(lián)系？如何理解“線程安全”問題？
答案：進程和線程都是由操作系統(tǒng)所體會的程序運行的基本單元，系統(tǒng)利用該基本單元實現(xiàn)系統(tǒng)對應用的并發(fā)性。
1、簡而言之,一個程序至少有一個進程,一個進程至少有一個線程.
2、線程的劃分尺度小于進程，使得多線程程序的并發(fā)性高。
3、另外，進程在執(zhí)行過程中擁有獨立的內存單元，而多個線程共享內存，從而極大地提高了程序的運行效率。
4、線程在執(zhí)行過程中與進程還是有區(qū)別的。每個獨立的線程有一個程序運行的入口、順序執(zhí)行序列和程序的出口。但是線程不能夠獨立執(zhí)行，必須依存在應用程序中，由應用程序提供多個線程執(zhí)行控制。
5、從邏輯角度來看，多線程的意義在于一個應用程序中，有多個執(zhí)行部分可以同時執(zhí)行。但操作系統(tǒng)并沒有將多個線程看做多個獨立的應用，來實現(xiàn)進程的調度和管理以及資源分配。這就是進程和線程的重要區(qū)別。
算法與程序設計一、
網(wǎng)頁爬蟲在抓取網(wǎng)頁時，從指定的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）
請先描述相應的算法，再給出相應的代碼實現(xiàn)。（只需給出判斷方法代碼，無需爬蟲代碼）
兩個單向鏈表的相交問題。算法與程序設計二、
4、有一種結構如下圖所示，它由層的嵌套組成，一個父層中只能包含垂直方向上或者是水平方向上并列的層，例如，層1可以包含2、3、4三個垂直方向上的層，層2可以包含5和6兩個水平方向的層，在空層中可以包含數(shù)據(jù)節(jié)點，所謂的空層是指不包含子層的層，每個空層可以包含若干個數(shù)據(jù)節(jié)點，也可以一個都不包含。
在這種結構上面，我們從垂直方向上劃一條線，我們約定每一個子層中我們只能經(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é)點序列， 可以給出偽代碼實現(xiàn)。
思路：（1）判斷兩個數(shù)所屬的同一層次的相同矩形框的下一層次矩形框是水平排列的還是垂直排列的，垂直排列在能在一條線上，水平排列則不能。
（2）用回溯算法求出所有在一條直線上的字符串，用兩字符串是否在同一直線上進行剪枝操作。
系統(tǒng)設計題
1、相信大家都使用過百度搜索框的suggestion功能，百度搜索框中的suggestion提示功能如何實現(xiàn)？請給出實現(xiàn)思路和主要的數(shù)據(jù)結構、算法。有什么優(yōu)化思路可以使得時間和空間效率最高？
應用字典樹來求前綴和TOP K對熱詞進行統(tǒng)計排序
2、兩個200G大小的文件A和B，AB文件里內容均為無序的一行一個正整數(shù)字（不超過2^63），請設計方案，輸出兩個文件中均出現(xiàn)過的數(shù)字，使用一臺內存不超過16G、磁盤充足的機器。
方案中指明使用java編程時使用到的關鍵工具類，以及為什么?
本站僅提供存儲服務，所有內容均由用戶發(fā)布，如發(fā)現(xiàn)有害或侵權內容，請
點擊舉報。
