面试流程模版（测试）

理解题目

目标

清晰地理解题目的要求以及限制条件，包括以下策略：

通过关键点，Testcase 来确保理解题目。
与面试官书面确认你正确理解题目，并且针对限制条件和边界情况进行提问

通过关键点，Testcase 来确保理解题目

在面试官提供题目的文字描述 / 面试官口述题目后

- 理解题目的沟通关键句："Let me write down some note to make sure I understand the question."
- 行动 1：在 IDE 或者文档中记录听到的关键点，每个关键点不应该过长，例如对于 Two Sum 这道题目：
    - given an array of int
    - find two element sum to target
    - return index
- 行动 2：如果不理解题目的话，那么可以通过以下方式帮助理解：
    - 先说出你对题目的理解，然后请面试官纠正

        > "Please correct me if I'm wrong, so the question is ..."
    - 使用 Testcase 来确认和理解题目，如果面试官没有提供 Testcase 或者提供的 Testcase 过于负责，那么你可以先提供简单的 Testcase：
        
        > "Given this testcase, [1, 5, 3, 9] and target = 10, the return ans should be [0, 3] because 1 + 9 equal to 10, am I understand the question correctly?"
    - "Let me write down some note so make sure understand the question"

与面试官书面确认你正确理解题目，并且针对限制条件和边界情况进行提问

在 IDE 或者文档中使用以下模版进行正式记录

Question：尝试用一句话总结题目，可以拷贝粘贴关键点里面的问题，不需要纠结英语语法正确性
Input and Output：在代码中的命名以及具体数据类型
Constraints:
  1. 根据输入可以提出的问题：
    - 输入是数组：数组长度是多少，数组包括的元素是什么，范围是多少
    - 输入是数字：数字范围是多少
    - 输入是二叉树：二叉树节点数量范围是多少，二叉树节点值范围是多少
  2. 结合题意可以提出的问题：
    - 针对本题可以提出：结果是唯一的吗？保证会有合法的结果吗？没有的话返回什么？
  3. 一般性问题：
    - "Do you have any time or space complexity requirement for my solution"
  4. 问得太多面试官不一定会都回答，所以对于一些常规的情况可以进行假设，例如：
    - "Based on this problem, I assume this array only contain interger."
    - "Based on this problem, I assume that there always would have a valid answer, and we only need to return any of them."
    如果你的假设错误，面试官会纠正你。
Testcases: 包括一个一般性测试用例以及一个边界情况测试用例

参考示例：

Question:
given an array of int, find two element sum to target and return index
Input:
  - array: int[]
  - target: int
Output:
   - res: int
Constraints:
   - 1 < array.length < 10,000
   - 1 < array[i] < 10000
   - always valid and return any answer
 Test Case:
    array = [2,7,11,15], T = 9 return [0, 1] # 本题中因为一定有合法解，所以不存在边界情况

分析题目

题目方向猜想：
- 情况 1：马上能够想到多个想法，那么讨论几个想法以及其优缺点，并且分析时空复杂度
- 情况 2：只能想到暴力解，先提出暴力解的思路，并且分析时间复杂度，然后使用 Testcase 来进行分析，尝试优化暴力解
  - 例如这道题，可以先提出可以使用两层循环进行解题，时间复杂度是 O(n^2)，空间是 O(1)，然后：
  - 使用 testcase [1, 5, 3, 9], target = 10，通过提出自己的观察，分析暴力解哪里可以进行优化，例如这题可以观察到我们不需要使用两层循环来进行两两配对，可以使用一个数据结构来记录需要寻找的值（Hashmap）
- 情况 3：完全没有头绪（通常来说应该可以想到暴力解），只能侧面要 Hint：
  - 根据输入类型以及题意进行猜想和探索，想出三个可能的 Tag
  - 例如这道题，根据输入类型可以猜测，双指针（次优解），栈，哈希表，然后可以问面试官这几个 Tag 是否有可能："I have several idea in my mind, like Two pointer, Stack or Hashmap, Which you do you think would be better?"
  - 根据面试官的回答来选择方向，Ta 可能会告诉你哪个 Tag 是 Ta 想要的方向，也可能拒绝告诉你。
题目思路讲解：
- 如果你知道如何解这道题，可以快速口述你的思路，最好是分拆成几步，然后问：“Do you think this is the solution you expected?"
- 写代码前的 Checkpoint: "Do you think I should start coding based on this solution?"
- 例如：
- 1. First step, create an empty hashmap
- 1. Loop over the array, for every element ele chece if [target - ele] in the hashmap or not, if in the hashmap, return the hashmap[target - ele], else, put ele in hashmap
- 如果面试官回答是的话，那么进入实现代码步骤
- 面试官回答不是的话，那么需要讨论其他解法（可能是最优解也可能是其他解法）
- 如果面试官不理解你的思路，那么你需要使用 Testcase 来讲述：
  - Given testcase [1, 5, 3, 9], target = 10
  - 1. create an empty hashmap HMap
  - 1. Loop over the array, the curren element is 1, 10 - 1 is not in the HMap, so we put 1 in HMap. and set its value to index 0
  - 1. Keep loop over the array, the curren element is 5, 10 - 5 is not in the HMap, so we put 5 in HMap, and set its value to index 1.
  - 1. Keep loop over the array, the curren element is 3, 10 - 3 is not in the HMap, so we put 3 in HMap, and set its value to index 2.
  - 1. Keep loop over the array, the curren element is 9, 10 - 9 is in the HMap, return HMap[1] and current index, so the result is [0, 3].

实现解法

想象代码
- 在写代码之前，可以尝试回答有多少行代码，这会要求你能够先想象出代码的细节，减少犯错以及修改
实现代码
- 实现的时候过于沉默或者过于话唠都不合适，可以在关键点（一般是写注释的地方）讲出你要实现的内容即可，注意这里要讲的是要实现的功能，而不是翻译代码。在简单的例子这两者可能区别不大，例如：
```
  def twoSum(self, nums, target):
      # Create a hashmap to store current element
      HMap = dict()
      # Loop over the array
      for i, num in enumerate(nums):
          # Check if target - current element in the HMap
          if target - num in HMap:
              return [HMap[target - num], i]
          HMap[nums[i]] = i
      return []
```
- 但是在复杂的例子中，需要讲的是要做的步骤是什么，而不是将代码翻译成英文，前者更加 High level，例如对于二分查找的 lower_bound 来说，前者会讲要实现的功能：找到第一个小于等于 element 的值，后者则是代码细节，设定 left 和 right 边界，每次都从两者的中间进行判断 ...

检查

快速检查
- 检查前的 Checkpoint: "Let me use a testcase to test my code"
- 先快速检查语法问题，如果使用的面试平台可以直接执行代码的话，一般来说面试官会要求执行代码。
- 如果执行代码的时候发现出现了意料之外的错误，或者执行多次依然无法通过的话，那么建议进行 Dry run 检查

Dry run 检查

使用一个 Testcase（这个 Testcase 最好是简单但又能够涵盖不同情况的），首要是简单的
一行行地 Run 代码

Given testcase [1, 5, 3, 9], target = 10

  def twoSum(self, nums, target):
      HMap = dict()
      # i = 0
      for i, num in enumerate(nums):
          # 10 - 1 not in HMap
          if target - num in HMap:
              return [HMap[target - num], i]
          # HMap[1] = 0
          HMap[nums[i]] = i
      return []

在遍历的过程中不断更新行间注释

其他错误
- 如果发现你的思路错了，或者忽略了一些 Testcase，尝试在代码中进行修改。

面试流程模版（测试）

理解题目​

目标​

通过关键点，Testcase 来确保理解题目​

与面试官书面确认你正确理解题目，并且针对限制条件和边界情况进行提问​

分析题目​

实现解法​

检查​

理解题目

目标

通过关键点，Testcase 来确保理解题目

与面试官书面确认你正确理解题目，并且针对限制条件和边界情况进行提问

分析题目

实现解法

检查