c++面试题【转】 面经
c++面試題【轉】
語言部分：
- 虛函數，多態。這個概念幾乎是必問。
- STL的使用和背后數據結構，vector string map set 和hash_map，hash_set
- 實現一個棧類，類似STL中的棧。這個題目初看非常簡單，當時我還有點不屑，怎么出這么簡單的題。但寫過c++和沒有寫過c++的人寫出的代碼是一眼就能看出差別的。譬如三大函數有沒有寫，引用的使用，都非常的關鍵。如果這方面沒有經驗，建議閱讀下http://book.douban.com/subject/1971825/ 這本書中簡單數據結構的實現，細節很關鍵?
- c部分：函數指針的聲明
- c++中的多線程
算法部分：
- 判斷一個單鏈表是否存在循環（快慢指針的方法）
- 如何判斷一副麻將牌胡了（回朔法）
- 二叉搜索樹，節點上已經標有數字，如何找兩個節點的最小公共節點（查找第一個在兩個節點值中間的節點，如兩個節點分別是3,8，查找在3,8之間的值的節點，如沒找到，則3,8其中一個是另一個父節點）
- 二叉樹，如何找兩個節點的最小公共節點（比較笨的方法是，找到從root到兩個節點的路徑，然后兩條路徑的從root開始的最后一個相同節點就是所求節點。精妙點的參考lca算法）
- 最短摘要生成，有一個數組，還有一個集合，在數組中尋找包含集合中全部元素的最短子串。詳細可以參見編程之美3.5
- 尋找最大的K個數，編程之美2.5
- 如何判斷兩個網頁的相關性（如果說面試搜索相關的只是，看下吳軍的數學之美大有裨益，其中的向量空間模型非常優美，TF和IDF這些術語也必須知道）
- Hash的平均查找長度和裝填因子的關系（好好回味下數據結構書吧）哈希表（等概率情況下）查找成功與查找不成功的平均查找長度
- 裝填因子load factor λ：散列表中元素 與 散列表大小 的比值。
- 常數時間 執行插入 刪除 查找，；哈希函數；解決沖突：分離鏈接法，λ≈1，不使用分離連接，盡量讓λ<0.5 這樣效率最高
- 一致性hash原理一致性哈希算法(consistent hashing)
- rehash的時候可能導致插入的元素響應時間特別長，有無更好的方法？
- 可以參考redis的rehash實現，當到了rehash的時候，不是一次性把所有的數據遷移到另一個更大的hash表中，而是每次遷移一個bucket，這樣可以平攤時間
- 如何對全是01的文件進行壓縮，一直沒有好的答案。高壓縮文件是如何實現的
??
系統設計部分：
- 當系統的處理請求時間一定的時候，如何可以加快響應速度。（cache的使用），當時很傻，竟然沒想到這個，我給的答案是增加系統規模，這樣只能減少請求等待時間。有時候面試人就會短路，google的題，想了半天才想出來
- 兩塊虛擬網卡進行通訊，但是需要數據加密，如何實現數據加密。感覺跟ssl很像
編程部分：
- 二分查找（頻率超高）
- 建堆，順便說下建堆的時間復雜度是O(n)，不是log，證明可以看算法導論構建二叉堆時間復雜度的證明
- 寫一個函數，將字符串反轉，反轉方式如下：“I am a student”反轉成“student a am I”，不借助任何庫函數 （頻率超高的一題，先反轉整個字符串，然后反轉每個詞）
?
詳細分析
2.標準關聯容器set, multiset, map, multimap
? ??內部采用的就是一種非常高效的平衡檢索二叉樹：紅黑樹，也成為RB樹(Red-BlackTree)。RB樹的統計性能要好于一般的平衡二叉樹
3.STL map和set的使用中不易理解的地方
- map: type pair<constKey, T>
? ??? ??很多不同的const Key對應的T對象的一個集合，所有的記錄集中只要const Key 不一樣就可以，T無關！
- set: type const Key
? ??? ??只存單一的對const Key，沒有map 的T對像！可以看成map的一個特例
?
（1）為何map和set的插入刪除效率比用其他序列容器高？，樹?
答：因為對于關聯容器來說，不需要做內存拷貝和內存移動。說對了，確實如此。map和set容器內所有元素都是以節點的方式來存儲，其節點結構和鏈表差不多，指向父節點和子節點
?
（2）為何每次insert之后，以前保存的iterator不會失效？
答：iterator這里就相當于指向節點的指針，內存沒有變，指向內存的指針怎么會失效呢(當然被刪除的那個元素本身已經失效了)。相對于vector來說，每一次刪除和插入，指針都有可能失效，調用push_back在尾部插入也是如此。因為為了保證內部數據的連續存放，iterator指向的那塊內存在刪除和插入過程中可能已經被其他內存覆蓋或者內存已經被釋放了。即使時push_back的時候，容器內部空間可能不夠，需要一塊新的更大的內存，只有把以前的內存釋放，申請新的更大的內存，復制已有的數據元素到新的內存，最后把需要插入的元素放到最后，那么以前的內存指針自然就不可用了。特別時在和find等算法在一起使用的時候，牢記這個原則：不要使用過期的iterator。
?
（3）為何map和set不能像vector一樣有個reserve函數來預分配數據？
答：我以前也這么問，究其原理來說時，引起它的原因在于在map和set內部存儲的已經不是元素本身了，而是包含元素的節點。也就是說map內部使用的Alloc并不是map<Key, Data, Compare, Alloc>聲明的時候從參數中傳入的Alloc。
4.set, multiset
? ??set和multiset會根據特定的排序準則自動將元素排序，set中元素不允許重復，multiset可以重復。
? ??因為是排序的，所以set中的元素不能被修改，只能刪除后再添加。
? ??向set中添加的元素類型必須重載<操作符用來排序。排序滿足以下準則：
? ??set中判斷元素是否相等：
? ??if(!(A<B || B<A))，當A<B和B<A都為假時，它們相等。
5.map，multimap
? ??map和multimap將key和value組成的pair作為元素，根據key的排序準則自動將元素排序，map中元素的key不允許重復，multimap可以重復。
- map<key,value>?
因為是排序的，所以map中元素的key不能被修改，只能刪除后再添加。key對應的value可以修改。
向map中添加的元素的key類型必須重載<操作符用來排序。排序與set規則一致。
6. List的功能方法
實際上有兩種List: 一種是基本的ArrayList,其優點在于隨機訪問元素，另一種是更強大的LinkedList,它并不是為快速隨機訪問設計的，而是具有一套更通用的方法。
List : 次序是List最重要的特點：它保證維護元素特定的順序。List為Collection添加了許多方法，使得能夠向List中間插入與移除元素(這只推薦LinkedList使用。)一個List可以生成ListIterator,使用它可以從兩個方向遍歷List,也可以從List中間插入和移除元素。
?
ArrayList : 由數組實現的List。允許對元素進行快速隨機訪問，但是向List中間插入與移除元素的速度很慢。ListIterator只應該用來由后向前遍歷ArrayList,而不是用來插入和移除元素。因為那比LinkedList開銷要大很多。
LinkedList : 對順序訪問進行了優化，向List中間插入與刪除的開銷并不大。隨機訪問則相對較慢。(使用ArrayList代替。)還具有下列方法：addFirst(), addLast(), getFirst(),getLast(), removeFirst() 和 removeLast(), 這些方法 (沒有在任何接口或基類中定義過)使得LinkedList可以當作堆棧、隊列和雙向隊列使用
7.1 hash_map和map的區別在哪里？
構造函數。hash_map需要hash函數，等于函數；map只需要比較函數(小于函數).
存儲結構。hash_map采用hash表存儲，map一般采用紅黑樹(RB Tree)實現。因此其memory數據結構是不一樣的。
7.2 什么時候需要用hash_map，什么時候需要用map?
? ??總體來說，hash_map 查找速度會比map快，而且查找速度基本和數據數據量大小，屬于常數級別map的查找速度是log(n)級別。并不一定常數就比log(n)小，hash還有hash函數的耗時，明白了吧，如果你考慮效率，特別是在元素達到一定數量級時，考慮考慮hash_map。但若你對內存使用特別嚴格，希望程序盡可能少消耗內存，那么一定要小心，hash_map可能會讓你陷入尷尬，特別是當你的hash_map對象特別多時，你就更無法控制了，而且hash_map的構造速度較慢。
?
? ??? ??現在知道如何選擇了嗎？權衡三個因素: 查找速度, 數據量, 內存使用。
8.一些使用上的建議：
Level 1 - 僅僅作為Map使用：采用靜態數組
Level 2 - 保存定長數據，使用時也是全部遍歷：采用動態數組（長度一開始就固定的話靜態數組也行）
Level 3 - 保存不定長數組，需要動態增加的能力，側重于尋找數據的速度：采用vector
Level 3 - 保存不定長數組，需要動態增加的能力，側重于增加刪除數據的速度：采用list
Level 4 - 對數據有復雜操作，即需要前后增刪數據的能力，又要良好的數據訪問速度：采用deque
Level 5 - 對數據中間的增刪操作比較多：采用list，建議在排序的基礎上，批量進行增刪可以對運行效率提供最大的保證
Level 6 - 上述中找不到適合的：組合STL容器或者自己建立特殊的數據結構來實現
?
9.其他
(1).vector - 會自動增長的數組
vector<int>vec(10) //一個有10個int元素的容器
vector<float> vec(10, 0.5)//一個有10個float元素的容器，并且他們得值都是0.5
vector<int>::iterator iter;
for(iter = vec.begin(); iter != vec.end(); iter++)
{
//. . . . . . .
}
?
? ??vector由于數組的增長只能向前，所以也只提供了后端插入和后端刪除，也就是push_back和pop_back。當然在前端和中間要操作數據也是可以的，用insert和erase，但是前端和中間對數據進行操作必然會引起數據塊的移動，這對性能影響是非常大的。
?? ??? ??
最大的優勢就是隨機訪問的能力。
vector<T1>::iterator相關的方法有：
begin()：用來獲得一個指向vector第一個元素的指針
end()：用來獲得一個指向vector最后一個元素之后的那個位置的指針，注意不是指向最后一個元素。
erase(vector<T1>::iterator)：用來刪除作為參數所傳入的那個iterator所指向的那個元素。
?
(2).list - 擅長插入刪除的鏈表
list<string>Milkshakes; list<int> Scores;
push_back, pop_backpush_front. pop_front
?
list是一個雙向鏈表的實現。
為了提供雙向遍歷的能力，list要比一般的數據單元多出兩個指向前后的指針
?
一個使用iterator來刪除元素的例子
list<string> stringList;
list<string>::iterator iter;
advance(iter, 5); //將iterator指向stringList的第五個元素
stringList.erase(iterator);//刪除
那么刪除操作進行以后，傳入erase()方法的iterator指向哪里了呢？它指向了刪除操作前所指向的那個元素的后一個元素。
?
(3).deque - 擁有vector和list兩者優點的雙端隊列
?
(4)．這三個模板的總結 比較和一般使用準則
這三個模板都屬于序列類模板，可以看到他們有一些通用方法
-
- size():得到容器大小
- begin():得到指向容器內第一個元素的指針（這個指針的類型依容器的不同而不同）
- end():得到指向容器內最后一個元素之后一個位置的指針
- erase():刪除傳入指針指向的那個元素
- clear():清除所有的元素
- ＝＝運算符：判斷兩個容器是否相等
- ＝運算符：用來給容器賦值
上面的三個模板有各自的特點
-
- vector模板的數據在內存中連續的排列，所以隨機存取元素（即通過[]運算符存取）的速度最快，這一點和數組是一致的。同樣由于它的連續排列，所以它在除尾部以外的位置刪除或添加元素的速度很慢，在使用vector時，要避免這種操作。
- list模板的數據是鏈式存儲，所以不能隨機存取元素。它的優勢在于任意位置添加 刪除元素的速度。
- deque模板是通過鏈接若干片連續的數據實現的，所以均衡了以上兩個容器的特點
?
?
標簽:?C++
好文要頂?關注我?收藏該文??
copperface
關注 - 3
粉絲 - 11
+加關注
0
0
??上一篇：你的變量究竟存儲在什么地方 && 全局內存【轉】
??下一篇：內存的靜態分配和動態分配的區別【轉】
?
總結
以上是生活随笔為你收集整理的c++面试题【转】 面经的全部內容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： 图解C++虚函数 虚函数表
- 下一篇： 内存的静态分配和动态分配的区别【转】