第1章 面試的流程

1. 編程時應(yīng)注意的三點：

• 思考清楚再開始編碼；
• 良好的代碼命名和縮進(jìn)對齊痊班；
• 能夠單元測試；

2. 現(xiàn)場面試時摹量，記得準(zhǔn)備幾個問題。（每輪面試的最后馒胆，面試官可能會讓面試者問問題）

3. 項目經(jīng)驗的描述（STAR）

• Situation：簡短的項目背景缨称；
• Task：自己完成的任務(wù)；
• Action：為了完成任務(wù)自己做了哪些工作祝迂，怎么做的睦尽；
• Result：自己的貢獻(xiàn)；

常被問的問題包括:

• 你在項目中遇到的最大的問題是什么型雳？
• 在項目中你學(xué)到了什么当凡？

4. 面試中應(yīng)聘者需要具備的素質(zhì)：

• 基礎(chǔ)知識扎實全面，包括編程語言纠俭、數(shù)據(jù)結(jié)構(gòu)（鏈表沿量、二叉樹...）、算法（查找冤荆、排序...）等朴则；
• 寫出正確的、完整的钓简、魯棒的高質(zhì)量代碼（邊界條件乌妒、特殊輸入...）；
• 思路清晰地分析外邓、解決復(fù)雜問題撤蚊；
• 從時間、空間復(fù)雜度兩方面優(yōu)化算法损话；
• 優(yōu)秀的溝通侦啸、學(xué)習(xí)、發(fā)散思維能力；

5. 高質(zhì)量代碼的例子——將字符串轉(zhuǎn)換成整數(shù) int StrToInt(char* string)匹中，你是否能考慮到下面幾個方面夏漱？

• 判斷指針string是否為空；
• 正負(fù)號顶捷；
• 非數(shù)字字符挂绰；
• 數(shù)值溢出（臨時變量用long long，若超過int范圍報錯服赎，否則返回int值）葵蒂；

第2章 面試的基礎(chǔ)知識

1. 編程語言（如C++）
   面試題1 為CMyString實現(xiàn)賦值運算符。

class CMyString
{
public:
    CMyString(char* pData=NULL);
    CMyString(const CMyString& str);
    ~CMyString(void);
private:
    char* m_pData;
};

考慮因素：

• 返回值類型聲明為該類型的引用（允許連續(xù)賦值）重虑，并且函數(shù)結(jié)束前返回*this践付。
• 傳入?yún)?shù)聲明為常量引用；
• 釋放實例自身已有的內(nèi)存缺厉；
• 判斷傳入?yún)?shù)和當(dāng)前實例是否為同一個實例永高；

高階：

• 考慮申請內(nèi)存失敗的情況。方法：創(chuàng)建一個臨時實例提针，將其與本身交換命爬。

2. 數(shù)據(jù)結(jié)構(gòu)的例子：向單鏈表尾部插入一個數(shù)據(jù)。需要注意的是辐脖，由于當(dāng)輸入鏈表為空時饲宛，會修改指向輸入鏈表的指針，因此要將輸入指針設(shè)為指向指針的指針嗜价，否則出了這個函數(shù)艇抠，它仍是一個空指針。

3. 算法和數(shù)據(jù)操作：
   面試題8：旋轉(zhuǎn)數(shù)組（例如[3, 4, 5, 1, 2]）中的最小值久锥。需要考慮的內(nèi)容：

• 使用二分法家淤；
• 本身數(shù)組是排序的（即沒有斷點）；
• 數(shù)組中有相同數(shù)字的情況（在某一部分出現(xiàn)這種情況則只能順序查找）奴拦；

面試題9的相關(guān)題目：斐波那契的變體
用一個2x1的小矩形去覆蓋2xn的大矩形媒鼓，有多少種方法？本質(zhì)仍是斐波那契數(shù)列错妖。

面試題10：二進(jìn)制中1的個數(shù)绿鸣。
常規(guī)解法：

//與 1、10暂氯、100潮模、1000依次相與
int NumberOf1(int n)
{
    int count = 0;
    usigned int flag = 1;
    while(flag)
    {
        if(n & flag)
            count++;
        flag = flag << 1;
    }
    return count;
}

高階解法：

//n-1會將n的右數(shù)第一個1變成0，右邊的所有0變成1痴施，so (n-1) & n 抹去了n的右數(shù)第一個1
int NumberOf1(int n)
{
    int count = 0;
    while(n)
    {
        ++count;
        n = (n-1) & n;
    }
    return count;
}

第3章 高質(zhì)量的代碼

1. 面試題13：在O(1)時間刪除鏈表節(jié)點
   如果遍歷鏈表找到目標(biāo)節(jié)點的前驅(qū)擎厢，并進(jìn)行刪除究流，則需要O(n)的時間，要在O(1)時間內(nèi)刪除節(jié)點动遭，采用的方法是將目標(biāo)節(jié)點的后繼復(fù)制到目標(biāo)節(jié)點芬探，并刪除目標(biāo)節(jié)點的后繼節(jié)點！
   需要注意的內(nèi)容包括：

• 要刪除的不是尾節(jié)點厘惦；
• 鏈表只有一個節(jié)點偷仿；
• 鏈表有多個節(jié)點，刪除尾節(jié)點宵蕉；

第4章 解決面試題的思路

1. 面試題26：復(fù)雜鏈表的復(fù)制
   復(fù)雜鏈表的節(jié)點不僅包含一個指向下一個節(jié)點的指針pNext酝静，還有一個指向鏈表中任意節(jié)點或者NULL的指針pSibling。

• 方法1：第一遍按單鏈表的方式復(fù)制鏈表羡玛，同時記錄A->A'的映射關(guān)系别智，第二遍復(fù)制pSibling；

• 方法2：第一步稼稿，在每個A后面插入A'薄榛，第二步，插入pSibling渺杉，第三布將鏈表按奇偶拆分長兩部分蛇数；

  
  

第5章 優(yōu)化時間和空間效率

1. 面試題29：數(shù)組中出現(xiàn)次數(shù)超過一半的數(shù)字

• 解法一：基于partition的O(n)算法。如果一個數(shù)出現(xiàn)超過一半是越，那么數(shù)組排序后，它一定位于中位數(shù)處碌上！因此把問題轉(zhuǎn)換成尋找第k大的數(shù)倚评！用快排的思想，每次隨機選一個數(shù)字作為分隔馏予，把比這個數(shù)小的都移到這個數(shù)前面天梧，大的都移到這個數(shù)后面，然后返回這個數(shù)在數(shù)組中的位置i霞丧，如果正好是k呢岗，那么就找到了，否則蛹尝，如果i>k后豫，就在i前繼續(xù)尋找，如果i<k則在后部繼續(xù)尋找突那。書上說這個方法是O(n)的挫酿，《算法導(dǎo)論》上有證明。
• 解法二：根據(jù)數(shù)組特點找出O(n)算法愕难。如果一個數(shù)出現(xiàn)超過一半早龟，那么它出現(xiàn)得比其他所有數(shù)加起來都多惫霸！方法：遍歷數(shù)組，保存上一次出現(xiàn)的數(shù)葱弟，當(dāng)前數(shù)和上個數(shù)相同是壹店，記錄次數(shù)+1，不相等則記錄次數(shù)-1芝加，如果次數(shù)減為0硅卢，下次需要記錄當(dāng)前數(shù)字。最后保存的數(shù)字妖混，可能就是我們要找的老赤。
• 上面兩個方法找出來的數(shù)，都需要一個O(n)的判定函數(shù)來進(jìn)行判定制市，它是不是真的出現(xiàn)了超過一半次數(shù)抬旺。

2. 面試題30：最小的k個數(shù)

• 解法一：利用partition的O(n)算法。
• 解法二：最小堆祥楣。特別適合海量數(shù)據(jù)的場景开财。

3. 面試題31：連續(xù)子數(shù)組最大和
   解法：從頭逐個累加，若當(dāng)前累加結(jié)果小于零误褪，則拋棄當(dāng)前結(jié)果责鳍，將和置零，從下一個數(shù)字開始重新累加兽间。要持續(xù)判斷當(dāng)前和是否大于當(dāng)前最大和历葛。

4. 面試題32：從1到n整數(shù)中1出現(xiàn)的次數(shù)
   實例分析：以21345為例，我們把它分成兩段嘀略，1-1345和1346-21345恤溶，第二段是20000個數(shù)。我們來看1346-21345帜羊。這一段咒程，1出現(xiàn)在首位有10000次（如果首位為1則不足10000次，而是1345+1次）讼育。再看這一段中帐姻，1出現(xiàn)在后4位是什么情況，我們進(jìn)一步把1346-21345分解成1346-11345和11346-21345奶段，即兩個10000饥瓷，那么這4位中，任意一位為1時忧饭，其他3位可以任選0-9扛伍，因此出現(xiàn)次數(shù)為2*10³。代碼直接貼圖了：
   

   
   注意词裤，復(fù)雜度是O(logn)哦刺洒！

5. 面試題33：把數(shù)組排成最小的數(shù)
   解法：兩個字符串m和n鳖宾，可以拼成mn也可以拼成nm，于是定義一個比較方法逆航，若mn<nm則m<n鼎文，即m應(yīng)該放在n前面。因此對數(shù)組進(jìn)行排序因俐，然后拼接即可拇惋。

6. 面試題34：丑數(shù)
   LeetCode里做過，題解264. Ugly Number II抹剩，感覺自己寫的代碼好優(yōu)美呢哈哈哈哈哈撑帖。

7. 面試題36：數(shù)組中的逆序?qū)?br> 解法：用歸并排序的想法做。假設(shè)數(shù)組的前面一半和后面一半已經(jīng)各自排好序澳眷，那么合并時候胡嘿，依次取兩個部分尾部較大的數(shù)寫入新數(shù)組，如果取的是前面一半的數(shù)钳踊，那么當(dāng)前后面一半還剩的數(shù)衷敌，都會跟它構(gòu)成逆序數(shù)！

第6章 面試中的各項能力

1. 知識遷移能力
   面試題39：二叉樹的深度

• 如果是求二叉樹深度拓瞪，那么直接遞歸進(jìn)行遍歷即可缴罗，因為對于某個節(jié)點只需要求左右子樹中深度更深的一個。
• 如果是判斷一棵樹是否為平衡二叉樹（左右節(jié)點高度差不超過1）祭埂，那么需要使用后續(xù)遍歷面氓，以免重復(fù)計算。

面試題40：數(shù)組中只出現(xiàn)一次的數(shù)字
一個整形數(shù)組中蛆橡，除了兩個數(shù)字以外侧但，其他數(shù)字都出現(xiàn)了兩次，請找出這兩個數(shù)字航罗。

• 如果只有一個數(shù)字出現(xiàn)一次，其他數(shù)字出現(xiàn)兩次屁药，那么將所有數(shù)字異或得到的結(jié)果就是那個數(shù)字（其他數(shù)字兩次異或抵消了）粥血；
• 問題轉(zhuǎn)換成，怎么把現(xiàn)在的數(shù)組分成兩部分酿箭，讓這兩部分每部分只包括一個只出現(xiàn)一次的數(shù)字复亏。
• 因為兩個只出現(xiàn)一次的數(shù)字不同，那么對它們求異或缭嫡，它們至少有一位二進(jìn)制是不同的缔御，根據(jù)這個二進(jìn)制位，將原數(shù)組分為兩個數(shù)組妇蛀，那么每個小數(shù)組就只包含一個只出現(xiàn)一次的數(shù)字了耕突！

面試題41：和為s的兩個數(shù)字 VS 和為s的連續(xù)正數(shù)序列（都是排序數(shù)組）

• 和為s的兩個數(shù)字：兩個指針笤成，一個代表子序列的頭head，一個代表子序列的尾tail眷茁，若當(dāng)前和小于s炕泳，則tail+=1，若當(dāng)前和>s上祈，則head+=1培遵。
• 和為s的連續(xù)正數(shù)序列：與上面類似，當(dāng)前和超了登刺，則拋棄較小的數(shù)籽腕，當(dāng)前和不足，則加入一個更大的數(shù)纸俭。

面試題42：翻轉(zhuǎn)單詞順序 VS 左旋轉(zhuǎn)字符串

• 翻轉(zhuǎn)單詞順序：二次反轉(zhuǎn)策略皇耗，先把整個字符串翻轉(zhuǎn)，再逐個翻轉(zhuǎn)單詞掉蔬。
• 左旋轉(zhuǎn)字符串：左旋m位廊宪，則將原字符串按m分為兩部分，分別翻轉(zhuǎn)兩部分女轿，再整個翻轉(zhuǎn)箭启。

2. 抽象建模能力
   面試題43：n個骰子的點數(shù)。
   n個骰子扔地上蛉迹，s為朝上一面的點數(shù)和傅寡，求所有s的可能值及其概率。

• 方法一：遞歸統(tǒng)計北救；

• 方法二：循環(huán)思路荐操，當(dāng)前拋了m個篩子，拋第m+1個的時候珍策，和為n的數(shù)目為前m次和為您n-1托启、n-2、n-3攘宙、n-4屯耸、n-5、n-6的總數(shù)蹭劈！
  代碼直接貼過來：

  
  

面試題45：約瑟夫環(huán)

• 用環(huán)形鏈表模擬疗绣。
• 數(shù)學(xué)公式。證明如下：
  設(shè)f(n, m)表示在0, 1, …, n-1中每次刪掉第m個數(shù)字后剩下的數(shù)字铺韧，這個數(shù)字k = (m-1)%n多矮；
  刪除k后剩下的數(shù)字為0, 1, …, k-1, k+1,…, n-1，并且下次從m+1開始刪哈打，相當(dāng)于序列為k+1,…, n-1, 0, 1, …, k-1塔逃，該序列最后剩下的數(shù)字也一定是關(guān)于n和m的函數(shù)讯壶，不過這個序列不是從0開始計數(shù)的，因此我們設(shè)f’(n-1, m)是在序列k+1,…, n-1, 0, 1, …, k-1中每次刪除第m個數(shù)字剩下的數(shù)字患雏，那么f(n, m) = f’(n-1, m)鹏溯。
  我們將k+1,…, n-1, 0, 1, …, k-1序列映射到0, 1, …, n-2的函數(shù)設(shè)為p，p(x) = (x-k-1)%n淹仑，p^-1(x) = (x+k+1)%n, 因此
  f(n, m) = f’(n-1, m) = p^-1[f(n-1, m)] = [f(n-1, m)+k+1]%n = [f(n-1, m)+(m-1)%n+1]%n = [f(n-1, m)+m]%n
  遞推公式及代碼如下：
  

3. 發(fā)散思維能力
   這部分題好多是涉及語言特點的丙挽，比如C++的類等，我這方面還沒有準(zhǔn)備匀借，沒有學(xué)好颜阐，先簡單記一下，可能語言過關(guān)了再回頭看會好一些吓肋。
   面試題46：求1+2+...+n
   不準(zhǔn)用乘除凳怨、for、while是鬼、if肤舞、else、switch均蜜、case等關(guān)鍵字及條件判斷語句（A?B:C）

• 利用構(gòu)造函數(shù)

  
  

• 利用虛函數(shù)

  
  

• 利用函數(shù)指針

  
  

• 利用模板類型

  
  

面試題47：不用加減乘除做加法
用位運算李剖！不考慮進(jìn)位=a^b，進(jìn)位=a&b<<1囤耳，需要循環(huán)進(jìn)行篙顺，直到不產(chǎn)生進(jìn)位！
相關(guān)問題：不用新變量交換兩個變量的值充择。

• a = a + b
  b = a - b
  a = a - b
• a = a ^ b
  b = a ^ b
  a = a ^ b

面試題48：不能被繼承的類

• 把構(gòu)造函數(shù)設(shè)為私有函數(shù)

  
  

• 使用友元

  
  

第7章 兩個面試案例

略德玫，主要還是要把細(xì)節(jié)考慮到，如參數(shù)的檢查椎麦，邊緣條件宰僧，錯誤輸入等。

第8章 英文版新增面試題

1. 面試題51：數(shù)組中重復(fù)的數(shù)字
   一個長度為n的數(shù)組里所有數(shù)字都在0到n-1之間观挎，某些數(shù)字是重復(fù)的撒桨，但不知道有幾個是重復(fù)的，請找出任意一個重復(fù)數(shù)字键兜。
   解法：從頭到尾掃描數(shù)組，當(dāng)掃描到下標(biāo)為i值為m的數(shù)字穗泵，若m=i普气，則繼續(xù)掃描下一個數(shù)字，若m≠i佃延，比較它和第m個數(shù)字现诀，若相等夷磕，則找到了一個重復(fù)數(shù)字，否則交換m和i位置的數(shù)字仔沿，即將當(dāng)前數(shù)字歸位坐桩。

2. 面試題57：刪除鏈表中重復(fù)的節(jié)點
   需要注意的是：如果鏈表的頭可能修改，則傳入?yún)?shù)的時候不能是ListNode* pHead封锉，而需要是ListNode** pHead绵跷！

3. 面試題64：數(shù)據(jù)流中的中位數(shù)
   解法：我們維護(hù)兩個堆，一個大頂堆b成福，一個小頂堆s碾局。我們保證b的最大值比s的最小值要小，那么b里所有值都比s小了奴艾，然后讓兩個堆中元素個數(shù)相等净当，那么通過兩個堆的堆頂就能求中位數(shù)啦。
   具體可以在數(shù)字總數(shù)目為偶數(shù)時蕴潦，把數(shù)字插入s像啼，數(shù)目為奇數(shù)時，插入b潭苞。但還是要根據(jù)數(shù)字的大小忽冻，維持b的頂比s的頂小。

4. 面試題65：滑動窗口的最大值
   這題之前根神跟我們說過萄传，確實設(shè)計很精巧甚颂。

• 可以用帶最大值的隊列做（用兩個帶最大值的棧模擬隊列）；
• 用deque做秀菱，貼代碼吧：

vector<int> maxInWindows(const vector<int>& num, unsigned int size)
{
    vector<int> maxInWindows;
    if(num.size() >= size && size >= 1)
    {
        deque<int> index;
        for(unsigned int i = 0; i < size; i++)
        {
            while(!index.empty() && num[i] >= num[index.back()])
                index.pop_back();
            index.push_back(i);
        }
        for(unsigned int i = size; i < num.size(); i++)
        {
            maxInWindows.push_back(num[index.front()]);
            while(!index.empty() && num[i] >= num[index.back()])
                index.pop_back();
            if(!index.empty() && index.front() <= (int)(i - size))
                index.pop_front(i);
        }
        maxInWindows.push_back(num[index.front()]);
    }
    return maxInWindows;
}