面试回忆录（一）
第一家面試公司：
滴滴打車（現場面試）
1.項目介紹（之后介紹項目問題）
2.給定一個節點，求這個節點在二叉樹的哪層上
1 //給定節點在哪層上 2 int BitreeLevel(BiNode *root,char key) 3 { 4 if(root != NULL && !found)//一個條件不滿足時就跳出 5 { 6 level++;//層數增加 7 if(root->data == key)//找到后標志 8 found = true; 9 else//沒有找到繼續找當前節點的左孩子或者右孩子 10 { 11 BitreeLevel(root->lchild,key); 12 BitreeLevel(root->rchild,key); 13 if(!found) 14 level--;//沒有發現層數減1 15 //為什么這里層數減1？ 16 //因為開始時層數加1才進入的下一層，即不管下一層是否都空都加1，然后再進入 17 //當沒有找到后，返回 18 } 19 } 20 return level;//返回層數 21 }第二家面試公司
IN我的生活（電話面試）
1.項目介紹（之后介紹項目問題）
2.recv函數返回值的考察
有關recv函數的相關知識：
函數原型：int?recv(?SOCKET?s,?????char?FAR?*buf,??????int?len,?????int?flags?????);???
不論是客戶端還是服務器端應用程序都用recv函數從TCP連接的另一端接收數據。
該函數的：
第一個參數指定接收端套接字描述符；
第二個參數指明一個緩沖區，該緩沖區用來存放recv函數接收到的數據；
第三個參數指明buf的長度；
第四個參數一般置0。
這里只描述同步Socket的recv函數的執行流程。當應用程序調用recv函數時，recv先等待s的發送緩沖?中的數據被協議傳送完畢，如果協議在傳送s的發送緩沖中的數據時出現網絡錯誤，那么recv函數返回SOCKET_ERROR，如果s的發送緩沖中沒有數?據或者數據被協議成功發送完畢后，recv先檢查套接字s的接收緩沖區，如果s接收緩沖區中沒有數據或者協議正在接收數據，那么recv就一直等待，只到?協議把數據接收完畢。當協議把數據接收完畢，recv函數就把s的接收緩沖中的數據copy到buf中（注意協議接收到的數據可能大于buf的長度，所以?在這種情況下要調用幾次recv函數才能把s的接收緩沖中的數據copy完。recv函數僅僅是copy數據，真正的接收數據是協議來完成的），recv函數返回其實際copy的字節數。如果recv在copy時出錯，那么它返回SOCKET_ERROR；如果recv函數在等待協議接收數據時網絡中斷了，那么它返回0。
注意：在Unix系統下，如果recv函數在等待協議接收數據時網絡斷開了，那么調用recv的進程會接收到一個SIGPIPE信號，進程對該信號的默認處理是進程終止。
默認情況下socket是阻塞的。
阻塞與非阻塞recv返回值沒有區別，都是：
<0?出錯
=0?對方調用了close?API來關閉連接
>0?接收到的數據大小，?
特別地：返回值<0時并且(errno?==?EINTR?||?errno?==?EWOULDBLOCK?||?errno?==?EAGAIN)的情況下認為連接是正常的，繼續接收。
只是阻塞模式下recv會一直阻塞直到接收到數據，非阻塞模式下如果沒有數據就會返回，不會阻塞著讀，因此需要循環讀取）。
返回說明：???
（1）成功執行時，返回接收到的字節數。
（2）若另一端已關閉連接則返回0，這種關閉是對方主動且正常的關閉
（3）失敗返回-1，errno被設為以下的某個值???
EAGAIN：套接字已標記為非阻塞，而接收操作被阻塞或者接收超時
EBADF：sock不是有效的描述詞
ECONNREFUSE：遠程主機阻絕網絡連接
EFAULT：內存空間訪問出錯
EINTR：操作被信號中斷
EINVAL：參數無效
ENOMEM：內存不足
ENOTCONN：與面向連接關聯的套接字尚未被連接上
ENOTSOCK：sock索引的不是套接字
3.kmp算法的講解以及編寫
KMP字符串模式匹配通俗點說就是一種在一個字符串中定位另一個串的高效算法。簡單匹配算法的時間復雜度為O(m*n);KMP匹配算法?？梢宰C明它的時間復雜度為O(m+n).。
（1）普通的匹配算法
//暴力樸素的匹配思想 int BFMatch(char* pFather,char* pSOn) {int nFather=strlen(pFather);int nSon=strlen(pSon);int i=0,j;while(i<nFather){j=0;while(pFather[i]==pSon[j]&&j<nSon){i++;j++;}if(j==nSon)return i-nSon;i=i-j+1; //指針i回溯 }return -1; }?KMP算法實現的核心是next數組的計算
第一步：首先，字符串"BBC ABCDAB ABCDABCDABDE"的第一個字符與搜索詞"ABCDABD"的第一個字符，進行比較。因為B與A不匹配，所以搜索詞后移一位。
?
第二步：因為B與A不匹配，搜索詞再往后移。
第三步：以此類推直到找到有一個字符和搜索詞的第一個字符相同為止。
?
第四步：接著比較字符串和搜索詞的下一個字符，還是相同。
第五步：直到字符串有一個字符，與搜索詞對應的字符不相同為止
第六步：普通的BF算法會發生指針的回溯現象，這樣做雖然可行，但是效率很低，因為你要把搜索位置移動到已經比較過的位置上，進行再一次的比較。
第七步：當空格與D不匹配時，你其實已經知道前面六個字符已經是”ABCDAB“。KMP算法的思想是，設法利用這個已知信息，不要把搜索位置移回已經比較過的位置，繼續把它向后移動，這樣來提高效率。
第八步：這是經過getNext函數所獲取的next數組里面的數值，擁有了next數組，那么我們就可以很容易的解決字符串快速匹配問題。所以說KMP最核心的部分就是如何去求next數組。
第九步：已知空格與D不匹配時，前面六個字符"ABCDAB"是匹配的。查表可知，最后一個匹配字符B對應的"部分匹配值"為2，于是子串的指針跳轉到SonID=next[SonID-1];的位置上。SonID=2;于是跳到搜索串C的位置。
第十步：之后因為空格與C也不匹配，搜索詞還要繼續進行跳轉，這次依舊還是根據公式跳轉
SonID=next[SonID-1]；SonID=0;這時候又是空格和A進行比較，依舊不相等。
第十一步：那么父串指針移動到下一位，相同，兩個串的指針就一起移動到下個位置
第十二步：逐位比較，直到搜索詞的最后一位，發現完全匹配，于是搜索完成。如果還要繼續搜索（即找出全部匹配），移動位數 = 7 - 0，再將搜索詞向后移動7位，這里就不再重復了。
第十三步：next數組的計算方法：
"部分匹配值"就是"前綴"和"后綴"的最長的共有元素的長度。以"ABCDABD"為例
－ "A"的前綴和后綴都為空集，共有元素的長度為0；
－ "AB"的前綴為[A]，后綴為[B]，共有元素的長度為0；
－ "ABC"的前綴為[A, AB]，后綴為[BC, C]，共有元素的長度0；
－ "ABCD"的前綴為[A, AB, ABC]，后綴為[BCD, CD, D]，共有元素的長度為0；
－ "ABCDA"的前綴為[A, AB, ABC, ABCD]，后綴為[BCDA, CDA, DA, A]，共有元素為"A"，長度為1；
－ "ABCDAB"的前綴為[A, AB, ABC, ABCD, ABCDA]，后綴為[BCDAB, CDAB, DAB, AB, B]，共有元素為"AB"，長度為2；
－ "ABCDABD"的前綴為[A, AB, ABC, ABCD, ABCDA, ABCDAB]，后綴為[BCDABD, CDABD, DABD, ABD, BD, D]，共有元素的長度為0。
?代碼如下：
1 #include <iostream> 2 #include <string.h> 3 using namespace std; 4 void GetNext(char pStr[],int next[],int length) 5 { 6 if(pStr==NULL||next==NULL||length<=0) return; 7 int nLength=strlen(pStr); 8 next[0]=0; 9 for(int iValue=0,nld=1;nld<nLength;nld++) 10 { 11 while(iValue>0&&pStr[iValue]!=pStr[nld]) iValue=next[iValue-1]; 12 if(pStr[iValue]==pStr[nld]) 13 { 14 iValue++; 15 } 16 next[nld]=iValue; 17 } 18 } 19 //尋找子串中在父串中的首次出現的位置 20 int kmp(char* pSubStr,char* pStr,int next[]) 21 { 22 if(pSubStr==NULL||pStr==NULL||next==NULL) return; 23 int SubLength=strlen(pSubStr),SonLength=strlen(pStr); 24 GetNext(pStr,next,SonLength); 25 for(int SubID=0,SonID=0;SubID<SubLength;SubID++) 26 { 27 while(SonID>0&&pSubStr[SubID]!=pStr[SonID]) SonID=next[SonID-1]; 28 if(pStr[SonID]==pSubStr[SubID]) 29 { 30 SonID++; 31 } 32 if(SonID==SonLength) 33 return SubID-SonLength+1; 34 } 35 return -1; 36 } 37 int main() 38 { 39 //agctagcagctagctg 40 char Str[]="abcadcdfbcabca"; 41 char SonStr[]="cdf"; 42 int nlength=strlen(Str); 43 int next[100]; 44 //memset(next,0,sizeof(next)); 45 GetNext(Str,next,nlength); 46 cout<<kmp(Str,SonStr,next)<<endl; 47 system("pause"); 48 return 0; 49 }?轉載一些大神們寫的有關KMP相關文章：
http://www.ruanyifeng.com/blog/2013/05/Knuth%E2%80%93Morris%E2%80%93Pratt_algorithm.html
http://www.cnblogs.com/yjiyjige/p/3263858.html
http://blog.chinaunix.net/uid-27164517-id-3280128.html
第三家面試公司
58集團（現場面試）
一面：
1.自我介紹
2.項目介紹（之后會介紹）
3.工廠模式，單例模式，策略模式
這里我推薦大家看一個鏈接對于設計模式描述的很好：
?http://www.jellythink.com/archives/878
二面：
1.自我介紹
2.多路復用I/O的考察:select，poll和epoll
如果說項目中存在網絡編程一般會考到，所以挺重要的，這塊知識點可深可淺，為什么說深，如果你很熟練的話，那么就聊一下各個模型是怎么運作的，聊聊epoll的底層實現（紅黑樹、回調機制和消息鏈表）為什么說淺，是時候該背背了。
會考察的題目一：select和epoll的區別
??［1］select但進程只能打開1024個套接字［ulimit?-a可以查詢],epoll可以處理百萬巨柄
??［2］select只能處理可讀可寫及異常事件，epoll可以處理跟多類型的事件
??［3］每一次調用select時都會進行一次內核態和用戶態的拷貝，都需要重新填充待檢測集合
??［4］select返回的事件集合［就緒和為就緒的］，采用輪詢的方式來檢測就緒事件，時間復雜度O（n）
??［5］select采用LT處理模式，epoll有ET和EPOLLONESHOT［這兩事件處理看書Linux高性能服務器編程］
??［6］epoll采用回調的方式，內核檢測到就緒文件描述符，觸發回調函數［將文件描述符上對應的事件插入內核就緒事件隊列
??????,內核在合適的時候將就緒事件隊列中的內容拷貝到用戶空間］事件復雜度O（1）
???[7]epoll_wait返回到套接字都有事件
???[8]epoll_wait未必高效，活動連接較多，回調函數被觸發得過于頻繁［不好］,epoll_wait適用于連接數量多，但活動連接數較少的情況
建議擴展著說，不要給人感覺你是背的感覺。
會考察的題目二：select、poll1和epoll的區別
?
（1）select，poll實現需要自己不斷輪詢所有fd集合，直到設備就緒，期間可能要睡眠和喚醒多次交替。而epoll其實也需要調用epoll_wait不斷輪詢就緒鏈表，期間也可能多次睡眠和喚醒交替，但是它是設備就緒時，調用回調函數，把就緒fd放入就緒鏈表中，并喚醒在epoll_wait中進入睡眠的進程。雖然都要睡眠和交替，但是select和poll在“醒著”的時候要遍歷整個fd集合，而epoll在“醒著”的時候只要判斷一下就緒鏈表是否為空就行了，這節省了大量的CPU時間。這就是回調機制帶來的性能提升。
（2）select，poll每次調用都要把fd集合從用戶態往內核態拷貝一次，并且要把current往設備等待隊列中掛一次，而epoll只要一次拷貝，而且把current往等待隊列上掛也只掛一次（在epoll_wait的開始，注意這里的等待隊列并不是設備等待隊列，只是一個epoll內部定義的等待隊列）。這也能節省不少的開銷。
3.內存泄露問題：
http://blog.csdn.net/na_he/article/details/7429171
http://www.cnblogs.com/xitang/p/3645043.html
http://blog.csdn.net/zdy0_2004/article/details/50254283
4.大數據問題
問題描述：
有一個動物園，存在著一百萬個動物，其中獅子是唯一的，其他種類動物每種兩只，問如何找到這只唯一的獅子在哪？
?解答：把每一個動物看做一個數的話，那么同種類的動物就是同一個數，我們根據兩個相同的數抑或等于零，零任何數抑或都等于那個數的方式來確定那個唯一的值，
這樣我們給動物們進行編號，進行每每抑或，那么最后就可以得出相應的動物了。
?
?
?
轉載于:https://www.cnblogs.com/famousli/p/5968206.html
總結
- 上一篇： 前端特效集
- 下一篇： 【数据结构复习】（1）绪论