# 剑指offer
## 1. 面试的流程
### 1.1 面试官谈面试
### 1.2 面试的3种形式
#### 1.2.1 电话面试
#### 1.2.2 共享桌面远程面试
#### 1.2.3 现场面试
### 1.3 面试的3个环节
#### 1.3.1 行为面试环节
##### 1 项目经验
##### 2 应聘者技能
###### 技能掌握程度
* 了解
* 仅 上过课/看过书， 妹做过实际项目
* 不列出肤浅的了解的技能，除非职位的确需要
* 熟悉
* 实际项目中使用某项技术较长时间，通过查阅文档可以解决大部分问题
* 已经工作过 / 项目开发过程中所用到的技能 ，可用熟悉
* 精通
* 使用得心应手
* 项目开发中， 别人请教这个领域的问题时，有信心有能力解决
* 能轻松地回答这个领域里绝大多数问题
##### 3 为啥跳槽
* 不抱怨， 不流露负面情绪
###### 避免以下
* 老板苛刻
* 同事难相处
* 加班频繁
* 工资低
#### 1.3.2 技术面试环节
* 基础扎实
* 代码质量高
* 分析问题思路清晰
* 优化时空效率
* 学习沟通等能力
##### 1 基础扎实
* 编程语言
* 数据结构
* 链表（常问）： 插入 删除
* 二叉树（常问） ：遍历（<-循环/递归）
* 查找 排序
* 二分查找
* 归并排序/快速排序
* 动规 贪心
##### 2 高质量代码
* 考虑全面
* 边界条件
* 特殊输入
* 鲁棒性
##### 3 思路清晰
###### 方法
* 举简单例子以便自己理解问题
* 数据结构简化题目
* 分治/动态规划
##### 4 优化效率的能力
* <- 各种数据结构的优缺点
* 熟练掌握常用算法
##### 5 优秀的综合能力
* 沟通
* 合作
###### 学习能力检测
* 问最近学啥
* 学习新概念
###### 知识迁移能力
* 某题和其上一题有关这种
###### 抽象建模/发散思维
* 抽象建模 -> 用数据结构表示
#### 1.3.3 应聘者提问
* <- 面试官想了解应聘者最关心的问题
* -> 要问1~2，不然显得没兴趣
* 视面试官职务
* 不问薪水，此和hr谈
* 不问面试结果
* <- 白问
* <- 显得无自我评估能力
* 与应聘 职位/项目 相关问题
* <- 上网搜索公司大概做啥
* <- 面试官说过的项目
## 2. 面试需要的基础知识
### 2.1 面试官谈基础知识
* 陈黎明
* os理解程度
* 一门编程语言的掌握程度。上手新的快，理解深
* 常用的算法和数据结构。不了解的程序员基本只能写写'hello world'
### 2.2 编程语言
###### 考核方式
* 直接问语法
* 写代码解决问题
###### 语言类别
* c <- 底层开发（如驱动)
* c++ <- linux
* c# <- windows
* java <- 跨平台
* object c <- ios
* perl, python <- 脚本语言
#### 2.2.1 c++
* 都要掌握
##### 1 概念理解
* c艹关键字理解程度
* sizeof
```
// 实例必须要占用空间
sizeof(struct none{}) = 1 <- visual studio
// 构造析构函数，只需知函数地址即可 && 无关于实例
sizeof(stuct none{只有 构造/析构函数}) = 1
sizeof(struct none{有个虚函数}) = 4 <-32bit
sizeof(struct none{有个虚函数}) = 8 // 64位机器上指针长8byte
```
##### 2 脑中运行
* 复制构造函数的参数，只能是 常量引用
* 不引用的话，就会无限调用复制构造函数
##### 3 实现 类/成员函数
* c艹
* 《effective c++》适合突击
* 列举了c艹常见问题及解决技巧
* 提的问题常考
* 《c++ primer》全面了解
* 《深度探索c艹对象模型》
* 理解c艹难题
* 《The c艹 programming language》 全面深入掌握
###### eg1
* c艹基础语法
* 内存泄漏的理解
* 异常安全原则
* 申请内存分配失败后，不改变原先的
```
; eg1 赋值运算符函数
```
#### 2.2.2 c sharp
* 常考与c艹区别
* struct && class
* c艹中struct和class区别
* struct中 成员变量&&成员函数 默认访问权限为public
* c#中
* 成员变量&&成员函数 在 struct和class中 默认为private
* struct定义值类型，在栈上分配
* class定义引用类型，在堆上分配
* c#中Finalizer方法(<- 运行时垃圾回收调用), Dispose方法释放资源
* c#可有 静态构造函数
* 第一次使用前 调用一次
* c#特有功能
* 反射
* 应用程序域
* 其它
* 书
* 《Professional c#》
* 附录介绍区别
* 《CLR via c#》
* c#
* clr
* .net
* 装箱卸箱
* 垃圾回收
* 反射
* 其它
###### eg2 实现singleton模式
* c#基础语法
* 单例模式
* 能多线程运行（加锁
### 2.3 数据结构
* 是面试考察的重点
* 主要考察
* 数组
* 连续内存存数字
* 字符串
* 连续内存存字符
* 链表（最高频率
* 鲁棒性
* 树（最高频率
* 栈
* 递归相关
* 深入理解帮住解决很多算法问题
* 队列
* bfs
* 深入理解帮住解决很多算法问题
#### 2.3.1 数组
* 简单
* 内存连续，顺序存储
* -> 时间效率高 -> 实现哈希表 -> 快查
* 预分配 -> 空间效率低
* <- vector
* 每次扩容时，新容量 = 2 * 之前的容量
* 旧数组复制到新数组，释放之前的内存
###### c艹
* sizeof
* sizeof(数组) = 数组大小
* sizeof(指针) = 4 <- 32bit
* 数组作为参数时，数组退化指针
###### eg3 数组中重复的数字
* 扫描排序后的
* 哈希表
* 时O(1), 空O(1)
```
```
#### 2.3.2 字符串
* 频率高
* <- 优化 <- 特殊规定
###### c/c艹/csharp字符串特性
* c/c艹
* 以 '\0' 结尾
* 注意越界
* 常量字符串 在单独的内存区域
* csharep
* System.String
* <- 不可改变
* StringBuilder
* 可改
#### 2.3.3 链表
* 面试中使用最频繁
* 结构简单
* 操作代码量少
* 哈希表、有向图等复杂数据结构，一个操作代码量大 -> 几十分钟的面试很难完成
* 是动态数据结构，需要指针操作
* 需较好编程功底
* 灵活
* 题可以有挑战性
#### 2.3.4 树
* 涉及大量指针
* 考察指针力
* 大多二叉树
* 遍历最重要
###### 遍历
* 遍历方式
* 前序
* 中序
* 后序
* 上三种都可 递归 / 循环
* 层次
* 用队列
* 前序遍历
“`
// 递归遍历
private void preorder(List
if (node == null) return;
l.add(node.val);
if (node.left != null)
preorder(l, node.left);
if (node.right != null)
preorder(l, node.right);
}
// 非递归遍历
Stack
s.push(root);
while (!s.empty()) {
TreeNode n = s.pop();
l.add(n.val);
if (n.right != null) {
s.push(n.right);
}
if (n.left != null) {
s.push(n.left);
}
}
“`
* 中序遍历
“`
// 递归
private void inorder(List
if (n.left != null)
inorder(l, n.left);
l.add(n.val);
if (n.right != null)
inorder(l, n.right);
}
// 非递归
Stack
TreeNode p = root;
while (!(p==null && s.empty())) {
while (p != null) { //来到最左边
s.push(p);
p = p.left;
}
if (!s.empty()) {
// 这步运行之后即是到达最左边的叶子节点
p = s.pop(); // p分为是否是叶子。是叶子则程序继续运行再次来到这里遍历父节点(这步之后的程序则是从左子节点到父节点)，不是叶子(有右节点)则遍历右子节点树
l.add(p.val);
p = p.right;
}
}
“`
* 后序遍历
“`
// 非递归
Stack
TreeNode p = root, vis = null;
while (!(p == null && s.empty())) {
while (p != null) {
s.push(p);
p = p.left;
}
if (!s.empty()) {
p = s.peek();
if (p.right != null && vis != p.right) {
p = p.right;
} else {
p = s.pop();
l.add(p.val);
vis = p;
p = null;
}
}
}
“`
* 层次遍历
“`
public List
List
if (root == null) return l;
Queue
q.offer(root);
int level = 0;
while (!q.isEmpty()) {
l.add(new ArrayList
int levelLength = q.size();
while ((levelLength–) > 0) {
TreeNode n = q.poll();
l.get(level).add(n.val);
if (n.left != null) {
q.offer(n.left);
}
if (n.right != null) {
q.offer(n.right);
}
}
++level;
}
return l;
}
“`
* 深度
“`
// 递归
public int maxDepth(TreeNode root) {
if (root == null) return 0;
return Math.max(maxDepth(root.left), maxDepth(root.right)) + 1;
}
“`
* 常直接/间接被考察
* 有很多特例
* 二叉搜索树
* 堆
* 最大堆
* 最小堆
* 红黑树
* 节点分 红黑二色
* 根节点to叶节点 的最长路径 《= 2x最短路
* c艹 stl之(multi)set, (multi)map等基于此实现
#### 2.3.5 栈和队列
###### 栈
* 计算机中常见
* 如线程栈存储 函数调用的参数返回地址临时变量等
* 后进先出
* 常不考虑排序
* 一般O(n)寻min/max
###### 队列
* 先进先出
* 栈 队列 相互联系
* 两个栈 => 队列
* 两个队列 => 栈
### 2.4 算法和数据操作
###### 算法
* 常考似数据结构
* 常可 递归/循环
* 递归 更简洁 性能低
* 排序 查找 常考
* 二分查找
* 归并排序 && 快排
* 二维数组搜索路径
* <- 回溯法
* <- 常递归实现
* 或栈实现
###### 位运算
#### 2.4.1 递归和循环
* fibonacci
* 自上而下递归 <- 效率低
* 自下而上循环 <- 实用
* 生僻公式O(logn) <- 不实用
##### 2.4.2 查找和排序
###### 查找
* 分类
* 顺序查找
* 二分查找 <- 循环 / 递归
* <- 一定掌握
* 哈希表查找 <- 主要考察数据结构而非算法
* 时O(1)查找元素，效率最高
* 缺点： 需要额外空间
* 二叉排序树查找 <- 主要考察数据结构而非算法
* -> 二叉搜索树
* (部分)排序的 数组中查找 数字/数字出现之次数
* <- 二分查找
```
public int search(int[] nums, int target) {
int start = 0, end = nums.length - 1;
int mid = (start + end) >> 1;
while (start <= end) {
mid = (start + end) >> 1;
if (target == nums[mid]) return mid;
else if (target < nums[mid]) {
end = mid-1;
} else {
start = mid+1;
}
}
return -1;
}
```
###### 排序
* 分类
* 插入排序
* 冒泡排序
* 归并排序
* 快排
* 常要手写 -> 记
* 其它
* 常比较各类优劣
* 记
* 算法特点
* 额外空间消耗
* 平均时间复杂度
* 最差时间复杂度
###### 面试时
* 问清应用环境
* 问清约束条件（时间空间限制）
* 冒泡排序
“`
for (int i=0; i
int temp = nums[k];
nums[k] = nums[k+1];
nums[k+1] = temp;
}
}
}
“`
* 简单选择排序
“`
for (int i=0; i
nums[k+1] = nums[k];
–k;
}
++k;
nums[k] = tmp;
}
“`
* 归并排序
“`
private void merge(int[] nums, int left, int mid, int right) {
int i1=left, i2=mid + 1;
int[] tmpArr = new int[right – left + 1];
int c = 0;
while (i1 <= mid && i2 <= right) {
if (nums[i1] <= nums[i2]) {
tmpArr[c++] = nums[i1++];
} else {
tmpArr[c++] = nums[i2++];
}
}
while (i1 <= mid) { tmpArr[c++] = nums[i1++]; }
while (i2 <= right) { tmpArr[c++] = nums[i2++]; }
for (int i=left; i<=right; ++i) {
nums[i] = tmpArr[i-left];
}
}
private void mergeSortRe(int[] nums, int left, int right) {
if (left == right) return;
int midIndex = (left + right) >> 1;
mergeSortRe(nums, 0, midIndex);
mergeSortRe(nums, midIndex + 1, right);
merge(nums, left, midIndex, right);
}
“`
* 时O(n)，空O(1)的排序算法
“`
// kong
// nums里的数属于[0, MAX]
int MAX = 100;
// 空O(1) 为常量
int[] count = new int[100];
System.out.println(count.length);
// 时O(n)
for (int i=0; i
int pivotIndex = Partion(nums, left, right);
quickSort(nums, left, pivotIndex – 1);
quickSort(nums, pivotIndex + 1, right);
}
“`
* 堆排序
“`
// 大顶堆
public void bigHeapify(int[] nums, int index, int length) {
int leftI = 2 * index + 1, rightI = 2 * index + 2;
if (leftI < length && nums[leftI] > nums[index]) {
int tmp = nums[index];
nums[index] = nums[leftI];
nums[leftI] = tmp;
bigHeapify(nums, leftI, length);
}
if (rightI < length && nums[rightI] > nums[index]) {
int tmp = nums[index];
nums[index] = nums[rightI];
nums[rightI] = tmp;
bigHeapify(nums, rightI, length);
}
}
public void buildBigHeap(int[] nums) {
for (int i= (nums.length / 2 – 1 ); i >= 0; –i) {
bigHeapify(nums, i, nums.length);
}
}
public void bigHeapSort(int[] nums) {
buildBigHeap(nums);
int length = nums.length – 1;
while (length >= 1) {
int tmp = nums[0];
nums[0] = nums[length];
nums[length] = tmp;
bigHeapify(nums, 0, length);
–length;
}
}
“`
* 比较
| 排序方法 | 平均情况 | 最坏情况 | 辅助空间 | 稳定性 | 适用 |
| — | — | — | — | — | — |
| 冒泡排序 | O(n^2) | O(n^2) | O(1) | 稳定 |
| 简单选择排序 | O(n^2) | O(n^2) | O(1) | 不稳定（把最小元素放到前面是来时，前面的被放到了后面） |
| 直接插入排序 | O(n^2) | O(n^2) | O(1) | 稳定 | 少量元素排序 |
| 归并排序 | O(nlogn) | O(nlogn) | O(n) | 稳定(两部分判断时，应判断 前一部分的<=后一部分的，=不能少) |
| 快速排序 | O(nlogn) | O(n^2) [主要是递归造成的栈空间使用] | O(logn)~O(n) | 不稳定(遍历完后，基准和tail交换时，前面的放到了后面来) |
| 堆排序 | O(nlogn) | O(nlogn) | O(1) | 不稳定(heapSort里将顶与最后一个元素交换时)
##### 2.4.3 回溯法
* 本质上其实是dfs...
##### 2.4.4 动态规划与贪婪算法
* dp特点
* 求最优点
* 最优解依赖于各子问题最优解
* 问题分为多个子问题后，子问题间还有更小的子问题
* 自上而下的递归思路分析 && 自下而上的循环
* 子问题最优解用数组保存(1/2维) 或 从下往上计算
* 由子问题解计算大问题解 -> 避免重复计算
* 动态规划
* 有多个选择则都尝试接着找出最优
* 动规中，分解子问题时特殊选择一定得到最优解
* -> 可贪婪算法
##### 2.4.5 位运算
* n = (n-1)&n -> n中最右边的1变成0
* ( x1 ^ x2 )中1的个数 = x1变成x2需要改变的bit位数
## 3 高质量的代码
### 3.1 面试官谈代码质量
* 容错处理能力 <- alipay
* 特别输入如何处理
* 代码不能只是针对 假想的正常值进行处理
* 要考虑异常情况
* 要考虑资源回收等问题
* 不能该掌握的妹掌握，提醒了还不知道 <-autodesk
* 浮点数因为精度问题，不能用==去判断是否相等
* 印象大打折扣 <- intel
* x 变量 函数命名妹章法 x
* x 解决具体问题找不到最合适的数据结构 x
* -> 程序写得太少 不够熟悉
* 程序正确性&&鲁棒性 <- 微软 sdeII
* 方面
* 输入参数检查
* 处理错误 异常方式
* 命名方式
* 要求
* 学生：正确性之外的基本能容忍，提示后希望能很快解决
* 有工作经验：不能容忍考虑不周，明显鲁棒性错误
### 3.2 代码的规范性
* 规范性方面
* 清晰的书写
* 面试大都是手写代码
* 代码量大都<=50行 -> 不用担忧妹时间写
* 清晰的布局
* 手写注意 缩进 对齐之类的
* 合理的命名
* 推荐用 完整的英文单词组合 命名 变量/函数
* BinaryTreeNode * pRoot
* 能看出 变量/函数 的用途
### 3.3 代码的完整性
###### 三方面确保完整性
* 功能测试
* 边界测试
* 输入范围
* 循环/递归 终止
* 负面测试
* 错误输入
###### 三种错误处理的方法
* 返回值
* 很多windows api如此, 0->成功, 否则失败
* 错误发生时设置全区变量
* windows可通过GetLastError
* 调用者忘检查
* 抛出异常
* c#推荐 try catch，c无异常
* 程序执行顺序被打乱，影响性能。
* 和面试官讨论具体如何处理
* 采用返回值处理错误，则说返回值含义 -> 表示考虑到了情况
###### 题
* 实现特定库函数(尤其是处理数值和字符串的函数)的功能是一类常见面试题
* 平时能熟悉库函数&&理解库函数的实现原理
* double除了平时判断时要注意(double = 0 <=> 绝对值很小), double作为返回值时也要注意。
* 除以2都用>>1
* 判断是否为奇数用 (x&0x1 == 1)
* char数组初始化后默认为0而不是’0′
* 考虑代码的可扩展性，如类似sort那样抽离出判断的函数
###### 面经
* 实习很看重基础，可以直接按照面经准备，写到简历上的一定要保证面试官问不住泥。 <- by ywt, 2020-02-13
* 面试官问啥答啥，有不明白就提出疑问，要营造一种技术交流的氛围。
###### java方法参数里的对象也可能是null, 要判断
### 3.3 代码的鲁棒性
* 面试时最简单实用的是 检查输入
* 面试官检查代码的方法也是 用测试用例进行测试
* 没有特别要求的话，二叉树的遍历用递归去做，因为代码简洁
###### 题
* 用一个指针遍历链表不能解决问题时，可尝试用两个，让其中一个指针遍历快一些，或让先走若干步。
###### 题
* 20没做
* 23没找到题
## 4 解决面试题的思路
### 4.1 面试官谈面试思路
* 编码前讲自己的思路是一个考察指标。一开始就编码的除非后面很优秀，否则很容易通不过 --支付宝的
* 想让应聘者讲思路并证明 --百度的
* 想让应聘者讲思路。如果应聘者没想清楚就动手，本身就不是太好。应聘者可举例、画图等方式解释清楚。 --sap的
* 一般最好在开始写之前讲清思路和设计 --淘宝的
* 想让应聘者讲思路，讲错了就让ta证明以便ta自己发现 --微软的
### 4.2 画图让抽象问题形象化
* 应聘者需要向面试官解释自己的思路，说不清的画图，看图讲解，这显示良好的沟通交流能力
### 4.3 举例让抽象问题具体化
* 若要求处理二叉树的遍历序列，则可以先找到二叉树的根节点，接着拆分成左右子树接着处理
### 4.4 分解让复杂问题简单化
* 若求符合一定条件的排列组合，则求出所有再筛选
* 若求多个元素的排列组合，则把这些元素们分成 一个+另外，接着递归
### 4之总结
* 做算法题时，举例分析写出大部分代码后，再完整带入一个例子进行代码完善而不是立即跑起程序进行测验(显得不好)
* 分治、动态规划都是分解问题的思路
## 5 优化时空效率
### 5.1 面试官谈效率
* 面试时对时空有要求 --baidu
* 内存不是特别大的话，时更重要因改进时间复杂度对算法要求更高 --英伟达
* 普通应用空间换时间，因(用户更关心速度、空间一般够); 嵌入式设备则空间换时间，因空间少 -- 微软
### 5.2 时间效率
* 首先想到的直观的解法不妨说出
* 提示我们还有更好的办法时，不能轻言放弃，而要积极思考、不同角度思考题，而非遇难题退缩
* 许多公司常问海量输入数据相关问题。这种问题中，内存不能装入所有输入数据，只能渐渐的读入一些，因此类似Partion()之类的操作不适用
* 解法多种、各有优缺点时，要问清
* 数据量多大、能否一次性载入内存
* 是否可修改引用类型所指向的(即输入数组之类的)
* 若频繁查找、替换替换 min/max, 应用二叉树(堆、红黑树等实现)
* 考虑用map时，若键的范围很小，如键只是字母，那就可以用数组而不是map
### 5.3 时空平衡
### 5.4 本章小结
## 6 面试中的各种能力
### 6.5 发散思维能力
* 不用新变量交换两个变量
```
a = a ^ b;
b = a ^ b;
a = a ^ b;
```