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

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

我問了如下一些問題：

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

為了幫助更多的同學(xué)拿到滿意的 offer，我整理了一下發(fā)出來，那么 Linux C/C++ 崗位一般會問哪些知識點呢？

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

1. 語言基礎(chǔ)

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

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

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

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

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

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

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

另外，時至今日，你一定要熟悉 C++11/14/17 常用的語言特性和類庫，這里簡單地列一下：

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

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

• final/override/=default/=delete 語法

• auto 關(guān)鍵字

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

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

• stl 容器新增的實用方法

• std::thread

• 線程局部存儲 thread_local

• 線程同步原語 std::mutex、std::condition_variable 等

• 原子操作類

• 智能指針類

• std::bind/std::function

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

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

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

• 《C++17 完全指南》

• 《Cpp 17 in Detail》

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

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

建議購買正版哦。

C++11/14/17 的語法雖然很實用，但是需要一定的練習(xí)才能掌握，推薦幾個學(xué)習(xí) C++11/14/17 的開源項目：

1. filezilla

filezilla 是一款開源的 FTP 軟件，其源碼下載地址如下：

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

需要使用 svn 工具來下載，安裝好 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ù)器開發(fā)”公眾號回復(fù)“獲取Filezilla源碼”進(jìn)行下載。

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

uWebSocket 是一款開源的 WebSocket 庫，最新版使用了大量 C++17 的語法，美中不足的是這個庫代碼存在不少 bug，我在項目中使用了它，但修改了其大量的 bug，有興趣的朋友也可以下載下來看一下：

下載地址：

https://github.com/uNetworking/uWebSockets

3. TeamTalk 的 PC 端

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

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

4. 最后是我的開源 Flamingo IM

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

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

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

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

1.排序（?？嫉呐判虬搭l率考排序為：快速排序 > 冒泡排序 > 歸并排序 > 桶排序）

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

1.二分查找

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

2.鏈表

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

3.隊列與棧

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

4.哈希表

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

5.樹

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

6.圖

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

7.其他的一些算法

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

3. 編碼基本功

還有一類面試題不好分類，筆者姑且將其當(dāng)作是考察編碼基本功，這類問題既可以考察算法也可以考察你寫代碼基本素養(yǎng)，這些素養(yǎng)不僅包括編碼風(fēng)格、計算機英語水平、調(diào)試能力等，還包括你對細(xì)節(jié)的掌握和易錯點理解，如有意識地對邊界條件的檢查和非法值的過濾。請讀者看以下的代碼執(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);