第6章 面試中的各項能力 6.1 面試官談能力 “應聘者能夠禮貌平和、不卑不亢地和面試官交流，邏輯清晰、詳略得當地介紹自己及項目經歷，談論題目時能夠發現問題的細節并向面試官進行詢問，這些都是比較好的溝通表現。對自己做的項目能夠了解很深入、對面試題能夠快速尋找解決方法是判斷應聘者學習能力的一個方法。這兩個能力都很重要，基本能夠起到一票否決的作用。” ——殷焰（支付寶，高級安全測試工程師） “有時候會問一些應聘者不是很熟悉的領域，看應聘者在遇到難題時的反應，在他們回答不出時會有人員提供解答，在解答過程中觀察他的溝通能力及求知欲。” ——朱麟（交通銀行，項目經理） “溝通能力其實整個過程都在考核，包括詢問他過往的經歷，也通常會涉及溝通能力。學習能力是在考查算法或者項目經驗過程中，通過提問，尤其是一些他沒有接觸過的問題來考核的。溝通能力和學習能力很重要，在某種程度上這些都是潛力。如果應聘者溝通能力不行、難以合作，我們不會錄取。” ——何幸杰（SAP，高級工程師） “讓其介紹過往項目其實就在考查溝通和表達能力。學習能力通過問其看書和關注什么來考查。溝通能力、學習能力對最終面試結果會有一定的影響。對于資深的應聘者，影響要大些。” ——韓偉東（盛大，高級研究員） “應聘者會被問及一些需求不是很明確的問題，解決這些問題需要應聘者和面試官進行溝通，以及在講解設計思路和代碼的過程中也需要和面試官交流互動。溝通及學習能力是面試成績中關鍵的考查點。” ——堯敏（淘寶，資深經理） “溝通、學習能力就是看面試者能否清晰、有條理地表達自己，是否會在自己所得到的信息不夠的情況下主動發問澄清，能否在得到一些暗示之后迅速做出反應糾正錯誤。” ——陳黎明（微軟，SDE II） 6.2 溝通能力和學習能力 1．溝通能力 隨著軟件、系統功能越來越復雜，開發團隊的規模也隨之擴張，開發者、測試者和項目經理之間的溝通交流也變得越來越重要。也正因為此，很多公司在面試的時候都會注意考查應聘者的溝通能力。這就要求應聘者無論是在介紹項目經驗還是介紹解題思路的時候，都需要邏輯清晰明了，語言詳略得當，表述的時候重點突出、觀點明確。 我們不能把好的溝通能力理解成夸夸其談。在面試的時候，知之為知之，不知為不知，對于不清楚的知識點，要勇敢承認，千萬別不懂裝懂。通常當應聘者說自己很懂某一領域的時候，面試官都會跟進幾個問題。如果應聘者在不懂裝懂，面試官遲早會發現，他可能就會覺得應聘者在其他的地方也有浮報虛夸的成分，這將是得不償失的。 有意向加入外企的應聘者要注意提高自己英文交流的能力。不少外企的面試部分甚至全部采用英語面試，這對英語的要求就很高。我們通過了英語的四六級考試未必能用英語對話。如果覺得自己英語的聽說能力還不夠好，建議花更多的時間來提高自己的聽力。英語面試中最重要的是我們要聽懂面試官的問題。通常采用英文面試的面試官自己的英語都比較好，即使我們的發音不夠標準，對方一般也能聽懂。這和我們能聽懂普通話不標準的老外說中文的道理是一樣的。但如果面試官的問題沒有聽明白，那我們就是說得再清楚也無濟于事了。 2．學習能力 計算機是一門更新速度很快的學科，每年都有新的技術不斷涌現。因此作為這個領域從業人員的軟件工程師們需要要具備很強的學習能力，否則時間一長就會跟不上技術進步的步伐。也正是因為這個原因，IT公司在面試的時候，面試官都會重視應聘者的學習能力。只有具備很強的學習能力及學習愿望的人，才能不斷完善自己的知識結構，不斷學習新的先進技術，讓自己的職業生涯保持長久的生命力。 通常面試官有兩種辦法考查應聘者的學習能力。第一種方法是詢問應聘者最近在看什么書或者在做什么項目、從中學到了哪些新技術。面試官可以用這個問題了解應聘者的學習愿望和學習能力。學習能力強的人對各種新技術充滿了興趣，隨時學習、吸收新知識，并把知識轉換為自己的技能。第二種方法是拋出一個新概念，接下來觀察應聘者能不能在較短時間內理解這個新概念并解決相關的問題。本書收集的面試題涉及諸如數組的旋轉（面試題8）、二叉樹的鏡像（面試題19）、丑數（面試題34）、逆序對（面試題36）等新概念。當面試官提出這些新概念的時候，他期待應聘者能夠通過思考、提問、再思考的過程，理解它們并最終解決問題。 3．善于學習、溝通的人也善于提問 面試官有一個很重要的任務就是考查應聘者的學習愿望及學習能力。學習能力怎么體現呢？面試官提出一個新概念，應聘者沒有聽說過它，于是他在已有的理解的基礎上提出進一步的問題，得到面試官的答復之后，思考再提問，幾個來回之后掌握了這個概念。這個過程能夠體現應聘者的學習能力。通常學習能力強的人具有主動積極的態度，對未知的領域有強烈的求知欲望。因此建議應聘者在面試過程中遇到不明白的地方多提問，這樣面試官就會覺得你態度積極、求知欲望強烈，會給面試結果加分。 面試小提示： 面試是一個雙向交流的過程，面試官可以問應聘者問題，同樣應聘者也可以向面試官提問。如果應聘者能夠針對面試題主動地提出幾個高質量的問題，面試官就會覺得他有很強的溝通能力和學習能力。 舉個例子，Google曾經有一道面試題：找出第1500個丑數。很多人都不知道丑數是什么。不知道怎么辦？面試官就坐在對面，可以問他。面試官會告訴你只含有2、3、5三個因子的數就是丑數。你聽了后，覺得聽明白了，但不太確定，于是可以舉幾個例子并讓面試官確認你的理解是不是正確：6、8、10、12都是丑數，但14就不是，對嗎？當面試官給出肯定的答復，你就知道自己的理解是對。問題問的是第1500個丑數，與順序有關。可是哪個數字是第一個丑數呢，1是不是第一個？這個你可能也不能確定，怎么辦？還是問面試官，他會告訴你1是或者不是丑數。題目是他出的，他有責任把題目解釋清楚。 有些面試官故意一開始不把題目描述清楚，讓題目存在一定的二義性。他期待應聘者能夠一步步通過提問來弄明白題目的要求。這也是在考查應聘者的溝通能力。為什么要這樣考查？因為實際工作也是這樣，不是一開始項目需求就定義得很清楚，程序員需要多次與項目經理甚至客戶反復溝通才能把需求弄清楚。如果沒有一定的溝通能力，當程序員面對一個模糊的客戶需求時他就會覺得無從下手。 比如最近很流行的一個面試題，面試官最開始問：如何求樹中兩個結點的最低公共祖先。此時面試官對題目中的樹的特點完全沒有給出描述，他希望應聘者在聽到問題后會提出幾個問題，比如這棵樹是二叉樹還是普通的樹。 如果面試官說是二叉樹，應聘者可以繼續問該樹是不是排序的二叉樹。面試官回答是排序的。聽到這里，應聘者才能確定思路：從樹的根結點出發遍歷樹，如果當前結點都大于輸入的兩個結點，則下一步遍歷當前結點的左子樹；如果當前結點小于輸入的兩個結點，則下一步遍歷當前結點的右子樹。一直遍歷到當前結點比一個輸入結點大而比另一個小的時候，此時當前結點就是符合要求的最低公共祖先。 在應聘者問樹是不是二叉樹的時候如果面試官回答是任意的樹，此時應聘者可以接著提問在樹結點中有沒有指向父結點的指針。如果面試官給出肯定的回答，也就是樹的結點中有指向父結點的指針，此時從輸入的結點出發，沿著指向父結點的指針一直到樹的根結點，可以看做一個鏈表，因此這個題目的解法就和求兩個鏈表的第一個公共結點的解法是一樣的了。如果面試官給出的是否定的回答，也就是樹的結點沒有指向父結點的指針，那么我們可以在遍歷的時候用一個棧來保存從根結點到當前結點的路徑，最終把它轉化成求兩個路徑的最后一個公共結點。詳細的解題過程請參考本書的7.2節。 面試官給出不同的條件，這將是3個完全不一樣的題目。如果一開始應聘者沒有弄清楚面試官的意圖就貿然動手解題，那結果很有可能是離題千里。從中我們也可以看出在面試過程中溝通的重要性。當覺得題目的條件、要求不夠明確的時候，我們一定要多提問以消除自己的疑惑。 6.3 知識遷移能力 所謂學習能力，很重要的一點就是根據已經掌握的知識、技術，能夠迅速學習、理解新的技術并能運用到實際工作中去。大部分新的技術都不是憑空產生的，而是在已有技術的基礎上發展起來的。這就要求我們能夠把對已有技術的理解遷移到學習新技術的過程中去，也就是要具備很強的知識遷移能力。以學習編程語言為例，如果全面理解了C++的面向對象的思想，那么學習下一門面向對象的語言Java就不會很難。在深刻理解了Java的垃圾回收機制之后，再去學習另外一門托管語言比如C#，也會很容易。 面試官考查知識遷移能力的一個方法是把經典的問題稍作變換。這個時候面試官期待應聘者能夠找到和經典問題的聯系，并從中受到啟發把解決經典問題的思路遷移過來解決新的問題。比如如果遇到面試題38“數字在排序數組中出現的次數”，我們看到“排序數組”就可以想到二分查找算法。通常二分查找算法用來在一個排序數組中查找一個數字。我們可以把二分查找的思想遷移過來稍作變換，用二分查找算法在排序數組中查找重復數字的第一個和最后一個，從而得到數字在數組中出現的次數。 面試官考查知識遷移能力的另一個方法就是先問一個簡單的問題，在應聘者解答完這個簡單的問題之后再追問一個相關的同時難度也更大的問題。這個時候面試官希望應聘者能夠總結前面解決簡單問題的經驗，把前面的思路、方法遷移過來。比如在面試題40“數組中只出現一次的數字”中，面試官先問一個簡單的問題即數組中只有一個數字只出現一次的情況。在應聘者想出用異或的辦法找到這個只出現一次的數字之后，他再追問如果數組中有兩個數字只出現一次，該怎么找出這兩個數字？這個時候應聘者要從前面的思路中得到啟發：既然有辦法找到數組中只出現一次的一個數字，那當數組中有兩個數字只出現一次的時候，我們可以把整個數組一分為二，每個子數組中包含一個只出現一次的數字，這樣我們就能在兩個子數組中分別找到那兩個只出現一次的數字。接下來我們就可以集中精力去想辦法把數組一分為二，這樣就能找到解決問題的竅門，整個題目的難度系數就降低了不少。 知識遷移能力的一種通俗的說法是“舉一反三”的能力。我們在去面試之前，通常都會看一些經典的面試題。然而題目總是做不完的，我們不可能把所有的面試題都準備一遍。因此更重要的是每做一道面試題的時候，都要總結這道題的解法有什么特點，有哪些思路是可以應用到同類型的題目中去的。比如為了解決面試題“翻轉單詞順序”，我們先翻轉整個句子的所有字符，再分別翻轉每個單詞中的字符。這樣多次翻轉字符的思路也可以運用到面試題“左旋轉字符串”中（面試題42）。在解決面試題28“字符串的排列”之后，我們發現“八皇后問題”其實歸根到底就是數組的排列問題。本書中很多章節在分析了一道題之后，列舉了和這道題相關的題目，讀者可以通過分析這些題目的相關性來提高舉一反三的能力。 面試題38：數字在排序數組中出現的次數 題目：統計一個數字在排序數組中出現的次數。例如輸入排序數組{1,2,3,3,3,3,4,5}和數字3，由于3在這個數組中出現了4次，因此輸出4。 既然輸入的數組是排序的，那么我們很自然地就能想到用二分查找算法。在題目給出的例子中，我們可以先用二分查找算法找到一個3。由于3可能出現多次，因此我們找到的3的左右兩邊可能都有3，于是我們在找到的3的左右兩邊順序掃描，分別找出第一個3和最后一個3。因為要查找的數字在長度為n的數組中有可能出現O（n）次，所以順序掃描的時間復雜度是O（n）。因此這種算法的效率和直接從頭到尾順序掃描整個數組統計3出現的次數的方法是一樣的。顯然，面試官不會滿意這個算法，他會提示我們還有更快的算法。 接下來我們思考如何更好地利用二分查找算法。假設我們是統計數字k在排序數組中出現的次數。在前面的算法中時間主要消耗在如何確定重復出現的數字的第一個k和最后一個k的位置上，有沒有可能用二分查找算法直接找到第一個k及最后一個k呢？ 我們先分析如何用二分查找算法在數組中找到第一個k。二分查找算法總是先拿數組中間的數字和k作比較。如果中間的數字比k大，那么k只有可能出現在數組的前半段，下一輪我們只在數組的前半段查找就可以了。如果中間的數字比k小，那么k只有可能出現在數組的后半段，下一輪我們只在數組的后半段查找就可以了。如果中間的數字和k相等呢？我們先判斷這個數字是不是第一個k。如果位于中間數字的前面一個數字不是k，此時中間的數字剛好就是第一個k。如果中間數字的前面一個數字也是k，也就是說第一個k肯定在數組的前半段，下一輪我們仍然需要在數組的前半段查找。 基于這個思路，我們可以很容易地寫出遞歸的代碼找到排序數組中的第一個k：  在函數GetFirstK中，如果數組中不包含數字k，那么返回-1。如果數組中包含至少一個k，那么返回第一個k在數組中的下標。 我們可以用同樣的思路在排序數組中找到最后一個k。如果中間數字比k大，那么k只能出現在數組的前半段。如果中間數字比k小，k就只能出現在數組的后半段。如果中間數字等于k呢？我們需要判斷這個k是不是最后一個k，也就是中間數字的下一個數字是不是也等于k。如果下一個數字不是k，則中間數字就是最后一個k了；否則下一輪我們還是要在數組的后半段中去查找。我們同樣可以基于遞歸寫出如下代碼：  和函數GetFirstK類似，如果數組中不包含數字k，那么GetLastK返回-1；否則返回最后一個k在數組中的下標。 在分別找到第一個k和最后一個k的下標之后，我們就能計算出k在數組中出現的次數了。相應的代碼如下：  在上述代碼中，GetFirstK和GetLastK都是用二分查找法在數組中查找一個合乎要求的數字，它們的時間復雜度都是O（logn），因此GetNumberOfK的總的時間復雜度也只有O（logn）。 源代碼： 本題完整的源代碼詳見38\_NumberOfK項目。 測試用例： ● 功能測試（數組中包含查找的數字，數組中沒有查找的數字，查找的數字在數組中出現一次/多次）。 ● 邊界值測試（查找數組中的最大值、最小值，數組中只有一個數字） ● 特殊輸入測試（表示數組的指針為NULL指針）。 本題考點： ● 考查應聘者的知識遷移能力。我們都知道二分查找算法可以用來在排序數組中查找一個數字。應聘者如果能夠運用知識遷移能力，把問題轉換成用二分查找算法查找重復數字的第一個和最后一個，那么這個問題也就解決了一大半。 ● 考查應聘者對二分查找算法的理解程度。這道題實際上是二分查找算法的加強版。只有對二分查找算法有著深刻的理解，應聘者才有可能解決這個問題。 面試題39：二叉樹的深度 題目一：輸入一棵二叉樹的根結點，求該樹的深度。從根結點到葉結點依次經過的結點（含根、葉結點）形成樹的一條路徑，最長路徑的長度為樹的深度。 二叉樹的結點定義如下：  例如，圖6.1中的二叉樹的深度為4，因為它從根結點到葉結點最長的路徑包含4個結點（從根結點1開始，經過結點2和結點5，最終到達葉結點7）。  圖6.1 深度為4的二叉樹 在本題中面試官給出了一種樹的深度的定義，我們可以根據這個定義去得到樹的所有路徑，也就能得到最長的路徑及它的長度。在面試題25“二叉樹中和為某一值的路徑”中我們詳細討論了如何記錄樹中的路徑。這種思路的代碼量比較大，我們可以嘗試更加簡潔的方法。 我們還可以從另外一個角度來理解樹的深度。如果一棵樹只有一個結點，它的深度為1。如果根結點只有左子樹而沒有右子樹，那么樹的深度應該是其左子樹的深度加1；同樣如果根結點只有右子樹而沒有左子樹，那么樹的深度應該是其右子樹的深度加1。如果既有右子樹又有左子樹，那該樹的深度就是其左、右子樹深度的較大值再加1。比如在圖6.1的二叉樹中，根結點為1的樹有左右兩個子樹，其左右子樹的根結點分別為結點2和3。根結點為2的左子樹的深度為3，而根結點為3的右子樹的深度為2，因此根結點為1的樹的深度就是4。 這個思路用遞歸的方法很容易實現，只需對遍歷的代碼稍作修改即可。參考代碼如下：  源代碼： 本題完整的源代碼詳見39\_1\_TreeDepth項目。 測試用例： ● 功能測試（輸入普通的二叉樹，二叉樹中所有結點都沒有左/右子樹）。 ● 特殊輸入測試（二叉樹只有一個結點，二叉樹的頭結點為NULL指針）。 只要應聘者對二叉樹這一數據結構很熟悉，就能很快寫出上面的代碼。如果公司對編程能力有較高的要求，面試官可能會追加一個與前面問題相關但難度更大的問題。比如，在應聘者做完上面的問題之后，面試官追問： 題目二：輸入一棵二叉樹的根結點，判斷該樹是不是平衡二叉樹。如果某二叉樹中任意結點的左右子樹的深度相差不超過1，那么它就是一棵平衡二叉樹。例如，圖6.1中的二叉樹就是一棵平衡二叉樹。 需要重復遍歷結點多次的解法，簡單但不足以打動面試官 有了求二叉樹的深度的經驗之后再解決這個問題，我們很容易就能想到一個思路：在遍歷樹的每個結點的時候，調用函數TreeDepth得到它的左右子樹的深度。如果每個結點的左右子樹的深度相差都不超過1，按照定義它就是一棵平衡的二叉樹。這種思路對應的代碼如下：  上面的代碼固然簡潔，但我們也要注意到由于一個結點會被重復遍歷多次，這種思路的時間效率不高。例如在函數IsBalance中輸入圖6.1中的二叉樹，我們將首先判斷根結點（結點1）是不是平衡的。此時我們往函數TreeDepth輸入左子樹的根結點（結點2）時，需要遍歷結點4、5、7。接下來判斷以結點2為根結點的子樹是不是平衡樹的時候，仍然會遍歷結點4、5、7。毫無疑問，重復遍歷同一個結點會影響性能。接下來我們尋找不需要重復遍歷的算法。 每個結點只遍歷一次的解法，正是面試官喜歡的 如果我們用后序遍歷的方式遍歷二叉樹的每一個結點，在遍歷到一個結點之前我們就已經遍歷了它的左右子樹。只要在遍歷每個結點的時候記錄它的深度（某一結點的深度等于它到葉節點的路徑的長度），我們就可以一邊遍歷一邊判斷每個結點是不是平衡的。下面是這種思路的參考代碼：  我們只需給上面的函數傳入二叉樹的根結點及一個表示結點深度的整型變量即可：  在上面的代碼中，我們用后序遍歷的方式遍歷整棵二叉樹。在遍歷某結點的左右子結點之后，我們可以根據它的左右子結點的深度判斷它是不是平衡的，并得到當前結點的深度。當最后遍歷到樹的根結點的時候，也就判斷了整棵二叉樹是不是平衡二叉樹。 源代碼： 本題完整的源代碼詳見39\_2\_BalancedBinaryTree項目。 測試用例： ● 功能測試（平衡的二叉樹，不是平衡的二叉樹，二叉樹中所有結點都沒有左/右子樹）。 ● 特殊輸入測試（二叉樹中只有一個結點，二叉樹的頭結點為NULL指針）。 本題考點： ● 考查對二叉樹的理解及編程能力。這兩個題的解法實際都只是樹的遍歷算法的應用。 ● 考查對新概念的學習能力。面試官提出一個新的概念即樹的深度，這就要求我們在較短的時間內理解這個概念并解決相關的問題。這是一種常見的面試題型。能在較短時間內掌握、理解新概念的能力，就是一種學習能力。 ● 考查知識遷移的能力。如果面試官先問如何求二叉樹的深度，再問如何判斷一棵二叉樹是不是平衡的，應聘者應該從求二叉樹深度的分析過程中得到啟發，找到判斷平衡二叉樹的突破口。 面試題40：數組中只出現一次的數字 題目：一個整型數組里除了兩個數字之外，其他的數字都出現了兩次。請寫程序找出這兩個只出現一次的數字。要求時間復雜度是O（n），空間復雜度是O（1）。 例如輸入數組{2,4,3,6,3,2,5,5}，因為只有4、6這兩個數字只出現一次，其他數字都出現了兩次，所以輸出4和6。 這是一個比較難的題目，很少有人能在面試的時候不需要提示一下子想到最好的解決辦法。一般當應聘者想了幾分鐘后還沒有思路，面試官會給出一些提示。面試官很有可能會說：你可以先考慮這個數組中只有一個數字只出現一次，其他的都出現了兩次，怎么找出這個數字？ 這兩個題目都在強調一個（或兩個）數字只出現一次，其他的出現兩次。這有什么意義呢？我們想到異或運算的一個性質：任何一個數字異或它自己都等于0。也就是說，如果我們從頭到尾依次異或數組中的每一個數字，那么最終的結果剛好是那個只出現一次的數字，因為那些成對出現兩次的數字全部在異或中抵消了。 想明白怎么解決這個簡單問題之后，我們再回到原始的問題，看看能不能運用相同的思路。我們試著把原數組分成兩個子數組，使得每個子數組包含一個只出現一次的數字，而其他數字都成對出現兩次。如果能夠這樣拆分成兩個數組，我們就可以按照前面的辦法分別找出兩個只出現一次的數字了。 我們還是從頭到尾依次異或數組中的每一個數字，那么最終得到的結果就是兩個只出現一次的數字的異或結果。因為其他數字都出現了兩次，在異或中全部抵消了。由于這兩個數字肯定不一樣，那么異或的結果肯定不為0，也就是說在這個結果數字的二進制表示中至少就有一位為1。我們在結果數字中找到第一個為1的位的位置，記為第n位。現在我們以第n位是不是1為標準把原數組中的數字分成兩個子數組，第一個子數組中每個數字的第n位都是1，而第二個子數組中每個數字的第n位都是0。由于我們分組的標準是數字中的某一位是1還是0，那么出現了兩次的數字肯定被分配到同一個子數組。因為兩個相同的數字的任意一位都是相同的，我們不可能把兩個相同的數字分配到兩個子數組中去，于是我們已經把原數組分成了兩個子數組，每個子數組都包含一個只出現一次的數字，而其他數字都出現了兩次。我們已經知道如何在數組中找出唯一一個只出現一次數字，因此到此為止所有的問題都已經解決了。 舉個例子，假設輸入數組{2,4,3,6,3,2,5,5}。當我們依次對數組中的每一個數字做異或運算之后，得到的結果用二進制表示是0010。異或得到結果中的倒數第二位是1，于是我們根據數字的倒數第二位是不是1分為兩個數組。第一個子數組{2,3,6,3,2}中所有數字的倒數第二位都是1，而第二個子數組{4,5,5}中所有數字的倒數第二位都是0。接下來只要分別對這兩個子數組求異或，就能找出第一個子數組中只出現一次的數字是6，而第二個子數組中只出現一次的數字是4。 想清楚整個過程之后再寫代碼就不難了。下面是參考代碼：  在上述代碼中，FindFirstBitIs1用來在整數num的二進制表示中找到最右邊是1的位，IsBit1的作用是判斷在num的二進制表示中從右邊數起的indexBit位是不是1。 源代碼： 本題完整的源代碼詳見40\_NumbersAppearOnce項目。 測試用例： 功能測試（數組中多對重復的數字，數組中沒有重復的數字） 本題考點： ● 考查知識遷移能力。只有一個數字出現一次這個簡單的問題，很多應聘者都能想到解決辦法。能不能把解決簡單問題的思路遷移到復雜問題上，是應聘者能否通過這輪面試的關鍵。 ● 考查對二進制和位運算的理解。 面試題41：和為s的兩個數字VS和為s的連續正數序列 題目一：輸入一個遞增排序的數組和一個數字s，在數組中查找兩個數，使得它們的和正好是s。如果有多對數字的和等于s，輸出任意一對即可。 例如輸入數組{1、2、4、7、11、15}和數字15。由于4＋11＝15，因此輸出4和11。 面試的時候，很重要的一點是應聘者要表現出很快的反應能力。只要想到一個方法，應聘者就可以馬上告訴面試官，即使這個方法不一定是最好的。比如這個問題，很多人都能立即想到O（n2）的方法，也就是先在數組中固定一個數字，再依次判斷數組中其余的n－1個數字與它的和是不是等于s。面試官會告訴我們這不是最好的辦法。不過這沒有關系，至少面試官知道我們的思維還是比較敏捷的。 接著我們尋找更好的算法。我們先在數組中選擇兩個數字，如果它們的和等于輸入的s，我們就找到了要找的兩個數字。如果和小于s呢？我們希望兩個數字的和再大一點。由于數組已經排好序了，我們可以考慮選擇較小的數字后面的數字。因為排在后面的數字要大一些，那么兩個數字的和也要大一些，就有可能等于輸入的數字s了。同樣，當兩個數字的和大于輸入的數字的時候，我們可以選擇較大數字前面的數字，因為排在數組前面的數字要小一些。 我們以數組{1、2、4、7、11、15}及期待的和15為例詳細分析一下這個過程。首先定義兩個指針，第一個指針指向數組的第一個（也是最小的）數字1，第二個指針指向數組的最后一個（也是最大的）數字15。這兩個數字的和16大于15，因此我們把第二個指針向前移動一個數字，讓它指向11。這個時候兩個數字1與11的和是12，小于15。接下來我們把第一個指針向后移動一個數字指向2。此時兩個數字2與11的和13，還是小于15。我們再一次向后移動第一個指針，讓它指向數字4。數字4、11的和是15，正是我們期待的結果。表6.1總結了在數組{1、2、4、7、11、15}中查找和為15的數對的過程。 表6.1 在數組{1、2、4、7、11、15} 中查找和為15的數對  這一次面試官會首肯我們的思路，于是就可以動手寫代碼了。下面是一段參考代碼：  在上述代碼中，ahead為較小的數字的下標，behind為較大的數字的下標。由于數組是排序的，因此較小數字一定位于較大數字的前面，這就是while循環繼續的條件是ahead>behind的原因。代碼中只有一個while循環從兩端向中間掃描數組，因此這種算法的時間復雜度是O（n）。 源代碼： 本題完整的源代碼詳見41\_1\_TwoNumbersWithSum項目。 測試用例： ● 功能測試（數組中存在和為s的兩個數，數組中不存在和為s的兩個數） ● 特殊輸入測試（表示數組的指針為NULL指針） 看到應聘者比較輕松地解決了問題還有時間剩余，有些面試官喜歡追問和前面問題相關但稍微難一些的問題。比如下面的問題就是一個例子： 題目二：輸入一個正數s，打印出所有和為s的連續正數序列（至少含有兩個數）。例如輸入15，由于1＋2＋3＋4＋5＝4＋5＋6＝7＋8＝15，所以結果打印出3個連續序列1～5、4～6和7～8。 有了解決前面問題的經驗，我們也考慮用兩個數small和big分別表示序列的最小值和最大值。首先把small初始化為1，bug初始化為2。如果從small到big的序列的和大于s，我們可以從序列中去掉較小的值，也就是增大small的值。如果從small到big的序列的和小于s，我們可以增大big，讓這個序列包含更多的數字。因為這個序列至少要有兩個數字，我們一直增加small到（1＋s）/2為止。 以求和為9的所有連續序列為例，我們先把small初始化為1，big初始化為2。此時介于small和big之間的序列是{1,2}，序列的和為3，小于9，所以我們下一步要讓序列包含更多的數字。我們把big增加1變成3，此時序列為{1,2,3}。由于序列的和是6，仍然小于9，我們接下來再增加big變成4，介于small和big之間的序列也隨之變成{1,2,3,4}。由于序列的和10大于9，我們要刪去去序列中的一些數字，于是我們增加small變成2，此時得到的序列是{2,3,4}，序列的和正好是9。我們找到了第一個和為9的連續序列，把它打印出來。接下來我們再增加big，重復前面的過程，可以找到第二個和為9的連續序列{4,5}。可以用表6.2總結整個過程。 表6.2 求取和為9的連續序列的過程  形成了清晰的解題思路之后，我們就可以開始寫代碼了。下面是這種思路的參考代碼：  在前面的代碼中，求連續序列的和應用了一個小技巧。通常我們可以用循環求一個連續序列的和，但考慮到每一次操作之后的序列和操作之前的序列相比大部分數字都是一樣的，只是增加或者減少了一個數字，因此我們可以在前一個序列的和的基礎上求操作之后的序列的和。這樣可以減少很多不必要的運算，從而提高代碼的效率。 源代碼： 本題完整的源代碼詳見41\_2\_ContinuesSquenceWithSum項目。 測試用例： ● 功能測試（存在和為s的連續序列，如9、100等；不存在和為s的連續序列，如4、0）。 ● 邊界值測試（連續序列的最小和3） 本題考點： ● 考查思考復雜問題的思維能力。應聘者如果能夠通過一兩個具體的例子找到規律，解決這個問題就容易多了。 ● 考查知識遷移的能力。應聘者面對第二個問題的時候，能不能把解決第一個問題的思路應用到新的題目上，是面試官考查知識遷移能力的重要指標。 面試題42：翻轉單詞順序 VS左旋轉字符串 題目一：輸入一個英文句子，翻轉句子中單詞的順序，但單詞內字符的順序不變。為簡單起見，標點符號和普通字母一樣處理。例如輸入字符串"I am a student. "，則輸出"student. a am I"。 這個題目流傳甚廣，很多公司都多次拿來作面試題，很多應聘者也多次在各種博客或者書籍上看到過通過兩次翻轉字符串的解法，于是很快就可以跟面試官解釋清楚解題思路：第一步翻轉句子中所有的字符。比如翻轉"I am a student. "中所有的字符得到".tneduts a ma I"，此時不但翻轉了句子中單詞的順序，連單詞內的字符順序也被翻轉了。第二步再翻轉每個單詞中字符的順序，就得到了"student. a am I"。這正是符合題目要求的輸出。 這種思路的關鍵在于實現一個函數以翻轉字符串中的一段。下面的函數Reverse可以完成這一功能：  接著我們可以用這個函數先翻轉整個句子，再翻轉句子中的每個單詞。這種思路的參考代碼如下：  在英語句子中，單詞被空格符號分隔，因此我們可以通過掃描空格來確定每個單詞的起始和終止位置。在上述代碼的翻轉每個單詞階段，指針pBegin指向單詞的第一個字符，而pEnd指向單詞的最后一個字符。 源代碼： 本題完整的源代碼詳見42\_1\_ReverseWordsInSentence項目。 測試用例： ● 功能測試（句子中有多個單詞，句子中只有一個單詞）。 ● 特殊輸入測試（字符串指針為NULL指針、字符串的內容為空、字符串中只有空格）。 有經驗的面試官看到一個應聘者幾乎不假思索就能想出一種比較巧妙的算法，就會覺得他之前可能見過這個題目。這個時候很多面試官都會再問一個問題，以考查他是不是真的理解了這種算法。面試官一個常見的考查辦法就是問一個類似的但更加難一點的問題。以這道題為例，如果面試官覺得應聘者之前看過這個思路，那他可能再問第二個問題： 題目二：字符串的左旋轉操作是把字符串前面的若干個字符轉移到字符串的尾部。請定義一個函數實現字符串左旋轉操作的功能。比如輸入字符串"abcdefg"和數字2，該函數將返回左旋轉2位得到的結果"cdefgab"。 要找到字符串旋轉時每個字符移動的規律，不是一件輕易的事情。那我們是不是可以從解決第一個問題的思路中找到啟發？在第一個問題中，如果輸入的字符串之中只有兩個單詞，比如"hello world"，那么翻轉這個句子中的單詞順序就得到了"world hello"。比較這兩個字符串，我們是不是可以把"world hello"看成是把原始字符串"hello world"的前面若干個字符轉移到后面？也就是說這兩個問題是非常相似的，我們同樣可以通過翻轉字符串的辦法來解決第二個問題。 以"abcdefg"為例，我們可以把它分為兩部分。由于想把它的前兩個字符移到后面，我們就把前兩個字符分到第一部分，把后面的所有字符都分到第二部分。我們先分別翻轉這兩部分，于是就得到"bagfedc"。接下來我們再翻轉整個字符串，得到的"cdefgab"剛好就是把原始字符串左旋轉2位的結果。 通過前面的分析，我們發現只需要調用3次前面的Reverse函數就可以實現字符串的左旋轉功能。參考代碼如下：  想清楚思路之后再寫代碼是一件很容易的事情，但我們也不能掉以輕心。面試官在檢查與字符串相關的代碼時經常會發現兩種問題：一是輸入空指針NULL時程序會崩潰；二是內存訪問越界的問題，也就是試圖訪問不屬于字符串的內存。例如如果輸入的n小于0，指針pStr+n指向的內存就不屬于字符串。如果我們不排除這種情況，試圖訪問不屬于字符串的內存就會留下嚴重的內存越界的安全隱患。在前面的代碼中，我們添加了兩個if判斷語句就是為了防止出現這兩種問題。 源代碼： 本題完整的源代碼詳見42\_2\_LeftRotateString項目。 測試用例： ● 功能測試（把長度為n的字符串左旋轉0個字符、1個字符、2個字符、n－1個字符、n個字符、n＋1個字符）。 ● 特殊輸入測試（字符串的指針為NULL指針）。 本題考點： ● 考查知識遷移的能力。當面試的時候遇到第二個問題，而之前我們做過“翻轉句子中單詞的順序”這個題目，那如果能夠把多次翻轉字符串的思路遷移過來，就能很輕易地解決字符串左旋轉的問題。 ● 考查對字符串的編程能力。 6.4 抽象建模能力 計算機只是一種工具，它的作用是用來解決實際生產生活中的問題。程序員的工作就是把各種現實問題抽象成數學模型并用計算機的編程語言表達出來，因此有些面試官喜歡從日常生活中抽取提煉出問題考查應聘者是否能建立數學模型并解決問題。要想順利解決這種類型的問題，應聘者除了需要具備扎實的數學基礎和編程能力之外，還需要具有敏銳的洞察力和豐富的想象力。 建模的第一步是選擇合理的數據結構來表述問題。實際生產生活中的問題千變萬化，而常用的數據結構卻只有有限的幾種。我們在根據問題的特點綜合考慮性能、編程難度等因素之后，選擇最合適的數據結構來表達問題，也就是建立模型。比如在面試題44“撲克牌的順子”中，我們用一個數組表示一副牌，用11、12和13分別表示J、Q、K并且用0表示大小王。在面試題45“圓圈中最后剩下的數字”中，我們可以用一個環形鏈表模擬一個圓圈。 建模的第二步是分析模型中的內在規律，并用編程語言表述這種規律。我們只有對現實問題進行深入細微的觀察分析之后，才能找到模型中的規律，才有可能編程解決問題。例如在本書2.4.2節提到的“青蛙跳臺階”問題中，它內在的規律是斐波那契數列。再比如面試題43“n個骰子的點數”問題，其本質是求數列f（n）＝f（n－1）＋f（n－2）＋f（n－3）＋f（n－4）＋f（n－5）＋f（n－6）。找到這個規律之后，我們就可以分別用遞歸和循環兩種不同的方法去寫代碼。然而，并不是所有問題的內在規律都是顯而易見的。在面試題45“圓圈中最后剩下的數字”中，我們經過嚴密的數學分析之后才能找到每次從圓圈中刪除的數字的規律，從而找到一種不需要輔助環形鏈表的快速方法來解決問題。 面試題43：n個骰子的點數 題目：把n個骰子扔在地上，所有骰子朝上一面的點數之和為s。輸入n，打印出s的所有可能的值出現的概率。 玩過麻將的人都知道，骰子一共6個面，每個面上都有一個點數，對應的是1～6之間的一個數字。所以n個骰子的點數和的最小值為n，最大值為6n。另外根據排列組合的知識，我們還知道n個骰子的所有點數的排列數為6n。要解決這個問題，我們需要先統計出每一個點數出現的次數，然后把每一個點數出現的次數除以6n，就能求出每個點數出現的概率。 解法一：基于遞歸求骰子點數，時間效率不夠高 現在我們考慮如何統計每一個點數出現的次數。要想求出n個骰子的點數和，可以先把n個骰子分為兩堆：第一堆只有一個，另一個有n－1個。單獨的那一個有可能出現從1到6的點數。我們需要計算從1到6的每一種點數和剩下的n－1個骰子來計算點數和。接下來把剩下的n－1個骰子還是分成兩堆，第一堆只有一個，第二堆有n－2個。我們把上一輪那個單獨骰子的點數和這一輪單獨骰子的點數相加，再和剩下的n－2個骰子來計算點數和。分析到這里，我們不難發現這是一種遞歸的思路，遞歸結束的條件就是最后只剩下一個骰子。 我們可以定義一個長度為6n－n＋1的數組，和為s的點數出現的次數保存到數組第s－n個元素里。基于這種思路，我們可以寫出如下代碼：  上述思路很簡潔，實現起來也容易。但由于是基于遞歸的實現，它有很多計算是重復的，從而導致當number變大時性能慢得讓人不能接受。關于遞歸的性能討論，詳見本書2.4.2節。 解法二：基于循環求骰子點數，時間性能好 可以換一種思路來解決這個問題。我們可以考慮用兩個數組來存儲骰子點數的每一個總數出現的次數。在一次循環中，第一個數組中的第n個數字表示骰子和為n出現的次數。在下一循環中，我們加上一個新的骰子，此時和為n的骰子出現的次數應該等于上一次循環中骰子點數和為n－1、n－2、n－3、n－4、n－5與n－6的次數的總和，所以我們把另一個數組的第n個數字設為前一個數組對應的第n－1、n－2、n－3、n－4、n－5與n－6之和。基于這個思路，我們可以寫出如下代碼：  在上述代碼中，我們定義了兩個數組pProbabilities\[0\]和pProbabilities\[1\]來存儲骰子的點數之和。在一輪循環中，一個數組的第n項等于另一數組的第n－1、n－2、n－3、n－4、n－5以及n－6項的和。在下一輪循環中，我們交換這兩個數組（通過改變變量flag實現）再重復這一計算過程。 值得注意的是，上述代碼沒有在函數里把一個骰子的最大點數硬編碼（hard code）為6，而是用一個變量g\_maxValue來表示。這樣做的好處是，如果某個廠家生產了其他點數的骰子，我們只需要在代碼中修改一個地方，擴展起來很方便。如果在面試的時候我們能對面試官提起對程序擴展性的考慮，一定能給面試官留下很好的印象。 源代碼： 本題完整的源代碼詳見43\_DicesProbability項目。 測試用例： ● 功能測試（1、2、3、4個骰子的各點數的概率）。 ● 特殊輸入測試（輸入0）。 ● 性能測試（輸入較大的數字，比如11）。 本題考點： ● 數學建模的能力。不管采用哪種思路解決問題，我們都要先想到用數組來存放n個骰子的每一個點數出現的次數，并通過分析點數的規律建立模型并最終找到解決方案。 ● 考查對遞歸和循環的性能的理解。 面試題44：撲克牌的順子 題目：從撲克牌中隨機抽5張牌，判斷是不是一個順子，即這5張牌是不是連續的。2～10為數字本身，A為1，J為11，Q為12，K為13，而大、小王可以看成任意數字。 我們需要把撲克牌的背景抽象成計算機語言。不難想象，我們可以把5張牌看成由5個數字組成的數組。大、小王是特殊的數字，我們不妨把它們都定義為0，這樣就能和其他撲克牌區分開來了。 接下來我們分析怎樣判斷5個數字是不是連續的，最直觀的方法是把數組排序。值得注意的是，由于0可以當成任意數字，我們可以用0去補滿數組中的空缺。如果排序之后的數組不是連續的，即相鄰的兩個數字相隔若干個數字，但只要我們有足夠的0可以補滿這兩個數字的空缺，這個數組實際上還是連續的。舉個例子，數組排序之后為{0，1，3，4，5}，在1和3之間空缺了一個2，剛好我們有一個0，也就是我們可以把它當成2去填補這個空缺。 于是我們需要做3件事情：首先把數組排序，再統計數組中0的個數，最后統計排序之后的數組中相鄰數字之間的空缺總數。如果空缺的總數小于或者等于0的個數，那么這個數組就是連續的；反之則不連續。 最后，我們還需要注意一點：如果數組中的非0數字重復出現，則該數組不是連續的。換成撲克牌的描述方式就是如果一副牌里含有對子，則不可能是順子。 基于這個思路，我們可以寫出如下代碼：  為了讓代碼顯得簡潔，上述代碼調用C的庫函數qsort排序。可能有人擔心qsort是O（nlogn）的時間復雜度，還不夠快。由于撲克牌的值出現在0～13之間，我們可以定義一個長度為14的哈希表，這樣在O（n）時間就能完成排序（本書2.4.1節有這種思路的例子）。通常我們認為不同級別的時間復雜度只有當n足夠大的時候才有意義。由于本題中數組的長度是固定的，只有5張牌，那么O（n）和O（nlogn）不會有多少區別，我們可以選用簡潔易懂的方法來實現算法。 源代碼： 本題完整的源代碼詳見44\_ContinousCards項目。 測試用例： ● 功能測試（抽出的牌中有一個或者多個大、小王，抽出的牌中沒有大、小王，抽出的牌中有對子）。 ● 特殊輸入測試（輸入NULL指針）。 本題考點： 考查抽象建模能力。這個題目要求我們把熟悉的撲克牌轉換為數組，把找順子的過程通過排序、計數等步驟實現。這些都是把生活中的模型用程序語言來表達的例子。 面試題45：圓圈中最后剩下的數字 題目：0,1,…,n－1這n個數字排成一個圓圈，從數字0開始每次從這個圓圈里刪除第m個數字。求出這個圓圈里剩下的最后一個數字。 例如，0、1、2、3、4這5個數字組成一個圓圈（如圖6.2所示），從數字0開始每次刪除第3個數字，則刪除的前四個數字依次是2、0、4、1，因此最后剩下的數字是3。  圖6.2 由0－4這5個數字組成的圓圈 本題就是有名的約瑟夫（Josephuse）環問題。我們介紹兩種方法：一種方法是用環形鏈表模擬圓圈的經典解法，第二種方法是分析每次被刪除的數字的規律并直接計算出圓圈中最后剩下的數字。 經典的解法，用環形鏈表模擬圓圈 既然題目中有一個數字圓圈，很自然的想法就是用一個數據結構來模擬這個圓圈。在常用的數據結構中，我們很容易想到環形鏈表。我們可以創建一個總共有n個結點的環形鏈表，然后每次在這個鏈表中刪除第m個結點。 如果面試官要求我們不能使用標準模板庫里的數據容器來模擬環形鏈表，我們自己實現一個鏈表也不是很難的事情。如果面試官沒有特殊要求，我們就可以用模板庫中的std::list來模擬一個環形鏈表。由于std::list本身并不是一個環形結構，因此每當迭代器（Iterator）掃描到鏈表末尾的時候，我們要記得把迭代器移到鏈表的頭部，這樣就相當于按照順序在一個圓圈里遍歷了。這種思路的代碼如下：  如果我們用一兩個例子仔細分析上述代碼的運行過程，就會發現我們實際上需要在環形鏈表里重復遍歷很多遍。重復的遍歷當然對時間效率有負面的影響。這種方法每刪除一個數字需要m步運算，總共有n個數字，因此總的時間復雜度是O（mn）。同時這種思路還需要一個輔助鏈表來模擬圓圈，其空間復雜度是O（n）。接下來我們試著找到每次被刪除的數字有哪些規律，希望能夠找到更加高效的算法。 創新的解法，拿到Offer不在話下 首先我們定義一個關于n和m的方程f（n,m），表示每次在n個數字0,1,…,n－1中每次刪除第m個數字最后剩下的數字。 在這n個數字中，第一個被刪除的數字是（m－1）%n。為了簡單起見，我們把（m－1）%n記為k，那么刪除k之后剩下的n－1個數字為0,1,…,k－1,k＋1,…,n－1，并且下一次刪除從數字k＋1開始計數。相當于在剩下的序列中，k＋1 排在最前面，從而形成k＋1,…,n－1,0,1,…,k－1。該序列最后剩下的數字也應該是關于n和m的函數。由于這個序列的規律和前面最初的序列不一樣（最初的序列是從0開始的連續序列），因此該函數不同于前面的函數，記為f’（n－1,m）。最初序列最后剩下的數字f（n,m）一定是刪除一個數字之后的序列最后剩下的數字，即f（n,m）＝f’（n－1,m）。 接下來我們把剩下的這n－1個數字的序列k＋1,…,n－1,0,1,…,k－1做一個映射，映射的結果是形成一個從0到n－2的序列：  我們把映射定義為p，則p（x）＝（x－k－1）%n。它表示如果映射前的數字是x，那么映射后的數字是（x－k－1）%n。該映射的逆映射是p－1（x）＝（x＋k＋1）%n。 由于映射之后的序列和最初的序列具有同樣的形式，即都是從0開始的連續序列，因此仍然可以用函數f來表示，記為f（n－1,m）。根據我們的映射規則，映射之前的序列中最后剩下的數字f’（n－1,m）＝p－1\[f（n－1,m）\]＝\[f（n－1,m）＋k＋1\]%n，把k＝（m－1）%n代入得到f（n,m）＝f’（n－1,m）＝\[f（n－1,m）＋m\]%n。 經過上面復雜的分析，我們終于找到了一個遞歸公式。要得到n個數字的序列中最后剩下的數字，只需要得到n－1個數字的序列中最后剩下的數字，并以此類推。當n＝1時，也就是序列中開始只有一個數字0，那么很顯然最后剩下的數字就是0。我們把這種關系表示為：  這個公式無論用遞歸還是用循環，都很容易實現。下面是一段基于循環實現的代碼：  可以看出，這種思路的分析過程盡管非常復雜，但寫出的代碼卻非常簡潔，這就是數學的魅力。最重要的是，這種算法的時間復雜度是O（n），空間復雜度是O（1），因此無論在時間效率還是空間效率上都優于第一種方法。 源代碼： 本題完整的源代碼詳見45\_LastNumberInCircle項目。 測試用例： ● 功能測試（輸入的m小于n，比如從最初有5個數字的圓圈刪除每次第2、3個數字；輸入的m大于或者等于n，比如從最初有6個數字的圓圈刪除每次第6、7個數字）。 ● 特殊輸入測試（圓圈中有0個數字）。 ● 性能測試（從最初有4000個數字的圓圈中每次刪除第997個數字）。 本題考點： ● 考查抽象建模的能力。不管應聘者是用環形鏈表來模擬圓圈，還是分析被刪除數字的規律，都要深刻理解這個問題的特點并編程實現自己的解決方案。 ● 考查對環形鏈表的理解及應用能力。大部分面試官只要求應聘者基于環形鏈表的方法解決這個問題。 ● 考查數學功底及邏輯思維能力。少數對算法和數學基礎要求很高的公司，面試官會要求應聘者不能使用O（n）的輔助內存，這個時候應聘者就只能靜下心來一步步推導出每次刪除的數字有哪些規律。 6.5 發散思維能力 發散思維的特點是思維活動的多向性和變通性，也就是我們在思考問題時注重運用多思路、多方案、多途徑地解決問題。對于同一個問題，我們可以從不同的方向、側面和層次，采用探索、轉換、遷移、組合和分解等方法，提出多種創新的解法。 通過考查發散思維能力，面試官能夠了解應聘者探索新思路的激情。面試時面試官故意限制應聘者不能使用常規的思路，此時他在觀察應聘者有沒有積極的心態，是不是能夠主動跳出常規思維的束縛從多角度去思考問題。比如在面試題46“求1＋2＋…＋n”中，面試官有意限制不能使用乘除法及與循環、條件判斷、選擇相關的關鍵字。這個問題應該說是很難的。在難題面前，應聘者是輕言放棄，還是充滿激情地尋找新思路、新方法，具有不同心態的應聘者在面試中的表現是大不一樣的。 通過考查發散思維，面試官能夠了解應聘者的靈活性和變通性。當常規思路遇到阻礙的時候，應聘者能不能及時地從另外的角度用不同的方法去分析問題，這些都能體現應聘者的創造力。在面試題47“不用加減乘除做加法”中，當四則運算被限制使用的時候，應聘者能不能迅速地從二進制和位運算這個方向尋找突破口，都是其思維靈活性的直接體現。 通過考查發散思維，面試官還能了解應聘者知識面的廣度和深度。面試實際上是一個厚積薄發的過程。在遇到問題之后，應聘者如果具有寬泛的知識面并且對各領域有較深的理解，那么他就更容易從不同的角度去思考問題。比如我們可以從構造函數、虛函數、函數指針及模板參數的實例化等不同角度去解決面試題46“求1＋2＋…＋n”。只有對C++各方面的特性了如指掌，我們才能在遇到問題的時候將各個知識點信手拈來。同樣，如果我們在學習數字電路相關課程的時候對CPU中加法器的原理有深刻的理解，那么自然就會想到從二進制和位運算的角度去思考解決面試題47“不用加減乘除做加法”。 面試題46：求1＋2＋…＋n 題目：求1＋2＋…＋n，要求不能使用乘除法、for、while、if、else、switch、case等關鍵字及條件判斷語句（A?B:C）。 這個問題本身沒有太多的實際意義，因為在軟件開發中不可能有這么苛刻的限制。但不少面試官認為這是一道不錯的能夠考查應聘者發散思維能力的題目，而發散思維能夠反映出應聘者知識面的寬度，以及對編程相關技術理解的深度。 通常求1＋2＋…＋n除了用公式n（n＋1）/2之外，無外乎循環和遞歸兩種思路。由于已經明確限制for和while的使用，循環已經不能再用了。遞歸函數也需要用if語句或者條件判斷語句來判斷是繼續遞歸下去還是終止遞歸，但現在題目已經不允許使用這兩種語句了。 解法一：利用構造函數求解 我們仍然圍繞循環做文章。循環只是讓相同的代碼重復執行n遍而已，我們完全可以不用for和while來達到這個效果。比如我們先定義一個類型，接著創建n個該類型的實例，那么這個類型的構造函數將確定會被調用n次。我們可以將與累加相關的代碼放到構造函數里。如下代碼正是基于這個思路：  解法二：利用虛函數求解 我們同樣也可以圍繞遞歸做文章。既然不能在一個函數中判斷是不是應該終止遞歸，那么我們不妨定義兩個函數，一個函數充當遞歸函數的角色，另一個函數處理終止遞歸的情況，我們需要做的就是在兩個函數里二選一。從二選一我們很自然地想到布爾變量，比如值為ture（1）的時候調用第一個函數，值為false（0）的時候調用第二個函數。那現在的問題是如何把數值變量n轉換成布爾值。如果對n連續做兩次反運算，即!!n，那么非零的n轉換為true，0轉換為false。有了上述分析，我們再來看下面的代碼：  這種思路是用虛函數來實現函數的選擇。當n不為零時，調用函數B::Sum；當n等于0時，調用函數A::Sum。 解法三：利用函數指針求解 在純C語言的編程環境中，我們不能使用虛函數，此時可以用函數指針來模擬，這樣代碼可能還更加直觀一些：  解法四：利用模板類型求解 另外我們還可以讓編譯器幫助完成類似于遞歸的計算。比如如下代碼：  Sum\_Solution4<100>::N就是1＋2＋…＋100的結果。當編譯器看到Sum\_Solution4<100>時，就會為模板類Sum \_Solution4以參數100生成該類型的代碼。但以100為參數的類型需要得到以99為參數的類型，因為Sum\_Solution4<100>::N＝ Sum \_Solution4 <99>::N＋100。這個過程會遞歸一直到參數為1的類型，由于該類型已經顯式定義，編譯器無須生成，遞歸編譯到此結束。由于這個過程是在編譯過程中完成的，因此要求輸入n必須是在編譯期間就能確定的常量，不能動態輸入，這是該方法最大的缺點。而且編譯器對遞歸編譯代碼的遞歸深度是有限制的，也就是要求n不能太大。 源代碼： 本題完整的源代碼詳見46\_Accumulate項目。 測試用例： ● 功能測試（輸入5、10求1＋2＋…＋5和1＋2＋…＋10）。 ● 邊界值測試（輸入0和1）。 本題考點： ● 考查發散思維能力。當習以為常的方法被限制使用的時候，應聘者是否能發揮創造力，打開思路想出新的辦法，是能否通過面試的關鍵所在。 ● 考查知識面的廣度和深度。上面提供的幾種解法，涉及構造函數、靜態變量、虛擬函數、函數指針、模板類型的實例化等知識點。只有深刻理解了相關的概念，才能在需要的時候信手拈來。這就是厚積薄發的過程。 面試題47：不用加減乘除做加法 題目：寫一個函數，求兩個整數之和，要求在函數體內不得使用＋、－、×、÷四則運算符號。 面試的時候被問到這個問題，很多人在想：四則運算都不能用，那還能用什么啊？可是問題總是要解決的，我們只能打開思路去思考各種可能性。首先我們可以分析人們是如何做十進制的加法的，比如是如何得出5＋17＝22這個結果的。實際上，我們可以分成三步進行：第一步只做各位相加不進位，此時相加的結果是12（個位數5和7相加不要進位是2，十位數0和1相加結果是1）；第二步做進位，5＋7中有進位，進位的值是10；第三步把前面兩個結果加起來，12＋10的結果是22，剛好5＋17＝22。 我們一直在想，求兩數之和四則運算都不能用，那還能用什么？對數字做運算，除了四則運算之外，也就只剩下位運算了。位運算是針對二進制的，我們就以二進制再來分析一下前面的三步走策略對二進制是不是也適用。 5的二進制是101，17的二進制是10001。還是試著把計算分成三步：第一步各位相加但不計進位，得到的結果是10100（最后一位兩個數都是1，相加的結果是二進制的10。這一步不計進位，因此結果仍然是0）；第二步記下進位。在這個例子中只在最后一位相加時產生一個進位，結果是二進制的10；第三步把前兩步的結果相加，得到的結果是10110，轉換成十進制正好是22。由此可見三步走的策略對二進制也是適用的。 接下來我們試著把二進制的加法用位運算來替代。第一步不考慮進位對每一位相加。0加0、1加1的結果都0，0加1、1加0的結果都是1。我們注意到，這和異或的結果是一樣的。對異或而言，0和0、1和1異或的結果是0，而0和1、1和0的異或結果是1。接著考慮第二步進位，對0加0、0加1、1加0而言，都不會產生進位，只有1加1時，會向前產生一個進位。此時我們可以想象成是兩個數先做位與運算，然后再向左移動一位。只有兩個數都是1的時候，位與得到的結果是1，其余都是0。第三步把前兩個步驟的結果相加。第三步相加的過程依然是重復前面兩步，直到不產生進位為止。 把這個過程想清楚之后，寫出的代碼非常簡潔。下面是一段基于循環實現的參考代碼：  源代碼： 本題完整的源代碼詳見47\_AddTwoNumbers項目。 測試用例： 輸入正數、負數和0。 本題考點： ● 考查發散思維能力。當＋、－、×、÷運算符都不能使用時，應聘者能不能打開思路想到用位運算做加法，是能否順利解決這個問題的關鍵。 ● 考查對二進制和位運算的理解。 相關問題： 不使用新的變量，交換兩個變量的值。比如有兩個變量a、b，我們希望交換它們的值。有兩種不同的辦法：  面試題48：不能被繼承的類 題目：用C++設計一個不能被繼承的類。 在C#中定義了關鍵字sealed，被sealed修飾的類不能被繼承。在Java中同樣也有關鍵字final表示一個類型不能被繼承。在C++中沒有類似于sealed和final的關鍵字，我們只有自己來實現。 常規的解法：把構造函數設為私有函數 很多人都能夠想到，在C++中子類的構造函數會自動調用父類的構造函數，子類的析構函數也會自動調用父類的析構函數。要想一個類不能被繼承，我們只要把它的構造函數和析構函數都定義為私有函數。那么當一個類試圖從它那繼承的時候，必然會由于調用構造函數、析構函數而導致編譯錯誤。 可是這個類型的構造函數和析構函數都是私有函數，我們怎樣才能得到該類型的實例呢？我們可以通過定義公有的靜態函數來創建和釋放類的實例。基于這個思路，我們可以寫出如下代碼：  這個類是不能被繼承，但總覺得它和普通的類型有些不一樣，使用起來有點不方便。比如我們只能得到位于堆上的實例，而得不到位于棧上的實例。 新奇的解法：利用虛擬繼承，能給面試官留下很好的印象 能不能實現一個與一般的類型相比除了不能被繼承之外其他用法都一樣的類型呢？辦法還是有的，不過需要一定的技巧。請看如下代碼：  這個SealedClass2使用起來和一般的類型沒有區別，我們可以在棧上、也可以在堆上創建實例。盡管類MakeSealed<SealedClass2>的構造函數和析構函數都是私有的，但由于類SealedClass2是它的友元類型，因此在SealedClass2中調用MakeSealed<SealedClass2>的構造函數和析構函數都不會引起編譯錯誤。 但當我們試圖從SealedClass2中繼承一個類并創建它的實例的時候，卻不能通過編譯。比如我們從SealedClass2中繼承出類型Try：  由于類SealedClass2是從類MakeSealed<SealedClass2>虛繼承過來的，在調用Try的構造函數的時候，會跳過SealedClass2而直接調用MakeSealed<SealedClass2>的構造函數。非常遺憾的是，Try不是MakeSealed<SealedClass2>的友元類型，因此不能調用它的私有構造函數。 通過上面的分析，我們發現從SealedClass2繼承的類，一旦實例化就會導致編譯出錯，因此SealedClass2不能被繼承，這也就滿足了題目的要求。 注：第二種方法的可移植性不好。雖然SealedClass2在Visual Studio中能夠編譯，但由于GCC中對friend的要求不同于Visual Studio，目前在最新的GCC中還不支持模板參數類型作為友元類型。 源代碼： 本題完整的源代碼詳見48\_SealedClass項目。 本題考點： ● 考查發散思維能力。當要求設計一個不能被繼承的類時，應聘者要馬上從把構造函數定義為私有函數出發去尋找解題方法。 ● 考查對C++多個概念的理解，比如構造函數、模板、友元等。 6.6 本章小結 面試是我們展示自己綜合素質的時候。除了扎實的編程能力，我們還需要表現自己的溝通能力和學習能力，以及知識遷移能力、抽象建模能力和發散思維能力等方面的綜合實力（如圖6.3所示）。  圖6.3 應聘者的綜合能力的組成 面試官對溝通能力、學習能力的考查貫穿著面試的始終。面試官不僅會留意我們回答問題時的言語談吐，還會關注我們是否能抓住問題的本質從而提出有針對性的問題。通常面試官認為善于提問的人有較好的溝通和學習能力。 知識遷移能力能幫助我們輕松地解決很多問題。有些面試官在提問一道難題之前，會問一道相關但比較簡單的題目，他希望我們能夠從解決簡單問題的過程中受到啟發，最終解決較為復雜的問題。另外，我們在面試之前可以做一些練習。如果面試的時候碰到類似的題目，就可以應用之前的方法。這要求我們平時要有一定的積累，并且每做完一道題之后都要總結解題方法。 有一類很有意思的面試題是從日常生活中提煉出來的，面試官用這種類型的問題來考查我們抽象建模的能力。為了解決這種類型的問題，我們先用適當的數據結構表述模型，并分析模型中的內在規律確定計算方法。 有些面試官喜歡在面試的時候限制使用常規的思路。這個時候就需要我們充分發揮發散思維的能力，跳出常規思路的束縛，從不同的角度去嘗試新的辦法。