第一章 面试
面试的3个环节
行为面试：首先自我介绍（30s～60s），主要介绍自己的学习、工作经历。
- STAR模型介绍项目经历：
Situation 简短的项目背景。比如项目的规模，开发的软件功能，目标用户；
->Task 自己完成的任务。注意区分“参与、负责”等用词；
->Action 为完成任务自己做了哪些工作，是怎么做的。可以写基于xx工具应用了xx技术；
->Result 自己的贡献。可以用数值化的结果展示自己完成的功效。 - 可能遇到的问题：
- 你在项目中遇到的最大问题是什么，是如何解决的？
- 从这个项目中学到了什么？
- 什么时候会和其他团队成员（开发、测试、设计、项目经理）有什么样的冲突，是如何解决的？
- 应聘者掌握的技能：
此处指代除去参与过的项目之外还掌握的技能，注意了解、熟悉、精通的区别。
了解：上过课看过书，没做过项目。
熟悉：简历中大部分应该均属于熟悉的内容。
精通：得心应手，有信心和能力解决。 - 回答“为什么跳槽”：
尽量避免老板苛刻、同事难相处、加班频繁、工资太低。
技术面试
主要针对链表、树、栈、队列和哈希表等数据结构的考察，其中对链表和二叉树更为侧重。
应聘者提问
注意对不同的面试官提问对应的问题，例如和技术面试官可以提问产品等，但不能提问未来战略规划或录用流程等。
第二章 面试需要的基础知识
编程语言
C++
- Sizeof：
Q. 定义一个空的类型(class)，里面没有任何成员变量和成员函数，对其求sizeof，结果是多少？
A. 结果为1。空类型的实例不包含任何信息，本来求sizeof应该是0，但当声明该类型的实例时必须在内存中占有一定的空间，否则无法使用实例。占用内存的大小由编译器决定。
Q. 如果增加一个构造和析构函数呢？
A. 还是1，因为调用构造函数和析构函数只需要知道函数地址即可，函数的地址只与类型相关，与类型的实例无关，编译器不会因为两个函数的存在在实例内添加额外信息。
Q. 如果把析构函数标记为虚函数？
A. C++编译器一旦发现一个类型中有虚函数，就会为该类型生成虚函数表，并在该类型的每一个实例中添加一个指向虚函数的指针。在32位机器上，一个指针4个字节；64位机器上，一个指针8个字节；所以sizeof结果为4、8. 赋值运算符函数
Q. 请为CMyString添加赋值运算符函数。1
2
3
4
5
6
7
8
9class CMyString
{
public:
CMyString(char* pData = nullptr)
CMyString(const CMyString& str)
~CMyString(void)
private:
char* m_pData;
}A. 先释放m_pData占用的内存，然后为m_pData申请所需要的内存空间，再实现赋值。
1
2
3
4
5
6
7
8
9
10
11
12
13CMyString& CMyString::operator=(const CMyString &str)
{
if(this == &str)
return *this;
delete []m_pData;
m_pData = nullptr;
m_pData = new char[strlen(str.m_pData) + 1];
strcpy(m_pData, str.m_pData);
return *this;
}
数据结构
数组
数组与指针相互关联也区别。C++没有记录数组大小，在用指针访问数组元素时，需要确保没有超出边界。
Q. 下面代码的输出结果是什么？1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16int GetSize(int data[])
{
return sizeof(data)
}
int main()
{
int data1[] = {1,2,3,4,5};
int size1 = sizeof(data1);
int* data2 = data1;
int size2 = sizeof(data2);
int size3 = GetSize(data1);
printf("%d, %d, %d,\n", size1,size2,size3);
}
A. size1是求数组的大小，其大小为20，因为每个int类型变量为4个字节；size2本质上是求指针data2的大小，在32位系统上任何指针大小均为4；GetSize中，当数组作为函数的参数进行传递时，数组会自动退化位同类型的指针，所以size3为指针大小4.
Q. 在一个长度为n的数组里，所有的数字都在0～n-1的范围内。数组中某些数字是重复的，但不知道有多少个数字重复了多少次，请找出数组中任意一个重复的数字。例：{2,3,1,0,2,5,3} -> {2,3}
A.
- 哈希表。碰见一个数字，如果哈希表中不存在则在表中记录为1，否则为重复数字。时间复杂度O(n), 空间复杂度(n)。
- 重排序。因为数字都是位于0～n-1的范围内，如果没有重复的数字，数字i将出现在下标i的位置。因为每个数字最多比较2次就能回到对应的位置i，所以时间复杂度O(n), 空间复杂度(1)。
1
2
3
4
5
6for i in range(n):
while A[i] != i:
if A[i] != A[A[i]]:
swap(A[i], A[A[i]])
else:
print('A[i] == A[A[i]]')
Q. 在一个长度为n+1的数组里，所有的数字都在0～n的范围内。数组中至少有一个数字是重复的，请找出数组中任意一个重复的数字，但不能修改数组。例：长度为8的数组{2,3,5,4,3,2,6,7} -> {2,3}
A.
- 哈希表。同上，时间复杂度O(n)，但需要空间复杂度(n)。`
- 二分法(对数字所在的范围进行二分)。如果没有重复的数字，1～n的的范围内肯定只有n个数字，但现在有n+1个数字，一定至少有一个重复数字。把1～n以m=(1+n)/2分为两部分，分别为[1, m]和[m+1, n]。如果数组中[1, m]中的数字个数大于m，则重复项一定出现在[1, m]中，否则出现在[m+1, n]中。时间复杂度O(nlogn), 空间复杂度(1)。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26def main():
left = 1
right = n
while left <= right:
mid = (left + right) / 2
cnt = count(A, left, mid, n) # check A[i] in [left, mid]
if left == right:
if cnt > 1: return left # 检索到重复数字
if cnt > mid - start + 1: # [left, mid]的闭区间长度为‘mid-start+1’
right = mid
else:
left = mid + 1 # 因为下面用的A[i] >= left， 所以这里+1
def count(A:list, left:int, right:int, length:int):
if A == []:
return 0
cnt = 0
for i in range(length):
if A[i] >= left and A[i] <= right:
cnt += 1
return cnt
Q. 二维数组的查找。在一个二维数组中，每行按照从左到右递增、每一列按照从上到下递增的顺序排毒。输入一个数字判断数组中是否存在。
A. 从数组A右上角A[i][j]开始：如果待查找的数字k比A[i][j]小，则肯定出现在左边的列；如果待查找的数字k比A[i][j]大，则肯定出现在右边的行，
1 | 例：k = 7 |
字符串
Q. 将字符串的每一个空格替换为‘20%’。1
2
3在网络编程中，如果URL参数中包含特殊字符，例如空格，‘#’等，可能导致服务端无法正确识别。
一般将这些特殊字符转换为可识别的字符，例如%后跟ASCLL码两位十六进制表示的写法。
空格的ASCLL码值为32，即十六进制0x20，因此空格被标示为%20，同理，‘#’标示为%23.
A.
解法1，时间复杂度O(n^2): 从前向后，每次碰到空格就将剩余字符串向后移动2位。这样会造成先移动字串的重复移动。
解法2，时间复杂度O(n): 从后向前，双指针法。先遍历一边字符串，计算出替换后字符串长度，p1指向原始字符串末尾，p2指向替换后字符串末尾。接着逐个向前移动p1，每移动一位便将其拷贝到p2处，随即p2向前移动一位。当p1指向空格时，p1向前移动一位，p2向前移动3位同时逐个插入’0’、’2’、’%’。直到p1=p2时替换结束。
相关题目（合并字符串或数组）：有两个排序的数组A1、A2，内存在A1末尾有足够多的空间容纳A2。实现一个函数将A2中所有的数字插入A1，并且所有数字有序。
同解法2，分别从后向前比较A1和A2，将较大的放在A1的合适位置。
链表
链表是一种动态数据结构，在创建时无需知道链表长度，每当插入一个节点时再重新分配内存，内存分配不是在创建链表时一次性完成，没有闲置的内存，链表的空间效率比数组高。1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74class ListNode(object):
def __init__(self, value=0):
self.value = value
self.next = None
def CreateList(ValueList: list):
head = ListNode()
head.next = ListNode()
phead = head.next
n = len(ValueList)
for i in range(n):
phead.value = ValueList[i]
if i < n-1:
phead.next = ListNode()
phead = phead.next
return head.next
def AddToTail(head: ListNode, value: int):
'''
注意head或head.next为空
'''
pNew = ListNode(value)
if head == None:
head = pNew
elif head.next == None:
head.next = pNew
else:
phead = head.next
while phead.next != None:
phead = phead.next
phead.next = pNew
return head
def RemoveNode(head: ListNode, value: int):
'''
注意head或head.next为空
'''
if head == None or (head.next == None and head.value != value):
return head
elif head.value == value:
return head.next
phead = head
pToBeDelete = head.next
while pToBeDelete != None:
if pToBeDelete.value == value:
phead.next = pToBeDelete.next
break
else:
phead = phead.next
pToBeDelete = pToBeDelete.next
return head
def PrintList(head: ListNode):
tNode = head
while tNode != None:
print(tNode.value)
tNode = tNode.next
def PrintListReversingly(head: ListNode):
'''
递归，先处理next节点，再处理自身节点
'''
if head != None:
if head.next != None:
PrintListReversingly(head.next)
print(head.value)
树
树的逻辑：除根节点之外每个节点只有一个父节点，根节点没有父节点；除叶节点外所有节点都有一个或多个子节点，叶节点没有子节点。
树的遍历：先序遍历(根节点、左子树、右子树)，中序遍历(左子树、根节点、右子树)，后序遍历(左子树、右子树、根节点)，层次遍历（BFS、先第一层、再第二层…）
二叉树搜索树：左子树节点小于等于根节点，右子树节点大于等于根节点，搜索数据复杂度O(nlogn)。
- 二叉树的特例1: 大顶堆（根节点值最大），小顶堆（根节点值最小）。
- 二叉树的特例2: 红黑树，把树中的节点定义为红和黑，通过规则确保从根节点到叶节点的最长路径长度不超过最短路径的两倍。C++的STL中set、map均基于此。
Q. 根据先序遍历和中序遍历还原二叉树
A. 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41class TreeNode(object):
def __init__(self, value=0):
self.value = value
self.left = None
self.right = None
def Construct(preorder: list, inorder: list):
'''
根据先、中序遍历结果重构二叉树
'''
if len(preorder) == 0 or len(inorder) == 0:
return
return ConstructCore(preorder, inorder)
def ConstructCore(preorder: list, inorder: list):
'''
根据先序遍历和中序遍历还原二叉树
preorder中的第一个即为当前根节点，在inorder中找到根节点后再划分为左右两部分，分别对应左右子树的内容，递归建树
左子树递归条件：inorder中根节点左侧列表长度大于0，意味着左子树还有数据
右子树递归条件：inorder中根节点右侧列表长度大于0，意味着右子树还有数据
'''
nodeValue = preorder[0]
root = TreeNode()
root.value = nodeValue
inorderIndex = 0
while inorder[inorderIndex] != nodeValue:
inorderIndex += 1
if inorderIndex > 0:
leftInoreder = inorder[:inorderIndex]
leftPreorder = preorder[1:1+inorderIndex]
root.left = ConstructCore(leftPreorder, leftInoreder)
if inorderIndex < len(preorder)-1:
rightInoreder = inorder[inorderIndex+1:]
rightPreoreder = preorder[1+inorderIndex:]
root.right = ConstructCore(rightPreoreder, rightInoreder)
return root
Q. 给定一棵二叉树和其中的一个节点，如何找出中序遍历序列的下一个节点？书中的节点除了有两个分别只想左、右子节点的指针，还有一个指向父节点的指针。
A. 举例一棵二叉树如图所示，其中序遍历结果为：d b h e i a f c g，可以总结为三种情况：
1 | a |
- 如果一个节点有右子树(例如a、b、c、e)，那么其中序遍历的下一个节点为该右子树中最左子节点，即f、h、g、i。
- 如果一个节点没有右子树，且该节点为父节点的左子节点(例如d、h、f)，那么其中序遍历的下一个节点即为其父节点，即b、e、c。
- 如果一个节点没有右子树，且该节点为父节点的右子节点(例如i、g)，那么其中序遍历的下一个节点为沿着该节点的父节点向上遍历，直到找到一个节点是其父节点的左子节点，其父节点则为待找寻的节点，即a、null。
栈和队列
栈：一个特殊的数据结构，最后被push入栈的元素会被第一个pop出，通常是一个不需要考虑排序的数据结构，需要O(n)的时间才能找到栈中的最大、小值。
队列：第一个进入队列的元素会第一个出来。
Q. 用两个栈模拟队列，实现appendTail和deleteHead，分别完成再队列尾部插入节点和再队列头部删除节点的功能
A. 假设有两个栈S1、S2。当有元素{a,b,c}入栈时候，将其依次压入S1，此时S1={a,b,c}，其中c为栈顶。如果要执行deleteHead，则将S1中的元素逐个压入S2中，此时S2={c,b,a}，其中a为栈顶，S1.pop()即可。如果要执行appendTail，当S2不为空时，队列头永远处于S2中，将待添加元素直接压入S1即可。
算法和数据操作
应重点掌握二分查找、归并排序、快速排序
递归和循环
Q. 求斐波那契数列第n项
A. f(n) = f(n-1) + f(n-2)使用递归实现时，重复计算项过多，最好使用循环来实现，时间复杂度O(n)。1
2
3
4
5
6
7def Fib(n: int):
result = [0, 1]
i = 2
while i <= n:
result.append(result[i-2] + result[i-1])
return result[n]
Q. 青蛙跳台阶问题：一只青蛙一次可以跳上1或2级台阶，求该青蛙跳上一个n级的台阶共有多少跳法。
A. 显然这是斐波那契数列的变体问题。
Q. 铺砖问题：用2*1的小矩形去完全无重叠的覆盖2*8大矩形，共有多少种方法。
A. 把2*8的覆盖方法记为f(8)，用一个2*1的小矩形去覆盖大矩形最左边时有两种选择，竖着或横着。当竖着放时，右边还剩下2*7的区域；当横着放时，右边还剩下2*6的区域，即f(8)=f(7)+f(6)，显然这是斐波那契数列的变体问题。
查找和排序
查找：如果要求在（完全或部分）排序的数组中查找一个数字、或统计某个数字出现的个数，那么我们都可以尝试用二分查找。
排序：应熟记各类排序算法的对比。
| 算法 | 稳定性 | 平均复杂度 | 最差复杂度 |
|---|---|---|---|
| 直接插入 | 稳定 | n2 | n2 |
| 冒泡排序 | 稳定 | n2 | n2 |
| 归并排序 | 稳定 | nlogn | nlogn |
| 希尔排序 | 不稳定 | n1/3 | n2 |
| 堆排序 | 不稳定 | nlogn | nlogn |
| 快速排序 | 不稳定 | nlogn | n2 |
| 直接选择 | 不稳定 | n2 | n2 |
Q. 手写快速排序
A. 快排思想：
- 首先选择一个partition(可以是随机选或直接选最左侧)，定义左右两个指针i=left,j=right;
- 从右侧开始，如果numbers[j]>=partition，则持续向左扫描j–，直到有numbers[j]< partition，此时swap(numbers[i],numbers[j]);
- 再从左侧开始，如果numbers[i]<=partition，则持续向右扫描i++，直到有numbers[i]>partition，此时swap(numbers[i],numbers[j]);
- 直到i==j为止，此时partition左侧的数字均小于partition，右侧则均大于partition。
- 递归qsort(left, i-1)和qsort(i+1, right)
1 | def qsort(numbers: list, left: int, right: int): |
Q. 旋转数组的最小数字：输入一个递增排序的数组的一个旋转(旋转：把一个数组开头若干个元素搬到数组末尾)，输出旋转数组的最小数字。例如：{3,4,5,1,2}为{1,2,3,4,5}的一个旋转，最小值为1.
A. 为了利用到排序信息，使复杂度降低到nlogn，使用二分查找。需要注意，如果mid处的数字和左右两端都相等时，无法判断最小值位于哪个序列中，所以只能顺序查找。1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24def revolveArray(numbers: list, left: int, right: int):
if numbers == None or len(numbers) == 0 or left > right:
return
# 如果numbers[left] < numbers[right]，说明已经是一个排好序的数组
while numbers[left] >= numbers[right]:
mid = int((left + right) / 2)
print(mid, left, right)
if right - left == 1:
return numbers[right]
elif numbers[left] == numbers[right] and numbers[left] == numbers[mid]:
print("只能顺序查找")
# 如果mid位于后半个递增序列，则最小值出现在mid前
elif numbers[mid] <= numbers[right]:
right = mid
# 如果mid位于前半个递增序列，则最小值出现在mid后
elif numbers[mid] >= numbers[left]:
left = mid
return numbers[left]
回溯法
Q. 请设计一个函数，用来判断在一个矩阵中是否包含某字符串所有字符的路径。路径可以从矩阵中任意一格开始，每一步可以向上下左右移动一格，每一格只能走一次。1
2
3a b t g
c f c s
j d e h
例如能找到bfce的路径，但不存在abfb的路径。
A. 利用回溯法解决。回溯法的解题思路：
- 需要使用到：全局地图、是否访问变量、当前位置、已访问到目标序列的位置
- 对地图进行全局遍历，对每一个点进行回溯探索
- 对(i,j)进行探索：
- 判断(i,j)是否出界、是否已被访问、是否满足待探索序列的当前位置变量
- 不满足则False
- 满足则先判断当前探索的序列是否已达成了题目要求，满足则True
- 否则标记当前位置为已探索，递归(i,j)上下左右各个位置，例如(i+1,j)…
- 如果(i,j)上下左右各个位置均为False，则撤销当前位置的探索标记，回到上一位置。
1 | def searchPath(chArray: list, string: str): |
Q. 地上有一个m行n列的方格，一个机器人从坐标(0,0)的格子开始移动，每次可以上上下左右移动一格，但不能进入行列坐标数位之和大于k的位置，例如当k=18时，机器人能进入(35, 37)，因为3+5+3+7=18，但不能进入(35, 38)，因为3+5+3+8=19>k。请问机器人能够到达多少格子。
A. 简单的回溯法，类似深度优先搜索，但与DFS不同的是，回溯法遇到不合法的情况后会退到上一个节点继续剩下的位置探索
- 思路为：首先构造需要的辅助变量，包括地图信息，行列数，要求序列、访问标志
- 建立整个地图的遍历
- 对地图每个节点进行搜索
- 对满足要求的节点标记为访问，然后依次回溯探索其上下左右的各个位置
1 | def searchRobotPath(rows: int, cols: int, k: int): |
动态规划与贪婪
动态规划：
- 如果需要求一个问题的最优解(最大值或最小值)，而且该问题能够分解为若干个子问题，并且子问题之间还有重叠的更小子问题，考虑用DP求解。
- DP解决问题时通常从上往下分析问题、从下往上求解问题。
- 通常从解决小问题开始，并把已经解决的子问题最优值存储在数组中。
Q. 剪绳子：有一根长度为n的绳子，要剪成m段，使每段绳子长度(整数)的乘积最大，其中n,m为整数。例如n=8时，剪成2,3,3三段乘积最大。
A. 有贪心和动归两种解决方案。
- 贪心：只要保证在大于等于5米之外，尽可能的剪成长度为3的绳子段；在等于4米时，尽可能剪成两个长度为2的绳子段。
- 动归：$ f(n) = max_{i \in n} f(i)*f(n-i) $
1 | def maxProductAfterCutting_dp(length: int): |
位运算
位运算规律：
| 与& | 或or | 异或^ |
|---|---|---|
| 0&0=0 | 0or0=0 | 0^0=0 |
| 0&1=0 | 0or1=1 | 0^1=1 |
| 1&0=0 | 1or0=1 | 1^0=1 |
| 1&1=1 | 1or1=1 | 1^1=0 |
| 左移<< | 右移>> |
|---|---|
| 左移补0 | 右移视情况 |
| 10001010<<3:=01010000 | 负数补1:10001010>>3:=11110001 |
| 00001010<<2:=00101000 | 正数补0:00001010>>2:=00000010 |
Q. 输入一个整数，输出该数二进制表示中1的个数，例如9=1001，则输出2。
A. 把一个整数减去1，再和原整数做与运算，会把该整数右边的1变成0，所以能执行多少次与运算就代表有多少个1.
- 1001: (1001-0001)&1001=1000&1001=1000 -> (1000-0001)&1000=0111&1000=0000
- 1010: (1010-0001)&1010=1001&1010=1000 -> (1000-0001)&1000=0111&1000=0000
1
2
3
4
5
6
7
8
9
10def numberOf1(number: int):
if number == 0:
return 0
cnt = 0
while number != 0:
cnt += 1
number = number & (number-1)
return cnt
面试官可能提问：能把右移换成处以2么，答案是不能，因为右移操作效率远高于除法。
Q. 用一条语句判断一个整数是不是2的整数次方。
A. 变式：2的整数次方的二进制数中只有一位1，if n & (n-1) == 0
Q. 输入两个整数m,n，计算需要改变m中多少二进制位才能变为n。
A. 变式：先求异或，再统计有多少位1.
