第1章 面试的流程

1. 编程时应注意的三点：

• 思考清楚再开始编码；
• 良好的代码命名和缩进对齐；
• 能够单元测试；

2. 现场面试时，记得准备几个问题。（每轮面试的最后，面试官可能会让面试者问问题）

3. 项目经验的描述（STAR）

• Situation：简短的项目背景；
• Task：自己完成的任务；
• Action：为了完成任务自己做了哪些工作，怎么做的；
• Result：自己的贡献；

常被问的问题包括:

• 你在项目中遇到的最大的问题是什么？
• 在项目中你学到了什么？

4. 面试中应聘者需要具备的素质：

• 基础知识扎实全面，包括编程语言、数据结构（链表、二叉树...）、算法（查找、排序...）等；
• 写出正确的、完整的、鲁棒的高质量代码（边界条件、特殊输入...）；
• 思路清晰地分析、解决复杂问题；
• 从时间、空间复杂度两方面优化算法；
• 优秀的沟通、学习、发散思维能力；

5. 高质量代码的例子——将字符串转换成整数 int StrToInt(char* string)，你是否能考虑到下面几个方面？

• 判断指针string是否为空；
• 正负号；
• 非数字字符；
• 数值溢出（临时变量用long long，若超过int范围报错，否则返回int值）；

第2章 面试的基础知识

1. 编程语言（如C++）
   面试题1 为CMyString实现赋值运算符。

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

考虑因素：

• 返回值类型声明为该类型的引用（允许连续赋值），并且函数结束前返回*this。
• 传入参数声明为常量引用；
• 释放实例自身已有的内存；
• 判断传入参数和当前实例是否为同一个实例；

高阶：

• 考虑申请内存失败的情况。方法：创建一个临时实例，将其与本身交换。

2. 数据结构的例子：向单链表尾部插入一个数据。需要注意的是，由于当输入链表为空时，会修改指向输入链表的指针，因此要将输入指针设为指向指针的指针，否则出了这个函数，它仍是一个空指针。

3. 算法和数据操作：
   面试题8：旋转数组（例如[3, 4, 5, 1, 2]）中的最小值。需要考虑的内容：

• 使用二分法；
• 本身数组是排序的（即没有断点）；
• 数组中有相同数字的情况（在某一部分出现这种情况则只能顺序查找）；

面试题9的相关题目：斐波那契的变体
用一个2x1的小矩形去覆盖2xn的大矩形，有多少种方法？本质仍是斐波那契数列。

面试题10：二进制中1的个数。
常规解法：

//与 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的右数第一个1变成0，右边的所有0变成1，so (n-1) & n 抹去了n的右数第一个1
int NumberOf1(int n)
{
    int count = 0;
    while(n)
    {
        ++count;
        n = (n-1) & n;
    }
    return count;
}

第3章 高质量的代码

1. 面试题13：在O(1)时间删除链表节点
   如果遍历链表找到目标节点的前驱，并进行删除，则需要O(n)的时间，要在O(1)时间内删除节点，采用的方法是将目标节点的后继复制到目标节点，并删除目标节点的后继节点！
   需要注意的内容包括：

• 要删除的不是尾节点；
• 链表只有一个节点；
• 链表有多个节点，删除尾节点；

第4章 解决面试题的思路

1. 面试题26：复杂链表的复制
   复杂链表的节点不仅包含一个指向下一个节点的指针pNext，还有一个指向链表中任意节点或者NULL的指针pSibling。

• 方法1：第一遍按单链表的方式复制链表，同时记录A->A'的映射关系，第二遍复制pSibling；

• 方法2：第一步，在每个A后面插入A'，第二步，插入pSibling，第三布将链表按奇偶拆分长两部分；

  
  

第5章 优化时间和空间效率

1. 面试题29：数组中出现次数超过一半的数字

• 解法一：基于partition的O(n)算法。如果一个数出现超过一半，那么数组排序后，它一定位于中位数处！因此把问题转换成寻找第k大的数！用快排的思想，每次随机选一个数字作为分隔，把比这个数小的都移到这个数前面，大的都移到这个数后面，然后返回这个数在数组中的位置i，如果正好是k，那么就找到了，否则，如果i>k，就在i前继续寻找，如果i<k则在后部继续寻找。书上说这个方法是O(n)的，《算法导论》上有证明。
• 解法二：根据数组特点找出O(n)算法。如果一个数出现超过一半，那么它出现得比其他所有数加起来都多！方法：遍历数组，保存上一次出现的数，当前数和上个数相同是，记录次数+1，不相等则记录次数-1，如果次数减为0，下次需要记录当前数字。最后保存的数字，可能就是我们要找的。
• 上面两个方法找出来的数，都需要一个O(n)的判定函数来进行判定，它是不是真的出现了超过一半次数。

2. 面试题30：最小的k个数

• 解法一：利用partition的O(n)算法。
• 解法二：最小堆。特别适合海量数据的场景。

3. 面试题31：连续子数组最大和
   解法：从头逐个累加，若当前累加结果小于零，则抛弃当前结果，将和置零，从下一个数字开始重新累加。要持续判断当前和是否大于当前最大和。

4. 面试题32：从1到n整数中1出现的次数
   实例分析：以21345为例，我们把它分成两段，1-1345和1346-21345，第二段是20000个数。我们来看1346-21345。这一段，1出现在首位有10000次（如果首位为1则不足10000次，而是1345+1次）。再看这一段中，1出现在后4位是什么情况，我们进一步把1346-21345分解成1346-11345和11346-21345，即两个10000，那么这4位中，任意一位为1时，其他3位可以任选0-9，因此出现次数为2*10³。代码直接贴图了：
   

   
   注意，复杂度是O(logn)哦！

5. 面试题33：把数组排成最小的数
   解法：两个字符串m和n，可以拼成mn也可以拼成nm，于是定义一个比较方法，若mn<nm则m<n，即m应该放在n前面。因此对数组进行排序，然后拼接即可。

6. 面试题34：丑数
   LeetCode里做过，题解264. Ugly Number II，感觉自己写的代码好优美呢哈哈哈哈哈。

7. 面试题36：数组中的逆序对
   解法：用归并排序的想法做。假设数组的前面一半和后面一半已经各自排好序，那么合并时候，依次取两个部分尾部较大的数写入新数组，如果取的是前面一半的数，那么当前后面一半还剩的数，都会跟它构成逆序数！

第6章 面试中的各项能力

1. 知识迁移能力
   面试题39：二叉树的深度

• 如果是求二叉树深度，那么直接递归进行遍历即可，因为对于某个节点只需要求左右子树中深度更深的一个。
• 如果是判断一棵树是否为平衡二叉树（左右节点高度差不超过1），那么需要使用后续遍历，以免重复计算。

面试题40：数组中只出现一次的数字
一个整形数组中，除了两个数字以外，其他数字都出现了两次，请找出这两个数字。

• 如果只有一个数字出现一次，其他数字出现两次，那么将所有数字异或得到的结果就是那个数字（其他数字两次异或抵消了）；
• 问题转换成，怎么把现在的数组分成两部分，让这两部分每部分只包括一个只出现一次的数字。
• 因为两个只出现一次的数字不同，那么对它们求异或，它们至少有一位二进制是不同的，根据这个二进制位，将原数组分为两个数组，那么每个小数组就只包含一个只出现一次的数字了！

面试题41：和为s的两个数字 VS 和为s的连续正数序列（都是排序数组）

• 和为s的两个数字：两个指针，一个代表子序列的头head，一个代表子序列的尾tail，若当前和小于s，则tail+=1，若当前和>s，则head+=1。
• 和为s的连续正数序列：与上面类似，当前和超了，则抛弃较小的数，当前和不足，则加入一个更大的数。

面试题42：翻转单词顺序 VS 左旋转字符串

• 翻转单词顺序：二次反转策略，先把整个字符串翻转，再逐个翻转单词。
• 左旋转字符串：左旋m位，则将原字符串按m分为两部分，分别翻转两部分，再整个翻转。

2. 抽象建模能力
   面试题43：n个骰子的点数。
   n个骰子扔地上，s为朝上一面的点数和，求所有s的可能值及其概率。

• 方法一：递归统计；

• 方法二：循环思路，当前抛了m个筛子，抛第m+1个的时候，和为n的数目为前m次和为您n-1、n-2、n-3、n-4、n-5、n-6的总数！
  代码直接贴过来：

  
  

面试题45：约瑟夫环

• 用环形链表模拟。
• 数学公式。证明如下：
  设f(n, m)表示在0, 1, …, n-1中每次删掉第m个数字后剩下的数字，这个数字k = (m-1)%n；
  删除k后剩下的数字为0, 1, …, k-1, k+1,…, n-1，并且下次从m+1开始删，相当于序列为k+1,…, n-1, 0, 1, …, k-1，该序列最后剩下的数字也一定是关于n和m的函数，不过这个序列不是从0开始计数的，因此我们设f’(n-1, m)是在序列k+1,…, n-1, 0, 1, …, k-1中每次删除第m个数字剩下的数字，那么f(n, m) = f’(n-1, m)。
  我们将k+1,…, n-1, 0, 1, …, k-1序列映射到0, 1, …, n-2的函数设为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. 发散思维能力
   这部分题好多是涉及语言特点的，比如C++的类等，我这方面还没有准备，没有学好，先简单记一下，可能语言过关了再回头看会好一些。
   面试题46：求1+2+...+n
   不准用乘除、for、while、if、else、switch、case等关键字及条件判断语句（A?B:C）

• 利用构造函数

  
  

• 利用虚函数

  
  

• 利用函数指针

  
  

• 利用模板类型

  
  

面试题47：不用加减乘除做加法
用位运算！不考虑进位=a^b，进位=a&b<<1，需要循环进行，直到不产生进位！
相关问题：不用新变量交换两个变量的值。

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

面试题48：不能被继承的类

• 把构造函数设为私有函数

  
  

• 使用友元

  
  

第7章 两个面试案例

略，主要还是要把细节考虑到，如参数的检查，边缘条件，错误输入等。

第8章 英文版新增面试题

1. 面试题51：数组中重复的数字
   一个长度为n的数组里所有数字都在0到n-1之间，某些数字是重复的，但不知道有几个是重复的，请找出任意一个重复数字。
   解法：从头到尾扫描数组，当扫描到下标为i值为m的数字，若m=i，则继续扫描下一个数字，若m≠i，比较它和第m个数字，若相等，则找到了一个重复数字，否则交换m和i位置的数字，即将当前数字归位。

2. 面试题57：删除链表中重复的节点
   需要注意的是：如果链表的头可能修改，则传入参数的时候不能是ListNode* pHead，而需要是ListNode** pHead！

3. 面试题64：数据流中的中位数
   解法：我们维护两个堆，一个大顶堆b，一个小顶堆s。我们保证b的最大值比s的最小值要小，那么b里所有值都比s小了，然后让两个堆中元素个数相等，那么通过两个堆的堆顶就能求中位数啦。
   具体可以在数字总数目为偶数时，把数字插入s，数目为奇数时，插入b。但还是要根据数字的大小，维持b的顶比s的顶小。

4. 面试题65：滑动窗口的最大值
   这题之前根神跟我们说过，确实设计很精巧。

• 可以用带最大值的队列做（用两个带最大值的栈模拟队列）；
• 用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;
}