快手實習生面試（C++,一面涼）

中興的比賽終于結束，終于有時間來回顧一下上次慘不忍睹的面試，害，說實話還是我第一次找工作的面試，居然還是視訊面試，中間麥克風也各種出問題，磕磕絆絆面了大概一個小時左右吧，然後就結束了，這裡回顧一下面試中的問題以及步驟吧，問題無先後順序。

1 自我介紹（略）

2 如何解決菱形繼承問題

這個問題有印象，當時答地是，基類對象函數必須為純虛函數。然後面試官也沒說對錯，就問了下還有别的嗎，然後我就說沒了。面試官也沒說對錯就開始下一問了。我查了下，錯的太離譜了...答案：兩個派生類繼承同一個基類，又有某個類同時繼承者兩個派生類，這種繼承被稱為菱形繼承。采用虛繼承可以解決這個問題。

3 虛函數定義

簡單地說，那些被virtual關鍵字修飾地成員函數，就是虛函數。虛函數的作用，用專業術語來解釋就是實作多态性（Polymorphism），多态性是将接口與實作進行分離；用形象的語言來解釋就是實作以共同的方法，但因個體差異，而采用不同的政策。

4 排序的穩定性，概念

這個說錯了，我還以為試是問時間複雜度的穩定性...，這個之前确實沒學到過，面試官和我說了下，是：假定在待排序的記錄序列中，存在多個具有相同的關鍵字的記錄，若經過排序，這些記錄的相對次序保持不變，即在原序列中，r[i]=r[j]，且r[i]在r[j]之前，而在排序後的序列中，r[i]仍在r[j]之前，則稱這種排序算法是穩定的；否則稱為不穩定的。

5 哈希表

哈希表是根據關鍵碼值(Key value)而直接進行通路的資料結構。也就是說，它通過把關鍵碼值映射到表中一個位置來通路記錄，以加快查找的速度。這個映射函數叫做散列函數，存放記錄的數組叫做散清單。

接下來問了哈希表的構造方法，我說忘記了（下面摘錄自百度）。

1.直接尋址法：取關鍵字或關鍵字的某個線性函數值為散列位址。即H(key)=key或H(key) = a·key + b，其中a和b為常數（這種散列函數叫做自身函數）。若其中H(key）中已經有值了，就往下一個找，直到H(key）中沒有值了，就放進去。

2. 數字分析法：分析一組資料，比如一組員工的出生年月日，這時我們發現出生年月日的前幾位數字大體相同，這樣的話，出現沖突的幾率就會很大，但是我們發現年月日的後幾位表示月份和具體日期的數字差别很大，如果用後面的數字來構成散列位址，則沖突的幾率會明顯降低。是以數字分析法就是找出數字的規律，盡可能利用這些資料來構造沖突幾率較低的散列位址。

3. 平方取中法：當無法确定關鍵字中哪幾位分布較均勻時，可以先求出關鍵字的平方值，然後按需要取平方值的中間幾位作為哈希位址。這是因為：平方後中間幾位和關鍵字中每一位都相關，故不同關鍵字會以較高的機率産生不同的哈希位址。

4. 折疊法：将關鍵字分割成位數相同的幾部分，最後一部分位數可以不同，然後取這幾部分的疊加和（去除進位）作為散列位址。數位疊加可以有移位疊加和間界疊加兩種方法。移位疊加是将分割後的每一部分的最低位對齊，然後相加；間界疊加是從一端向另一端沿分割界來回折疊，然後對齊相加。

5. 随機數法：選擇一随機函數，取關鍵字的随機值作為散列位址，即H(key)=random(key)其中random為随機函數,通常用于關鍵字長度不等的場合。

6. 除留餘數法：取關鍵字被某個不大于散清單表長m的數p除後所得的餘數為散列位址。即 H(key) = key MOD p,p<=m。不僅可以對關鍵字直接取模，也可在折疊、平方取中等運算之後取模。對p的選擇很重要，一般取素數或m，若p選的不好，容易産生同義詞。

6 圖的建構

問了幾個圖存儲結構。有鄰接矩陣、鄰接多重表、鄰接表、十字連結清單等。

7 無序數組求中位數（提示：堆）

劍指offer面試題41，可惜忘記了。

寫代碼：

兩個都對了

1 不引入第三個變量交換倆變量

2 翻轉連結清單

總結

一面涼，我感覺主要是崗位不合适，因為我投的是iOS開發...主要是在深圳沒太多合适的崗位，然後北京覺得太遠，害，下次努力呗！加油！