拼多多、騰訊 C++開發工程師面試題

（一）拼多多實習服務端

1、 一個C++源檔案從文本到可執行檔案經曆的過程

對于C/C++編寫的程式，從源代碼到可執行檔案，一般經過下面四個步驟：

1).預處理，産生.ii檔案

2).編譯，産生彙編檔案(.s檔案)

3).彙編，産生目标檔案(.o或.obj檔案)

4).連結,産生可執行檔案(.out或.exe檔案)

2、#include 的順序以及尖叫括号和雙引号的差別

1. #include的順序的差別：

頭檔案的引用順序對于程式的編譯還是有一定影響的。如果要在檔案a.h中聲明一個在檔案b.h中定義的變量，而不引用b.h。那麼要在a.c檔案中引用b.h檔案，并且要先引用b.h，後引用a.h,否則彙報變量類型未聲明錯誤，也就是常見的某行少個“；”符号。

2. #include尖括号和雙引号的差別：

1）#include <> ，認為該頭檔案是标準頭檔案。編譯器将會在預定義的位置集查找該頭檔案，這些預定義的位置可以通過設定查找路徑環境變量或者通過指令行選項來修改。使用的查找方式因編譯器的不同而差别迥異。

2）#include ""，認為它是非系統頭檔案，非系統頭檔案的查找通常開始于源檔案所在的路徑。查找範圍大于<>。

3、程序和線程，為什麼要有線程

1、和程序相比，它是一種非常"節儉"的多任務操作方式。在linux系統下，啟動一個新的程序必須配置設定給它獨立的位址空間，建立衆多的資料表來維護它的代碼段、堆棧段和資料段，這是一種"昂貴"的多任務工作方式。（資源）

2、運作于一個程序中的多個線程，它們之間使用相同的位址空間，而且線程間彼此切換所需時間也遠遠小于程序間切換所需要的時間。據統計，一個程序的開銷大約是一個線程開銷的30倍左右。（切換效率）

3、線程間友善的通信機制。對不同程序來說，它們具有獨立的資料空間，要進行資料的傳遞隻能通過程序間通信的方式進行，這種方式不僅費時，而且很不友善。線程則不然，由于同一進城下的線程之間貢獻資料空間，是以一個線程的資料可以直接為其他線程所用，這不僅快捷，而且友善。（通信）

除以上優點外，多線程程式作為一種多任務、并發的工作方式，還有如下優點：

1、使多CPU系統更加有效。作業系統會保證當線程數不大于CPU數目時，不同的線程運作于不同的CPU上。(CPU設計保證）

2、改善程式結構。一個既長又複雜的程序可以考慮分為多個線程，成為幾個獨立或半獨立的運作部分，這樣的程式才會利于了解和修改。（代碼易維護）

4、C++11有哪些新特性

1）關鍵字及新文法：auto、nullptr、for

2）STL容器：std::array、std::forward_list、std::unordered_map、std::unordered_set

3）多線程：std::thread、std::atomic、std::condition_variable

4）智能指針記憶體管理：std::shared_ptr、std::weak_ptr

5）其他：std::function、std::bind和lamda表達式

5、為什麼可變參數模闆至關重要，右值引用，完美轉發，lambda

6、malloc的原理，brk系統調用幹什麼的，mmap呢

malloc的實作方案：

1）malloc 函數的實質是它有一個将可用的記憶體塊連接配接為一個長長的清單的所謂空閑連結清單。

2）調用 malloc（）函數時，它沿着連接配接表尋找一個大到足以滿足使用者請求所需要的記憶體塊。 然後，将該記憶體塊一分為二（一塊的大小與使用者申請的大小相等，另一塊的大小就是剩下來的位元組）。 接下來，将配置設定給使用者的那塊記憶體存儲區域傳給使用者，并将剩下的那塊（如果有的話）傳回到連接配接表上。

3）調用 free 函數時，它将使用者釋放的記憶體塊連接配接到空閑連結清單上。

4）到最後，空閑鍊會被切成很多的小記憶體片段，如果這時使用者申請一個大的記憶體片段， 那麼空閑連結清單上可能沒有可以滿足使用者要求的片段了。于是，malloc（）函數請求延時，并開始在空閑連結清單上檢查各記憶體片段，對它們進行記憶體整理，将相鄰的小空閑塊合并成較大的記憶體塊。

brk和mmap：

從作業系統角度來看，程序配置設定記憶體有兩種方式，分别由兩個系統調用完成：brk和mmap（不考慮共享記憶體）。

1、brk是将資料段(.data)的最高位址指針_edata往高位址推；

2、mmap是在程序的虛拟位址空間中（堆和棧中間，稱為檔案映射區域的地方）找一塊空閑的虛拟記憶體。

這兩種方式配置設定的都是虛拟記憶體，沒有配置設定實體記憶體。在第一次通路已配置設定的虛拟位址空間的時候，發生缺頁中斷，作業系統負責配置設定實體記憶體，然後建立虛拟記憶體和實體記憶體之間的映射關系。

在标準C庫中，提供了malloc/free函數配置設定釋放記憶體，這兩個函數底層是由brk，mmap，munmap這些系統調用實作的。

7、C++的記憶體管理方式，STL的allocator，最新版本預設使用的配置設定器

C++的記憶體管理方式：

在c++中記憶體主要分為5個存儲區：

棧（Stack）：局部變量，函數參數等存儲在該區，由編譯器自動配置設定和釋放.棧屬于計算機系統的資料結構，進棧出棧有相應的計算機指令支援，而且配置設定專門的寄存器存儲棧的位址，效率分高，記憶體空間是連續的，但棧的記憶體空間有限。

堆(Heap)：需要程式員手動配置設定和釋放（new,delete），屬于動态配置設定方式。記憶體空間幾乎沒有限制，記憶體空間不連續，是以會産生記憶體碎片。作業系統有一個記錄空間記憶體的連結清單，當收到記憶體申請時周遊連結清單，找到第一個空間大于申請空間的堆節點，将該節點配置設定給程式，并将該節點從連結清單中删除。一般，系統會在該記憶體空間的首位址處記錄本次配置設定的記憶體大小，用于delete釋放該記憶體空間。

全局/靜态存儲區:全局變量，靜态變量配置設定到該區，到程式結束時自動釋放，包括DATA段（全局初始化區）與BSS段（全局未初始化段）。其中，初始化的全局變量和靜态變量存放在DATA段，未初始化的全局變量和靜态變量存放在BSS段。BSS段特點：在程式執行前BSS段自動清零，是以未初始化的全局變量和靜态變量在程式執行前已經成為0.

文字常量區：存放常量，而且不允許修改。程式結束後由系統釋放。

程式代碼區：存放程式的二進制代碼

SGI 版本STL的預設配置器std::alloc

參見：《STL源碼剖析》

1）考慮到小型區塊所可能造成的記憶體碎片問題，SGI設計了雙層配置器。第一級配置器直接使用malloc()和free()；第二級則視情況采取不同的政策：當配置區塊超過128bytes時，視為“足夠大”，便調用第一級配置器；當配置區塊小于128bytes時，視之為“過小”，為了降低額外負擔，便采用memory pool（記憶體池）整理方式，而不在求助于第一級配置器。

2）記憶體池的核心：記憶體池和16個自由連結清單（各自管理8,16，...，128bytes的小額區塊）。在配置設定一個小區塊時，首先在所屬自由連結清單中尋找，如果找到，直接抽出配置設定；若所屬自由連結清單為空，則請求記憶體池為所屬自由連結清單配置設定空間；預設情況下，為該自由連結清單配置設定20個區塊，若記憶體池剩餘容量不足，則配置設定可配置設定的最大容量；若記憶體池連一個區塊都無法配置設定，則調用chunk_alloc為記憶體池配置設定一大塊區塊；若記憶體不足，則嘗試調用malloc配置設定，否則傳回bad_alloc異常。

8、hash表的實作，包括STL中的哈希桶長度常數。

hash表的實作主要涉及兩個問題：散列函數和碰撞處理。

1）hash function （散列函數）。最常見的散列函數：f(x) = x % TableSize .

2）碰撞問題（不同元素的散列值相同）。解決碰撞問題的方法有許多種，包括線性探測、二次探測、開鍊等做法。SGL版本使用開鍊法，使用一個連結清單保持相同散列值的元素。

雖然開鍊法并不要求表格大小必須為質數，但SGI STL仍然以質數來設計表格大小，并且将28個質數（逐漸呈現大約兩倍的關系）計算好，以備随時通路，同時提供一個函數，用來查詢在這28個質數之中，“最接近某數并大于某數”的質數。

9、hash表如何rehash，怎麼處理其中儲存的資源

先想想為什麼需要rehash:

因為，當loadFactor（負載因子）<=1時，hash表查找的期望複雜度為O(1). 是以，每次往hash表中添加元素時，我們必須保證是在loadFactor <1的情況下，才能夠添加。

模仿C++的vector擴容方式，Hash表中每次發現loadFactor==1時，就開辟一個原來桶數組的兩倍空間（稱為新桶數組），然後把原來的桶數組中元素全部轉移過來到新的桶數組中。注意這裡轉移是需要元素一個個重新哈希到新桶中的。

（二）騰訊二面面經

1、redis的主從複制怎麼做的

Redis舊版複制功能隻有同步和指令傳播。新版複制功能加入了部分同步的功能。

1）同步：

2）指令傳播：

當主伺服器會将自己執行的寫指令，也即是造成主從伺服器不一緻的那條寫指令，發送給從伺服器執行，當從伺服器執行了相同的寫指令之後，主從伺服器将再次回到一緻狀态。

3）部分同步：（斷線後重複制）

複制偏移量：通過對比主從伺服器的複制偏移量，程式可以很容易地知道主從伺服器是否處于一緻狀态。

複制積壓緩沖區：主服務儲存最近的寫指令到複制積壓緩沖區，是一個先進先出隊列

伺服器運作ID：從伺服器記錄上次同步的主伺服器的Id。

2、寫代碼，去掉字元串中的空格空格

#include <iostream>
 using namespace std;
 int main()
 {
 char str[40] = " abc 123 456 ";
 int num = 0;
 int i;
 for(i = 0; str[i] != '\0'; ++i)
 {
 if(str[i] == ' ')
 ++num;
 else
 str[i-num] = str[i];
 }
 str[i-num] = '\0';
 printf("%s\n",str);
}
           

3、如何把一個檔案快速下發到100w個伺服器

gossip算法？Gossip有衆多的别名“閑話算法”、“疫情傳播算法”、“病毒感染算法”、“謠言傳播算法”。

4、如何判斷一個圖是否連同？

DFS、BFS、并查集

如果大家對C/C++感興趣的話，可以加一下我們的學習交流Q群：637  935  295，免費領取一套學習資料和視訊課程喲~

5、ubuntu開機的時候系統做了什麼

1）加載BIOS

BIOS程式首先檢查，計算機硬體能否滿足運作的基本條件，這叫做”硬體自檢”。硬體自檢完成後，BIOS把控制權轉交給下一階段的啟動程式。

2）讀取MBR

計算機讀取該裝置的第一個扇區，也就是讀取最前面的512個位元組。如果這512個位元組的最後兩個位元組是0x55和0xAA，表明這個裝置可以用于啟動；如果不是，表明裝置不能用于啟動，控制權于是被轉交給”啟動順序”中的下一個裝置。

3）Bootloader

在這種情況下，計算機讀取”主引導記錄”前面446位元組的機器碼之後，不再把控制權轉交給某一個分區，而是運作事先安裝的”啟動管理器”（boot loader），由使用者選擇啟動哪一個作業系統。

Boot Loader 就是在作業系統核心運作之前運作的一段小程式。通過這段小程式，我們可以初始化硬體裝置、建立記憶體空間的映射圖，進而将系統的軟硬體環境帶到一個合适的狀态，以便為最終調用作業系統核心做好一切準備。

Boot Loader有若幹種，其中Grub、Lilo和spfdisk是常見的Loader。Linux環境中，目前最流行的啟動管理器是Grub。

4）加載核心

核心的加載，核心加載後，接開始作業系統初始化，根據程序的優先級啟動程序。