客戶端面試知識點總結

最近通過自己的面試，計劃進入新的一家公司進行作業，中間面試的程序中也發現了自己的一些不足，因為有一些知識點在作業中用到的機會不會很多，就會有一些遺忘，所以自己也是一邊總結一邊面試，將自己每一次面試中回答的不是很好的問題記錄下來，

首先自己面試的崗位大的歸類為客戶端開發，但是不是專門的Android開發或者是iOS開發，所以總結內容還是偏向于資料結構和一些基礎的語法，

因為自己是游戲開發相關的作業，所以主要使用的語言還是C++和Lua，Java和C#雖然也寫的不少，但是自己本身并不是內行，只是偶爾有Android或者Unity相關的任務的時候，會使用對應平臺的語言，所以本次記錄的重點主要是：Lua、C++、資料結構以及一些簡單的演算法，

自己在總結的時候，為了使得自己記憶更加深刻，會將文字記錄盡量的口語化，就像自己在和面試官對話一樣，在看這篇博客的時候，大家完全可以當做在回答面試官的問題，

1、有關多型

這個面試題目，在我面試好幾家公司的時候都有問到過，面試官可能問的是什么是多型？或者讓我談談多型的機制等等，

關于多型，我之前是有寫過一篇博客，但是是我在學習C++的時候總結的，鏈接：C++面向物件語言的特性之一：多型，但是里面還是屬于知識點的總結，面試的時候總不能像背書一樣，把知識點都背下來，這樣肯定是不行的，所以我的回答是這樣：

首先說到多型，那么還是得分成兩個類別，一個靜態多型，一個是動態多型，

靜態多型指的是程式在編譯期間才可以確定的多型型別，而動態多型指的是程式在運行期間才可以確定的多型型別，

靜態多型分為：函式多載和泛型編程，首先是函式多載，滿足這幾個條件就可以多載：①在同一個作用域②函式名相同但是引數不同（引數順序、引數個數、引數型別）③回傳值可以相同可以不同，其次靜態多型里面還有泛型編程，泛型編程里面就是我們的模板，

除了我們剛才說的靜態多型，還有就是我們的動態多型，動態多型的實作就是靠我們的虛函式，

關于虛函式的關鍵字就是：virtual，

被virtual修飾的函式為虛函式，后面加上"=0"則成為了純虛函式，擁有純虛函式的類為抽象類，抽象類不能實體化，之后派生類將抽象類繼承之后，并且實作其虛函式，那派生類才可以實體化物件，

這里有幾個需要注意的點：①就是被宣告為虛函式的函式只能是非靜態函式，靜態函式不能宣告為虛函式；②建構式不能被宣告為虛函式，是因為虛函式是儲存在虛表當中的，每一個物件的儲存空間里面有一張虛表，但是建構式是在你構造物件的時候，這個時候你需要構造物件以及開辟物件所需要的儲存空間，這個時候就和虛函式的原理沖突了，所以建構式是不能為虛函式的，③同樣的道理，解構式就可以是虛函式，因為這個時候物件已經宣告出來，空間已經開辟，虛表也有了，

剛才說的是有關虛函式的一些使用了，那么有了虛函式之后，他還會影響的就是我們的：物件模型，在類中如果有虛函式的話，那么在創建物件的時候，就會在物件模型的前4個位元組多出來，用來存放虛表的指標，用虛表的指標就能獲得虛表，虛表里面存放的就是我們的虛函式，這個里面虛函式的存放順序是按照宣告的順序存放的，這是單個基類的虛表情況，

在派生類中，如果基類有虛函式，且派生類重寫了虛函式，那么其虛表中虛函式的存放規則是這樣的：

①現將基類的虛函式拷貝一份

②如果派生類中對基類中的虛函式進行了重寫，那么派生類的虛函式將替代相同偏移量位置的基類的虛函式

③如果派生類中新增加自己的新函式，那么就按照在派生類中宣告的次序，依次存放到虛表中，

當然了，每一個物件只能有一個虛表，此時派生類的物件模型中就只有一個派生類的虛表，

2、C++中參考和指標的區別

相同點：就是他們倆都指向了記憶體，而指標值指向的是記憶體的地址，參考則是記憶體的別名，

不同點：指標是可以改變值，參考不能被改變值

Sizeof(參考)獲得是參考變數的大小，sizeof(指標)是固定值，32位機器上是4位元組，64位機器是8位元組了

參考是型別安全的，指標不是型別安全的，比如父類指標指向子類物件

3、有關位元組對齊

首先我們要先看一下位元組對齊的規則：

1. 結構體中每一個成員儲存地址的偏移量，是當前成員型別大小的整數倍，不夠就在前一個成員變數的偏移量中補空位元組
2. 結構體總大小，是結構體位元組對齊之后大小的整數倍，不夠就在后面補空位元組

光說可能不是很明了，所以我們舉個例子：

這么一個結構體：char a, int a, double c

不位元組對齊的結果就是1+4+8 = 13位元組，

位元組對齊之后，先放一個位元組的a，再放4個位元組的b，但是因為放好a之后，偏移量就成了1，1不是4的倍數，所以給a的偏移量補齊3個空位元組，這個時候，b就可以在偏移量為4的起始地址存放，存放完成之后，繼續存放double型別的c,因為現在偏移量已經到了8，所以可以直接存放double型別的c，

此時整個程序算下來就4+4+8 = 16位元組了，

那么我們為什么要位元組對齊呢？那一定是為了讀取效率，因為計算機在讀取資料的時候，不是一個位元組一個位元組讀取，而是一次讀取一個位元組塊，如果說按照我們剛才的舉例，這個時候double型別的成員c,肯定是在兩個位元組塊中的，此時計算機就需要讀取兩遍位元組塊，

但是當我們位元組對齊之后，這個成員變數一定是在一整個8位元組的位元組塊中的，那么一次就可以讀取這個成員c，效率就高很多，

4、C++中的隱式轉換const_cast、static_cast、dynamic_cast等

這個C++中提供一種轉換型別的方式，其實可以和C語言中的轉換方式進行對比一下，

C語言中怎么轉換，通常我們C風格的轉換就是直接進行強轉，也就是顯示轉換，大家都認為這種轉換方式比較粗暴，而C++中提供了幾種新的型別轉換方式，利用了模板的一個操作，提供了:static_cast, const_cast, dynamic_cast, reinterpret_cast這幾種轉換方式，

static_cast轉換的就是基本型別的轉換，int 轉成char之類的，還有進行基類和派生類的轉換，但是需要注意的是：派生類轉基類是安全的，基類轉派生類是不安全的，

const_cast看名字就知道是const 和非const型別的一個轉換了，

而dynamic_cast作用的范圍是在類之間進行轉換的，而且dynamic_cast有一個特點就是當遇到非法的轉換的時候回回傳空指標，所以一定程度上可以避免不安全的型別轉換，

5、NULL和nullptr的區別

我們先說這個NULL，C語言中通常把NULL定義為 #define NULL ((void*)0)

也就是把0定義為了一個void*的指標，然后我們將這個NULL賦值給我們自己的型別，這當中是有一個隱式轉換的，

但是C++中其實是不允許將void*隱式轉換成其他型別的指標的，所以C++中會將NULL定義為 0 ，這樣就有可能會出一個問題：

當我們有兩個函式多載時，一個引數是int*型別，一個是int型別，

這個時候，如果我們傳0，就有可能呼叫我們不希望的函式，也就是這樣的操作會有一個二義性，這個時候C++11中的nullptr就很好的解決了這個問題，此時我們就可以直接用nullptr表示空指標，

6、C++中記憶體區域分了哪些，都儲存了什么內容

區域里面首先是我們的堆疊：堆疊空間是編譯器需要的時候進行分配的，里面存放的變數通常就是我們的區域變數了，我通常使用的就是我們的函式堆疊，

堆：堆是由我們程式員自己去開辟和控制的一個記憶體空間，我們什么時候會用到堆呢？

當我們使用new或者malloc去開辟一段我們需要的空間的時候，這一段空間就會在我們的堆上面，對應的我們就需要使用delete和free去釋放對應的空間，

全域/靜態儲存區 這里面儲存的就是我們的全域變數和靜態變數，名字雖然不同但是占用的是同一塊記憶體區

常量儲存區：顧名思義，儲存的就是我們的這個不能被修改的常量，

7、C++程式的運行程序

1. 預編譯階段：①處理宏定義指令，#define，將值進行替換；②條件編譯指令：#ifdefine等，條件編譯指令是為了我們的程式能在在不同環境下做不同的事情③頭檔案指令：#include 頭檔案其實就算是文本展開了， 系統的頭檔案我們用的是<>括號，自己的頭檔案我們用""
2. 編譯階段：編譯階段會檢測我們語法，然后將預編譯產生的檔案轉化成匯編代碼
3. 匯編階段：匯編階段將上一步中的匯編代碼轉化成我們的機器代碼，經過匯編階段得到的是目標檔案；目標檔案有段組成：①代碼段：存放的就是我們程式指令，一般是可讀可執行不可寫的一個狀態②資料段：存放程式中用的全域和靜態資料
4. 鏈接階段：鏈接階段是將我們有參考的檔案做一個關聯，區分的就是我們的靜態鏈接和動態鏈接

8、動態鏈接和靜態鏈接的區別

靜態鏈接：鏈接的時機在形成可執行程式之前

每一個.c檔案都會形成一個.o檔案，但是我們這個檔案中可能要用到其他檔案的函式，為了實作這種情況，就需要進行一個鏈接，

優缺點很明顯，因為是提前鏈接好，所以運行速度會快一些，但是是形成可執行程式之前的鏈接，所以每一個程式都需要對目標檔案持有一份副本，而且聯結器在鏈接靜態庫的時候是以目標檔案為單位的，一個目標檔案中可能有很多的函式，鏈接的時候也會被一起鏈接進來，是比較浪費空間的，

可更新性比較差，因為當靜態庫里面函式改變的時候，就要重新進行編譯鏈接的程序，

動態鏈接：鏈接的時機在程式執行時

鏈接的程序是這樣的：系統首先加載程式1，這個時候發現程式1依賴動態庫1，就去加載動態庫1；當程式2運行的時候，系統發現程式2也依賴于動態庫1，這個時候因為動態庫已經在記憶體中了，就不會再加載了，而只是將動態庫映射到程式2的虛擬地址空間中，

優點：和靜態鏈接對比就是占用的空間下，可更新性強，但是性能稍微低一些，因為是在運行的時候才去加載，

總結就是：視情況而定

8、C++的拷貝建構式為什么要使用const Type&型別

因為如果不是參考的話，首先因為是傳值，所以編譯器要對傳進來的引數進行一次拷貝，這個時候要拷貝引數生成形參，需要用的就還是拷貝建構式，這樣一來就引起了拷貝建構式的回圈呼叫了，

至于const 其實如果不加，編譯器也不會報錯，但是在我們本身無意改變這個值的話，加上const就可以防止函式里面對參考的騷操作，從而引起的一些不必要的錯誤，

9、OpenGL渲染管線的基本描述

1. 首先使我們的頂點資料的一個收集階段，如果我們要畫一個三角形，那么此時我們就需要3個3D資料，每個資料就代表三角形的一個頂點，
2. 期次收集好頂點資料之后，就需要經過我們的頂點著色器的階段，這個階段會對我們的頂點進行一些矩陣計算
3. 接著是我們的圖元裝配階段，按照我們指定的圖元形狀將頂點組裝成對應的形狀
4. 接著是我們的幾何著色器，幾何著色器會通過新產生的頂點而構造出同樣形狀的新的圖元，
5. 接著是我們的光柵化的階段，將圖元映射到對應的螢屏對應的像素，生成片段，每一個片段里面存放的都是計算這個像素需要的所有的資料，這里還會進行裁剪，將不在我們視口范圍內的東西舍棄掉，增加效率，
6. 片段著色器，計算每一個像素最終在螢屏上顏色，
7. 后是我們Alpha測驗和混合階段，進行一些深度測驗，決定當前物體有沒有被遮擋和透明度的一些計算，

10、Lua和C++通信的程序

Lua和C++進行通信的一個基本結構是一個虛擬堆疊，

首先是這個虛擬堆疊的索引，從堆疊底往上是1開始逐漸+1，從堆疊頂往下的-1開始逐漸-1，

因為這樣的話，我們就可以不用知道堆疊里面有多少的元素，而對堆疊進行操作了，

既然是通信，那肯定是分為兩個部分了，一個是C++呼叫Lua，一個是Lua呼叫C++，

A) C++呼叫Lua

首先Lua里面我們經常會做一些配置表，然后進行一些簡單的邏輯運算，都會在Lua里面進行實作，現在我們需要在C++里面讀取Lua里面的變數，

這里面其實有一個約定，就是誰產生誰負責，誰負責誰銷毀，

C++需要我Lua中的變數，那就由Lua去產生，然后由Lua去記錄，再由Lua去銷毀，產生的值就會放在堆疊上面，C++里面可以通過api進行操作這個值，

需要注意的是，堆疊的操作都是基于堆疊頂的，只會操作堆疊頂的值，

比如說Lua里面有一個全域函式：Add（a,b），計算a,b的回傳值，

那我們的程序是什么呢：

首先肯定使是我們的Lua狀態機要拿到，

通過Lua狀態機獲取函式：Add， 然后壓入堆疊（通過lua_getglobal介面）

然后將引數1壓入堆疊

然后將引數2壓入堆疊

然后使用介面lua_pcall介面呼叫函式，同時我們需要將引數的個數，回傳值結果的個數傳給Lua，

呼叫沒有出錯之后，堆疊頂的資料就是我們需要的回傳值，

B) Lua呼叫C++

Lua呼叫C++程序其實比較類似，還是類比于我們C++中有一個Add函式，Lua想要呼叫，

開始呼叫之前呢，就需要將C++中的函式通過lua_register函式進行一個注冊，注冊完成之后就可以將Lua函式與堆疊頂的C++的函式建立一個參考關系，

lua_register函式其實是將lua_pushfunction 和 lua_setglobal兩步進行了一個封裝，

注冊完成之后呢，Lua里面進行呼叫該函式的時候，就會向堆疊里面進行傳參，

傳參程序就是向堆疊里面壓入資料，

然后在我們的C++的Add函式里面，通過lua_gettop獲取堆疊頂索引，此時的堆疊頂索引應該是 引數的個數了，

接著循取出堆疊里面的元素，然后進行操作，最后把我們的計算的值依次壓入堆疊中，

最后通過回傳值告訴Lua該函式回傳給Lua的值的個數，

11、快速排序、堆排序、冒泡排序

這幾種常用的排序演算法，還是自己手敲一遍，印象深刻，光看文字的話，很容易就忘掉了，

12、C++的智能指標

有這么幾種分類：aotu_ptr, shared_ptr, weak_ptr, unique_ptr

1. aotu_ptr：在智能指標的時候中，判斷智能指標是不是空應該使用.get() == nullptr，

中途釋放智能指標使用的是.reset()函式，

如果使用.release函式，只是把當前的只能指標賦值為空，指向的記憶體并沒有釋放，

aotu_ptr在C++11中已經被遺棄，

2. unique_ptr：unique_ptr是取代auto_ptr的產物，是一個獨享所有權的智能指標，

賦值的時候用p1 = std::move(p2)，可以避免p2的指標成為野指標，

unique_ptr可以直接使用==來判斷值是否為空，當然也支持auto_ptr的功能，

3. shared_ptr：shared_ptr通過參考計數來判斷當前資源所有者的個數，可以通過use_count()

查看當前所有者的總數，釋放share_ptr的時候，直到最后一個使用者呼叫，才會釋放所擁有的資源，

4. weak_ptr：weak_ptr使用解決shared_ptr指標回圈參考的問題的，weak_ptr指向物件的時候，不會增加物件的參考計數，是一種弱參考，我們不能直接通過weak_ptr去訪問物件的方法，而是得通過p.lock() 獲取一個shared_ptr的指標，通過這個新的指標去訪問物件中的方法，

13、設計模式之工廠模式

簡單工廠模式

此時我們有一個基類Product，

然后我們有兩個派生類ProductA，ProductB，都繼承與Product，

然后我們有一個Factory類，這個類里面根據條件（switch）來進行創建對應的Product類

工廠模式

此時我們的Factory也有一個基類Factory，

有兩個派生類：FactoryA，FactoryA繼承與Factory

此時我們如果生成A，就是用FactoryA，如果生產B就是用FactoryB，

抽象工廠模式

當然了，情況可能要更復雜一些：

ProductA分為ProductA1，ProductA2兩種型號，

ProductB分為ProductB1，ProductB2兩種型號，

那我們的工廠應該怎么做呢？

我們的應該抽象成創建1型別產品的工廠和創建2型別產品的工廠，

首先是一個基類Factory，里面有兩個介面：

CreateProductA（） 和 CreateProductB（）

然后派生類Factory1，Factory2，

Factory1里面我們需要提供的兩個介面就是CreateProductA（創建產品A1）和CreateProductB（創建產品B1）兩個介面，

Factory2里面我們需要提供的兩個介面就是CreateProductA（創建產品A2）和CreateProductB（創建產品B2）兩個介面，

14、設計模式之監聽者模式

例子：小李在打游戲，小王在抄作業，班長負責監視老師來了沒有，老師來了，通知給大家，小李結束打游戲，小王結束抄作業，

首先肯定是班長的通知基類：TeacherNotify

里面的三個純虛介面：addListener，removeListener，notify

班長的通知類：MonitorNotify

里面有一個List用來存放當前有誰在監聽MonitorNotify通知，

addListener就是供監聽類呼叫，往通知類的List里面添加監聽

removeListener就是移除監聽，從List里面

Notify就回圈List，遍歷出來之后，回圈的通知各個對應的TeacherListener，

學生的監聽類就是：TeacherListener，

里面就一個純虛介面：onTeacherComing()

這個時候派生類就是:小李類和小王類

需要實作onTeacherComing介面，然后里面做自己對應的邏輯，

15、Lua的垃圾回識訓制

Lua的GC采用的是標記清除法，先對所有的物件進行一次掃描，掃描完成之后，根據物件是否可以訪問才決定是否回收物件，

Lua中會將物件標記為三種顏色，白色，灰色和黑色，

白色代表可回收的狀態，

灰色為待標記狀態，表示當前對應已經被GC標記，但是其參考的物件還沒有被GC標記，

黑色為正常使用的不可回收狀態，

回收的整個程序：

1、首先新建物件的狀態被標記為白色

2、先遍歷整個根節點中的物件，也就是Lua中類似全域表的空間，將遍歷出來的物件，標記為灰色，然后放在灰色集合中，

3、回圈遍歷灰色鏈表，把當前拿出來的物件設定為黑色，然后遍歷其參考的物件有哪些，如果其參考的物件狀態為白色，就將其設定為灰色，然后加入到灰色的集合中，等待遍歷，直至灰色集合遍歷完成，

4、上面的遍歷階段完成之后，接著就是清除階段，清除標記為白色的物件，

5、最后在reset相關的狀態，等待下一次的GC條件滿足之后，在進行GC，

Lua5.1之后

參考了增量GC的一個概念，因為如果按照之前的一旦開始GC，不能停止的執行方式，會影響程式的執行，

所以增量GC就將每一步分成了若干狀態去執行，當某一次執行量過大的時候，就等待下一次的遍歷，

但是這個時候就有可能產生另外一種問題，

就是是標記階段完成，但是清掃階段還沒有開始的時候，此時有新的物件產生；正常來說它是應該被標記為白色的，但是如果標記為白色的話，按照接下來進行清掃操作的規則，就會把白色的物件清掃掉，這樣顯然是不合理的，

所以Lua里面的解決辦法就是創建兩個白色，白色1和白色2；

如果上述情況發生的話，Lua會將新創建的變數標記為白色2，當清掃階段開始的時候，只會清掃白色1標記的物件，這樣就解決了這個問題，

Lua中的GC還有兩個因素：一個是間歇率，一個是步進倍率，

間歇率控制的是當前記憶體使用總量的是上一次的幾倍的時候，開啟GC，200就是代表兩倍，增大這個值會讓垃圾收集器變得不積極，

步進倍率控制的是垃圾收集器是以記憶體分配的多少速率來進行回收的，增大這個值會讓垃圾收集器變得更積極，Lua提供的介面是：collectgarbage（），里面的引數就是：”collect”:做一下垃圾回收，“restart”:重啟垃圾收集器等...

16、Lua中是怎么區分值是在陣列中儲存還是在哈希表中儲存

陣列試圖保存所有key值介于1到n之間的值

非整數的key值和超過一定資料范圍的key，其對應的值會存放在哈希表中，

對于存盤的陣列的大小要求同時滿足：①1-n之間有一半的空間沒有浪費 ②二分之n到n的空間上至少有一個空間被利用，

17、Lua中table表的Hash部分是怎么進行插入賦值的

對于table中哈希表的部分，Lua使用的方法是開放地址法，為了讓資料更緊湊，

賦值的時候，首先判斷key值是不是在table中，

如果在，那就直接插入，

如果不在，則檢查當前Hash出來的位置是否為空，

如果為空則直接插入，

如果不為空，就要判斷占領當前位置的node是不是主位置，如果是主位置，則將自己要插入的node存放到新的節點里面；如果不是主位置，則把當前的結點放到新位置，在把自己要插入得值放在當前位置中，

獲取新位置的函式，執行程序是：獲取table結構中記錄當前hash表最后一個位置的指標，然后向前遍歷，找到一個為nil的位置，回傳這個nil的位置，若沒有找到則進行reHash操作，重新分配空間，

18、平衡樹是怎么插入節點的

19、紅黑樹是怎么插入節點的

19和20問題，我建議大家還是和排序問題一樣，上手敲一下代碼記得會比較清晰一些，

20、有關STL的問題

STL的問題是比較五花八門的，估計單寫一篇博客還是不能完全的總結，但是里面主要問題還是會問你STL里面容器的底層資料結構是什么，陣列、哈希表等等，

還有就是STL里面 有關迭代器失效的問題，

以及底層資料結構查詢和插入的時間、空間復雜度等，

寫在后面

這一次面試也讓我重新撿起了基礎知識的學習，有一些問題校招的時候也是有問過的，所以可見大家對于面試者的基礎知識是很看重的，

還有就是寫在你簡歷上的專案內容，只要是寫在簡歷上的，就必須要弄懂弄透，包括：底層原理以及自己在作業中遇到的坑，這些必須是要了如指掌的，

這幾周的面試經過，基本把大家能夠想到的游戲公司都面試了一下，因為自己剛開始的時候是投的Unity的崗位，但是自己的Unity都是自己私下學習的，沒有相關專案的實踐，所以幾乎都撲街了，導致后面都有點懷疑自己的能力是不是真的不行，好在自己在后面就及時的調整了方向，繼續面試平臺相關的崗位，找朋友幫忙內推，也算是在金三銀四的招聘季尾聲拿下了騰訊、網易、無端科技、沐瞳的offer，

也希望這篇總結能幫助大家拿到自己心儀的offer，

順便打個廣告：騰訊天美J6作業室，內推可以聯系我:374489401@qq.com，歡迎投簡歷~

想試試：西山居，莉莉絲，無端科技，Funplus等大廠的朋友都可以幫你內推，歡迎騷擾！