面试流程

你可以通过观看模拟面试视频来了解面试流程：

算法面试中需要保证自己完成了 A (Ask) C (Conform) T (Test) 三个步骤：

Ask - 提问

无论这道题对你来说是简单还是难，每道算法题都需要按照以下模版输出文档：

Questions:

边听问题边记录关键点，确保不会因为网络或者英语沟通问题错误理解题目，写下来的话可以与面试官共同确认题目，不需要过于注重语法

备注

如果有一些小问题你不确定，不一定要提问，例如 “我假设题目的输入只会包含 a 到 z 字符” 说出自己的假设，如果面试官没有反驳的话就继续讲下去。这样的话可以减少不必要的提问。

Input:

记录题目输入的类型，例如纯数字，仅包含 a-z 的字符串

Output:

记录输出的类型

Constraints:

输入范围，特殊的时空复杂度要求，例如不能使用额外的空间

Test case:

不影响受面试官的测试用例所影响，尝试列出两个或者以上合适的测试用例，可以用作最后的检查环节

备注

合适的测试用例要求指的是不会太过特殊而且能够尽量覆盖题目要求的测试用例。

Solution1:

一句话简介思路，记录时空复杂度

文档记录示例： Two Sum

Questions: 
given a unsorted list array and target T
return two index,  array[i] + array[j] = T
exactly one solution

Input: 
array of integer [a1, a2, ... an]

Output:
[i, j]

Constraints:
1 ≤ array.length < 10^6
0 ≤ array[i] < 10^8

Test Case:
array = [2,7,11,15], T = 9 return [0, 1]
array = [3, 3], T = 6 return [0, 1]

Solution1: 
Idea: Two for loop to check all possible answer 
Time: O(n^2)
Space: O(1)

Solution2:
Idea: Use Hashmap to record element seen before
Time: O(n)
Space: O(n)

根据对应不同类型的输入你可以提出相应的问题：

输入	输入规模	特点	可能的解法
数字	数字范围	是否是整数	递归，二分查找
字符串	字符串长度	字符集范围	双指针，滑动窗口，栈，动态规划，贪心
数组	数组长度	元素是否唯一是否有序	哈希表，排序，双指针，滑动窗口，动态规划，贪心
矩阵	矩阵大小	值的范围是否可以修改矩阵	BFS，DFS，Union Find，动态规划
链表	链表长度	单向还是双向链表是否有环	快慢指针，哈希表
二叉树	节点数量	是否是特殊类型的二叉树是否平衡	递归，栈
图	节点数量	是否有环是否是简单图节点值的范围	BFS, DFS, Union Find, Dijkstra

备注

而且你也可以通过记录该输入的不同维度来进行解题，例如给定字符串，除了记录字符串本身之外，某些情况下还可以记录它的 ASCII 码，索引位置，出现频率等。

通过输入规模，也可以反推时间复杂度，从而判断可能使用哪些算法（注：这个技巧不适用全平台）：

范围	时间复杂度	可能的解法
0 < n < 10^9	O(log(n)) / O(根号n)	二分查找，位运算，快速幂，数学解
0 < n < 10^6	O(n)	栈，双指针，滑动窗口，哈希表，并查集，KMP，一维动态规划
0 < n < 10^5	O(nlog(n))	排序，排序后双指针/二分查找，分治，堆，Dijkstra 算法，线段树
0 < n < 10^4	O(n^2)	双层遍历，二维动态规划，Bellman-Ford 算法
0 < n < 200	O(n^3)	三层遍历，Floyd–Warshall 算法
0 < n < 30	O(2^n) / O(n!)	NP 问题，状态压缩的动态规划

Conform - 确认

确认分为三步：

先简单解释你的解题思路

a. 建立一个哈希表
b. 遍历数组，对于数组每个元素 i，判断 v = target - i 是否出现在哈希表中，如果是的话，返回对应的索引
c. 将元素 i 及其索引存储到哈希表中
d. 遍历所需的时间是 O(n)，哈希表所需的空间是 O(n)，n 是数组的长度

利用白板或者文档，使用几个例子（包括简单的例子，特殊的例子）验证自己的思路是否正确，对于题目 Two Sum，可以使用两个例子（在本题中，由于答案有且只有一个，所以不需要列举不可能的例子）：
```
[-1, 1], target = 0
[1, 2, 4], target = 5
```

对于例子 1 可以这样解释：

    a. 建立一个哈希表
    b. 遍历数组，第一个元素为 -1，0 - 1 不在哈希表中
    c. 将元素 -1 及其索引 0 存储到哈希表中。此时哈希表为 {-1: 0}
    b. 继续遍历数组，第二个元素为 1，0 - 1 在哈希表中，返回对应的索引

正式写代码之前要问面试官，“现在我可以按照这个思路写代码了吗？”。确保你的解法是面试官想要的解法。要记住，算法面试要实现面试官能理解并且期望你实现的解法，而不是仅仅正确的解法。即使代码正确但是没有向面试官解释清楚的话，最终的评价也不会太好。

Test - 检查

写完代码后，主动使用一两个例子（包括简单的例子，特殊的例子）以及 Trace Table 技巧来检查代码中是否出现问题，同时也可以在检查的过程中添加遗漏的注释，改正不规范的变量命名。

常见问题

以下为算法面试中的常见问题：

自我介绍

没有准备自我介绍，自我介绍缺乏亮点
- 解决方法：你应该预先写下自我介绍的文档，主要分为两个部分：
  1. 现阶段情况：对于校招/实习，阐述你所在的学校以及列举较出色的学术成绩，例如奖学金或者高 GPA 或者高分的专业课。对于在职跳槽，阐述你的工作经验以及擅长的技术方向。
  2. 过往经验：针对简历上面的项目，着重讲述个人职责中的亮点，例如用户量，并发量以及解决了哪个难点。
对简历上的项目以及内容不熟悉
- 解决方法：对于简历上面的项目，你需要进行简单的介绍，对于简历上列举的技能列表，你需要了解它们的使用场景。
语言表达不流畅，出现太多“呃”或者词不达意
- 解决方案：多练，有意识地进行调整，例如用停顿来代替“呃”
自顾自说话，缺乏和面试官的互动
- 解决方案：避免大段的自我介绍，如果面试官对里面的内容感兴趣会深入提问。

做题过程

没有问清楚数据范围以及类型
- 解决方案：养成先问问题在做题的习惯，有些题目的数据范围会极大地影响选择哪个解法。
没有表现出思考的过程就直接要 hint
- 解决方案：可以根据数据范围以及类型反推时间复杂度以及解法类型（动态规划，BFS，双指针），先尝试分析问题，然后提供几个解法类型给面试官选择来要 hint。
没有提出暴力解
- 解决方案：先提出暴力解，然后再去想更优的解法。除非你非常有把握，否则不要直接就想最优解，如果你不提出暴力解的话，面试官可能以为你连暴力解都不会。
没有找到好的例子来讲解思路
- 解法方案：尝试用一些简洁的例子向面试官讲解你的思路
没有利用文档做好记录
- 解决方案：利用文档记录：
  1. 数据范围以及类型
  2. 解法的时空复杂度，分析过程
  3. 代码以及注释
缺乏注释
- 解决方案：在主动检查的过程中可以在关键点添加注释
缺乏主动检查
- 解决方案：养成主动检查的好习惯，写完代码后，你需要主动检查而不是等着面试官提出检查或者发现问题再进行改正。

面试流程

Ask - 提问​

Questions:​

Input:​

Output:​

Constraints:​

Test case:​

Solution1:​

常见问题​

自我介绍​

做题过程​