內(nèi)推字節(jié) Linux C/C++ 開(kāi)發(fā)的那位同學(xué)沒(méi)通過(guò)面試......

最近同事內(nèi)推了一位 Linux C/C++ 后端開(kāi)發(fā)的同學(xué)到我們公司面試，我是一面的面試官，很遺憾這位工作了兩年的同學(xué)面試表現(xiàn)不是很好。

我問(wèn)了如下一些問(wèn)題：

“Redis 持久化機(jī)制，redis 銷毀方式機(jī)制，MQ 實(shí)現(xiàn)原理，C++ 虛函數(shù)，hash 沖突的解決，memcached 一致性哈希，socket 函數(shù)、select/poll/epoll模型，同步互斥，異步非阻塞，回調(diào)的概念，innodb索引原理，單向圖最短路徑，動(dòng)態(tài)規(guī)劃算法?！?/span>

為了幫助更多的同學(xué)拿到滿意的 offer，我整理了一下發(fā)出來(lái)，那么 Linux C/C++ 崗位一般會(huì)問(wèn)哪些知識(shí)點(diǎn)呢？

C++ 面試一般考察的內(nèi)容

1. 語(yǔ)言基礎(chǔ)

C++ 虛函數(shù)這是面試初、中級(jí) C++ 職位一個(gè)概率 95% 以上的面試題。一般有以下幾種問(wèn)法：

1.在有繼承關(guān)系的父子類中，構(gòu)建和析構(gòu)一個(gè)子類對(duì)象時(shí)，父子構(gòu)造函數(shù)和析構(gòu)函數(shù)的執(zhí)行順序分別是怎樣的？

2.在有繼承關(guān)系的類體系中，父類的構(gòu)造函數(shù)和析構(gòu)函數(shù)一定要申明為 virtual 嗎？如果不申明為 virtual 會(huì)怎樣？

3.什么是 C++ 多態(tài)？C++ 多態(tài)的實(shí)現(xiàn)原理是什么？

4.什么是虛函數(shù)？虛函數(shù)的實(shí)現(xiàn)原理是什么？

5.什么是虛表？虛表的內(nèi)存結(jié)構(gòu)布局如何？虛表的第一項(xiàng)（或第二項(xiàng)）是什么？

6.菱形繼承（類 D 同時(shí)繼承 B 和 C，B 和 C又繼承自A）體系下，虛表在各個(gè)類中的布局如何？如果類B和類C同時(shí)有一個(gè)成員變了m，m如何在D對(duì)象的內(nèi)存地址上分布的？是否會(huì)相互覆蓋？

另外，時(shí)至今日，你一定要熟悉 C++11/14/17 常用的語(yǔ)言特性和類庫(kù)，這里簡(jiǎn)單地列一下：

• 統(tǒng)一的類成員初始化語(yǔ)法與 std::initializer_list

• 注解標(biāo)簽（attributes）

• final/override/=default/=delete 語(yǔ)法

• auto 關(guān)鍵字

• Range-based 循環(huán)語(yǔ)法

• 結(jié)構(gòu)化綁定

• stl 容器新增的實(shí)用方法

• std::thread

• 線程局部存儲(chǔ) thread_local

• 線程同步原語(yǔ) std::mutex、std::condition_variable 等

• 原子操作類

• 智能指針類

• std::bind/std::function

C++11/14 網(wǎng)上的資料已經(jīng)很多了，C++17 的資料不多，重頭戲還是 C++11 引入的各種實(shí)用特性，這就給讀者推薦一本我讀過(guò)的：

• 《深入理解 C++11：C++11 新特性解析與應(yīng)用》

• 《深入應(yīng)用 C++11：代碼優(yōu)化與工程級(jí)應(yīng)用》

• 《C++17 完全指南》

• 《Cpp 17 in Detail》

這里網(wǎng)絡(luò)上也有人分享出來(lái)，下載鏈接：

鏈接: https://pan.baidu.com/s/1Af_6-bkugcTFljpIoeIk7Q 密碼: mltg

建議購(gòu)買正版哦。

C++11/14/17 的語(yǔ)法雖然很實(shí)用，但是需要一定的練習(xí)才能掌握，推薦幾個(gè)學(xué)習(xí) C++11/14/17 的開(kāi)源項(xiàng)目：

1. filezilla

filezilla 是一款開(kāi)源的 FTP 軟件，其源碼下載地址如下：

https://svn.filezilla-project.org/svn/FileZilla3/trunk

需要使用 svn 工具來(lái)下載，安裝好 svn 工具后，在 svn 界面中 checkout 上述地址或者使用如下命令下載：

svn co https://svn.filezilla-project.org/svn/FileZilla3/trunk filezilla

如果使用 svn 圖形化工具，直接使用以下 svn 地址將源碼 checkout 到指定目錄即可：

https://svn.filezilla-project.org/svn/FileZilla3/trunk

如果你不知道怎么下載，可以直接在“高性能服務(wù)器開(kāi)發(fā)”公眾號(hào)回復(fù)“獲取Filezilla源碼”進(jìn)行下載。

2. uWebSocket 網(wǎng)絡(luò)庫(kù)

uWebSocket 是一款開(kāi)源的 WebSocket 庫(kù)，最新版使用了大量 C++17 的語(yǔ)法，美中不足的是這個(gè)庫(kù)代碼存在不少 bug，我在項(xiàng)目中使用了它，但修改了其大量的 bug，有興趣的朋友也可以下載下來(lái)看一下：

下載地址：

https://github.com/uNetworking/uWebSockets

3. TeamTalk 的 PC 端

TeamTalk 是蘑菇街開(kāi)源的一款用于企業(yè)內(nèi)部的即時(shí)通信工具，其下載地址是：

https://github.com/balloonwj/TeamTalk/tree/master/win-client

4. 最后是我的開(kāi)源 Flamingo IM

https://github.com/balloonwj/flamingo balloonwj/flamingo

2. 算法與數(shù)據(jù)結(jié)構(gòu)基礎(chǔ)

說(shuō)到算法和數(shù)據(jù)結(jié)構(gòu)，對(duì)于社招人士和對(duì)于應(yīng)屆生一般是不一樣的，對(duì)于大的互聯(lián)網(wǎng)公司和一般的小的企業(yè)也是不一樣的。下面根據(jù)我當(dāng)面試官面試別人和找工作被別人面試經(jīng)驗(yàn)來(lái)談一談。

先說(shuō)考察的內(nèi)容，除了一些特殊的崗位，常見(jiàn)的算法和數(shù)據(jù)結(jié)構(gòu)面試問(wèn)題有如下：

1.排序（?？嫉呐判虬搭l率考排序?yàn)椋嚎焖倥判?> 冒泡排序 > 歸并排序 > 桶排序）

一般對(duì)于對(duì)算法基礎(chǔ)有要求的公司，如果你是應(yīng)屆生或者工作經(jīng)驗(yàn)在一至三年內(nèi)，以上算法如果寫(xiě)不出來(lái)，給面試官的影響會(huì)非常不好，甚至直接被 pass 掉。對(duì)于工作三年以上的社會(huì)人士，如果寫(xiě)不出來(lái)，但是能分析出其算法復(fù)雜度、最好和最壞的情況下的復(fù)雜度，說(shuō)出算法大致原理，在多數(shù)面試官面前也可以過(guò)的。注意，如果你是學(xué)生，寫(xiě)不出來(lái)或者寫(xiě)的不對(duì)，基本上面試過(guò)不了。

1.二分查找

二分查找的算法盡量要求寫(xiě)出來(lái)。當(dāng)然，大多數(shù)面試官并不會(huì)直接問(wèn)你二分查找，而是結(jié)合具體的場(chǎng)景，例如如何求一個(gè)數(shù)的平方根，這個(gè)時(shí)候你要能想到是二分查找。我在2017年年底，面試agora時(shí)，面試官問(wèn)了一個(gè)問(wèn)題：如何從所有很多的ip地址中快速找個(gè)某個(gè)ip地址。

2.鏈表

無(wú)論是應(yīng)屆生還是工作年限不長(zhǎng)的社會(huì)人士，璉表常見(jiàn)的操作一定要熟練寫(xiě)出來(lái)，如鏈表的查找、定位、反轉(zhuǎn)、連接等等。還有一些經(jīng)典的問(wèn)題也經(jīng)常被問(wèn)到，如兩個(gè)鏈表如何判斷有環(huán)（我在2017年面試餓了么二面、上海黃金交易所一面被問(wèn)過(guò)）。鏈表的問(wèn)題一般不難，但是鏈表的問(wèn)題存在非常多的“坑”，如很多人不注意邊界檢查、空鏈表、返回一個(gè)鏈表的函數(shù)應(yīng)該返回鏈表的頭指針等等。

3.隊(duì)列與棧

對(duì)于應(yīng)屆生來(lái)說(shuō)一般這一類問(wèn)的比較少，但是對(duì)于社會(huì)人士尤其是中高級(jí)崗位開(kāi)發(fā)，會(huì)結(jié)合相關(guān)的問(wèn)題問(wèn)的比較多，例如讓面試者利用隊(duì)列寫(xiě)一個(gè)多線程下的生產(chǎn)者和消費(fèi)者程序，全面考察的多線程的資源同步與競(jìng)態(tài)問(wèn)題（下文介紹多線程面試題時(shí)詳細(xì)地介紹）。棧一般對(duì)于基礎(chǔ)要求高的面試，會(huì)結(jié)合函數(shù)調(diào)用實(shí)現(xiàn)來(lái)問(wèn)。即函數(shù)如何實(shí)現(xiàn)的，包括函數(shù)的調(diào)用的幾種常見(jiàn)調(diào)用方式、參數(shù)的入棧順序、內(nèi)存棧在地址從高向低擴(kuò)展、棧幀指針和棧頂指針的位置、函數(shù)內(nèi)局部變量在棧中的內(nèi)存分布、函數(shù)調(diào)用結(jié)束后，調(diào)用者和被調(diào)用者誰(shuí)和如何清理?xiàng)５鹊?。某年面試京東一基礎(chǔ)部門，面試官讓寫(xiě)從0加到100這樣一個(gè)求和算法，然后寫(xiě)其匯編代碼。

4.哈希表

哈希表是考察最多的數(shù)據(jù)結(jié)構(gòu)之一。常見(jiàn)的問(wèn)題有哈希沖突的檢測(cè)、讓面試者寫(xiě)一個(gè)哈希插入函數(shù)等等?；旧弦粓?chǎng)面試下來(lái)不考察紅黑樹(shù)基本上就會(huì)問(wèn)哈希表，而且問(wèn)題可淺可深。我印象比較深刻的是，當(dāng)年面試百度廣告推薦部門時(shí)，二面問(wèn)的一些關(guān)于哈希表的問(wèn)題。當(dāng)時(shí)面試官時(shí)先問(wèn)的鏈表，接著問(wèn)的哈希沖突的解決方案，后來(lái)讓寫(xiě)一個(gè)哈希插入算法，這里需要注意的是，你的算法中插入的元素一定要是通用元素，所以對(duì)于 C++ 或者 Java 語(yǔ)言，一定要使用模板這一類參數(shù)作為哈希插入算法的對(duì)象。然后，就是哈希表中多個(gè)元素沖突時(shí)，某個(gè)位置的元素使用鏈表往后穿成一串的方案。最終考察 linux 下 malloc（下面的ptmalloc） 函數(shù)在頻繁調(diào)用造成的內(nèi)存碎片問(wèn)題，以及開(kāi)源方案解決方案 tcmalloc 和 jemalloc?？傮w下來(lái)，面試官是一步步引導(dǎo)你深入。（有興趣的讀者可以自行搜索，網(wǎng)上有很多相關(guān)資料）

5.樹(shù)

面試高頻的樹(shù)是紅黑樹(shù)，也有一部分是B樹(shù)（B+樹(shù)）。紅黑樹(shù)一般的問(wèn)的深淺不一，大多數(shù)面試官只要能說(shuō)出紅黑樹(shù)的概念、左旋右旋的方式、分析出查找和插入的平均算法復(fù)雜度和最好最壞時(shí)的算法復(fù)雜度，并不要寫(xiě)面試者寫(xiě)出具體代碼實(shí)現(xiàn)。一般 C++ 面試問(wèn) stl 的map，java 面試問(wèn) TreeMap 基本上就等于開(kāi)始問(wèn)你紅黑樹(shù)了，要有心里準(zhǔn)備。筆者曾經(jīng)面試愛(ài)奇藝被問(wèn)過(guò)紅黑樹(shù)。B樹(shù)一般不會(huì)直接問(wèn)，問(wèn)的最多的形式是通過(guò)問(wèn) MySQL 索引實(shí)現(xiàn)原理（數(shù)據(jù)庫(kù)知識(shí)點(diǎn)將在下文中討論）。筆者面試騰訊看點(diǎn)部門二面被問(wèn)到過(guò)。

6.圖

圖的問(wèn)題就我個(gè)人面試從來(lái)沒(méi)遇到過(guò)，不過(guò)據(jù)我某位哥哥所說(shuō)，他在進(jìn)三星電子之前有一道面試題就是深度優(yōu)先和廣度優(yōu)先問(wèn)題。

7.其他的一些算法

如 A*尋路、霍夫曼編碼也偶爾會(huì)在某一個(gè)領(lǐng)域的公司的面試中被問(wèn)到。

3. 編碼基本功

還有一類面試題不好分類，筆者姑且將其當(dāng)作是考察編碼基本功，這類問(wèn)題既可以考察算法也可以考察你寫(xiě)代碼基本素養(yǎng)，這些素養(yǎng)不僅包括編碼風(fēng)格、計(jì)算機(jī)英語(yǔ)水平、調(diào)試能力等，還包括你對(duì)細(xì)節(jié)的掌握和易錯(cuò)點(diǎn)理解，如有意識(shí)地對(duì)邊界條件的檢查和非法值的過(guò)濾。請(qǐng)讀者看以下的代碼執(zhí)行結(jié)果是什么？

for(char i = 0; i < 256; ++i) {  printf("%d\n", i);
} 

strcpy(dest3, strcpy(dest2, strcpy(dest1, src1)));

int atoi(const char* p);