算法总结 | 技术面试手册 | tech-interview-handbook 中文文档

在编码面试中，大多数候选人最害怕的是：如果卡在某个问题上不知道如何解决怎么办？幸运的是，有结构化的方法可以用来处理编码面试问题，这将增加你解决问题的机会。从找到解决方案或方法，到优化时间和空间复杂度，以下是一些顶级技巧和最佳实践，可以帮助你解决编码面试问题。

如何找到编码面试问题的解决方案

当面临一个编码面试问题时，候选人应该首先询问澄清性问题，并与面试官讨论几种可能的解决方法。然而，这是大多数候选人往往会卡住的地方。值得庆幸的是，有一种结构化的方式来做到这一点。

请注意，并非所有技巧都适用于每一个编码面试问题，你也可以对一个问题使用多种技巧！在练习过程中应用这些技巧，你会培养出对哪种技巧适合当前问题的直觉。

1. 通过绘制问题来可视化问题

你是否曾经好奇为什么编码面试传统上是在白板上进行的，而视频解释答案时通常会使用图表？白板使得绘制图表变得容易，这对于解决问题非常有帮助！编码的很大一部分是理解程序内部状态的变化，图表是表示内部数据结构状态的非常有用的工具。如果你很难理解解决方案是如何获得的，可以尝试用图形表示问题，并在必要时，表示每个步骤的内部状态。

如果输入涉及树、图、矩阵、链表，这种技巧尤其有用。

示例

你如何以螺旋顺序返回矩阵中的所有元素？通过绘制矩阵和你迭代器需要沿每个方向采取的步骤，将极大地帮助你看到模式。

2. 考虑如何手动解决这个问题

手动解决这个问题就是不编写任何代码来解决这个问题，就像非程序员一样。这通常是在尝试理解给定的示例时自然而然发生的事情。

有些人没有意识到的是，有时一个可行的解决方案仅仅是手动方法的代码版本。如果你能围绕这种方法提出一套具体的规则，适用于每一个示例，你就可以写出代码。虽然这样做可能不会得到最有效的解决方案，但这是一个开始，会给你一些分数。

示例

你如何在不编写任何代码的情况下验证一棵树是否是一个有效的二叉搜索树？首先检查左子树是否只包含小于根的值，然后检查右子树是否只包含大于根的值，然后对每个节点重复此过程。这个过程似乎可行。现在你只需要把这个过程变成代码。

3. 提供更多示例

无论你是否遇到困难，提供更多示例都是有用的。这有助于加强你对问题的理解，防止你过早地跳入编码，帮助你识别出一个可以推广到任何输入的模式，这就是解决方案！最后，多个示例可以在最后作为测试用例来验证你的解决方案。

4. 将问题分解成更小的独立部分

如果问题很大，从高层次的函数开始，并将其分解成更小的构成函数，分别解决每一个。这可以防止你被一次性处理所有细节所压倒，并保持你的思维结构化。

这样做也让面试官清楚地知道你有了解决方案，即使你没有完成所有较小的函数的编码。

示例

组变位词问题可以分解为两个部分 - 哈希字符串，将字符串分组。每个部分都可以用独立的实现细节单独解决。你可以从以下代码开始：

def group_anagrams(strings):
  def hash(string):
    # 填写稍后
    pass

  def group_strings(strings_hashes):
    # 填写稍后
    pass

  strings_hashes = [(string, hash(string)) for string in strings]
  return group_strings(strings_hashes)

然后继续填写每个函数的实现。但是，请注意，有时最有效的解决方案将要求你打破一些抽象，并在一次输入迭代中执行多次操作。如果你的面试官要求你基于你良好的抽象解决方案进行优化，那是一条可行的前进道路。

5. 在问题上应用常见的数据结构和算法

与现实世界中的软件工程不同，那里的问题通常是开放式的，可能没有明确的解决方案，编码面试问题往往性质较小，设计得可以在面试期间解决。你还可能会期望解决这个问题所需的知识并不是超乎寻常的，而这些知识在大学里已经教授过了。幸运的是，常见的数据结构和算法的数量是有限的，根据我的经验，一个简单的尝试方法是遍历所有常见的数据结构并将其应用于问题。以下是在编码面试问题中需要记住并尝试的数据结构列表，按出现频率排序：

哈希表：对于高效的查找非常有用。这是面试中出现最频繁的数据结构之一，保证你会用到它。
图：如果数据以实体之间的关联呈现给你，你可能会将问题建模为图，并使用一些常见的图算法来解决。
栈和队列：如果你需要解析具有嵌套属性的字符串（例如数学表达式），你几乎肯定会用到栈。
堆：问题涉及基于某种优先级的调度/排序。也适用于在集合中找到最大K个最小K个/中位数元素。
树/前缀树：你是否需要以空间高效的方式存储字符串，并且非常快速地查找字符串的存在（或者至少是部分字符串）？

例程

排序
二分搜索：如果输入数组已排序，你需要比O(n)更快的搜索速度，则此方法有用。
滑动窗口
双指针
并查集
BFS/DFS
从后向前遍历
拓扑排序

未来我们会添加如何更好地根据问题确定最相关的数据结构和例程的技巧。

如何优化你的方法或解决方案

在你提出编码面试问题的初始解决方案之后，你的面试官很可能会提示你通过询问“我们能做得更好吗”来优化解决方案。以下技巧可以帮助你进一步优化解决方案的时间和空间复杂度：

如何优化时间复杂度

1. 确定解决方案的最佳理论时间复杂度

解决方案的最佳理论时间复杂度（BTTC）是你知道无法超越的时间复杂度。

一些简化示例：

查找数组中数字之和的最佳BTTC是O(n)，因为你必须至少查看数组中的每个值一次。
查找字谜组数的最佳BTTC是O(nk)，其中n是单词数量，k是单词中最大的字母数，因为你必须至少查看每个单词一次，并且至少查看每个单词中的每个字符一次。
查找矩阵中岛屿数量的最佳BTTC是O(nm)，其中n是行数，m是列数，因为你必须至少查看矩阵中的每个单元格一次。

为什么了解BTTC很重要？这样你就不会陷入寻找比BTTC更快解决方案的死胡同。最快的实际解决方案只能与BTTC一样快，不能比BTTC更快。BTTC在实践中不一定能够实现（因此是理论的），它只是意味着你永远找不到比它更快的真实解决方案。如果你的初始解决方案比BTTC慢，那么可能有机会改进，以便达到BTTC（但并不总是如此）。向面试官提及BTTC会作为一个积极的信号，并提醒自己你不应该试图提出比BTTC更快解决方案。

有些人可能会认为BTTC仅仅是数据结构中元素的总数，因为你需要遍历每个元素一次。这并不总是真的。最著名的例子是在已排序的数字数组中查找一个数字。已排序属性改变了很多事情：

查找数字将是O(log(n))，因为你可以使用二分搜索。
查找最大数字将是O(1)，因为它位于数组的最后一个位置。

这就是为什么关注问题细节非常重要。不要因为没有注意到问题细节而错误地确定BTTC！

确定了正确的BTTC后，你现在知道最优解决方案的时间复杂度介于初始解决方案和BTTC之间，并可以朝着这个方向努力。如果你的解决方案已经具有BTTC，并且面试官正在询问你进一步优化，通常有两件事他们正在寻找：

做更少的工作。你的解决方案可能是O(n)，但你可以通过对数组进行两次遍历来让面试官寻找使用单次遍历的解决方案。
使用更少的空间。请参阅下面的章节关于优化空间复杂度。

2. 识别重叠和重复计算

一个天真的/暴力解决方案经常一遍又一遍地执行相同的操作。当代码执行一个之前已经完成的昂贵操作时，花点时间退一步，考虑是否可以重用之前计算的成果。动态规划（DP）是最明显的完全利用过去计算的问题类型。有一些非DP问题也可以利用这种技术，尽管不那么直接，可能需要一个预处理步骤。

示例

《数组乘积除自身》问题是一个包含重叠/重复工作的良好示例。要获取一个索引的值，你需要乘以所有其他位置的值。对数组中的每个值都这样做将花费O(n²)时间。然而，请看：

result[n]：Product(nums[0] … nums[n-1]) * Product(nums[n + 1] … nums[N - 1])
result[n + 1]：Product(nums[0] … nums[n]) * Product(num[n + 2] … nums[N - 1])

在计算result[n]与result[n + 1]时有很多重复的工作！这是一个机会，在计算result[n]的同时重用早期计算结果来计算result[n + 1]。实际上，我们可以利用前缀数组帮助我们在O(n)时间内到达最终解决方案，但代价是需要更多的空间。

3. 尝试不同的数据结构

选择合适的数据结构对于编码面试至关重要。它可以帮你解决问题，也可以帮助你优化现有的解决方案。有时值得再次迭代你已经知道的数据结构。查找时间是否拖慢了您的算法？通常情况下，大多数查找操作在哈希表的帮助下应该是O(1)的。如果您的解决方案中的查找操作是您解决方案的时间复杂性的瓶颈，那么很多时候，您可以使用哈希表来优化查找。

示例

最近的K个原点对问题可以通过计算每个点的距离、排序它们，然后取K个最小值的方式以一种天真地方式解决。由于排序，这需要O(nlog(n))的时间。然而，通过使用堆数据结构，时间复杂度可以降低到O(nlog(k))，因为当堆的大小限制在K个元素时，从堆中添加/移除只需要O(log(k))的时间。改变数据结构对算法的效率产生了巨大的影响！

4. 确定冗余工作

这里是几个代码示例，这些代码正在进行冗余工作。尽管犯这些错误可能不会改变您代码的整体时间复杂度，但您还需要根据编码能力进行评估，因此编写尽可能高效的代码是很重要的。

不要不必要的检查条件

以下是一些Python示例中第二个检查是多余的。

if not arr and len(arr) == 0 - 第一个检查已经确保数组为空，所以没有必要进行第二个检查。
x < 5 and x < 10 - 第二个检查是第一个检查的一个子条件。

注意检查顺序

if slow() or fast() - 这里有一个检查包含两个操作，持续时间不同。只要其中一个操作评估为true，条件就会评估为true。大多数计算机按顺序执行操作，从左到右，因此将fast()放在左边更有效率。
if likely() and unlikely() - 这个例子使用了与上面类似的观点。如果我们首先执行unlikely()并且它是false，我们就不需要执行likely()。

不要不必要的调用方法

如果在函数中需要多次引用某个属性，并且该属性必须从函数调用中派生出来，如果该值在整个函数生命周期中不变，就将结果缓存为一个变量。输入数组的长度是最常见的例子。大多数时候，输入数组的长度不会改变，在开始时声明一个名为length = len(array)的变量，并在函数中使用length而不是每次需要时都调用len(array)。

早期终止

早期终止。一旦有了答案就停止，立即返回答案。这里有一个利用早期终止的例子。考虑这个基本问题“确定一个字符串数组中是否包含一个字符串，不管大小写”。它的代码：

def contains_string(search_term, strings):
  result = False
  for string in strings:
    if string.lower() == search_term.lower():
      result = True
  return result

这段代码有用吗？当然。这段代码已经尽可能高效了吗？不，我们只需要知道搜索词是否存在于字符串数组中。一旦我们知道存在这个值，就可以停止迭代。

def contains_string(search_term, strings):
  for string in strings:
    if string.lower() == search_term.lower():
      return True # 停止比较数组列表的其余部分，因为结果不会改变。
  return False

大多数人已经知道了这一点，并且在面试之外也这样做。然而，在紧张的面试环境中，人们往往会忘记最明显的事情。在可以的情况下尽早终止循环。

最小化循环内的工作

让我们进一步改进上面的例子来解决“确定一个字符串数组中是否包含一个字符串，不管大小写”的问题。

def contains_string(search_term, strings):
  for string in strings:
    if string.lower() == search_term.lower():
      return True
  return False

请注意，对于for循环的每次迭代，您都会调用search_term.lower()一次！这是浪费，因为search_term在整个函数生命周期中不会改变。

def contains_string(search_term, strings):
  search_term_lowercase = search_term.lower()
  for string in strings:
    if string.lower() == search_term_lowercase:
      return True
  return False

最小化循环内的工作，并且如果不需要重做已经完成的工作，则不要重复做。

懒惰

懒惰评估是一种评估策略，它延迟了对表达式的评估，直到需要其值为止。让我们使用上述相同的例子。我们可以稍微技术性地改进一下：

def contains_string(search_term, strings):
  if len(strings) == 0:
    return False
  # 如果根本没有字符串，就不需要将搜索词转换为小写。
  search_term_lowercase = search_term.lower()
  for string in strings:
    if string.lower() == search_term_lowercase:
      return True
  return False

这被认为是微优化，而且大多数时候strings不会为空，但我使用它来说明如果不需要进行某些计算，则不必这样做。这也适用于初始化代码中需要的对象（通常是哈希表）。如果输入为空，就没有必要初始化任何变量！

如何优化空间复杂度

大多数时候，时间复杂度比空间复杂度更重要。但是，当你已经达到了最优的时间复杂度时，面试官可能会要求你优化你的解决方案所使用的空间（如果它使用了额外的空间）。这里有一些你可以用来提高代码空间复杂度的技巧。

1. 改变数据原地/覆盖输入数据

如果你的解决方案包含创建新数据结构来进行中间处理/缓存的代码，内存空间就会被分配，有时会被视为负面的。一个绕过这个问题的技巧是在原始输入数组中覆盖值，这样你的代码中就不会分配任何新的空间。然而，请注意，如果你需要在代码的后续部分使用输入数据，不要以不可逆的方式破坏输入数据。一种可能的方法（但你在编程面试之外永远不要使用）是变异原始数组，并将其用作哈希表来存储中间数据。请参见下面的示例。

请注意，在软件工程中，通常不鼓励修改输入数据，这会使代码更难以阅读和维护，因此，在编程面试中，你通常应该只在必要时原地修改数据。

示例

通过创建一个新数组并以排序的方式填充相应值，可以轻松以O(n)时间和O(n)空间解决Dutch National Flag问题。作为额外的挑战和空间优化，面试官通常会要求一个O(n)时间和O(1)空间的解决方案，该方案涉及原地对输入数组进行排序。

将原始数组用作哈希表的例子是First Missing Positive问题。在第一个for循环之后，数组中的所有值都是正数，你可以通过对应于该数字的索引的值的否定来指示数字的存在。要指示存在数字4，就否定nums[4]。

2. 更改数据结构

数据结构再次出现？是的，数据结构再次出现！数据结构对于编程面试至关重要，掌握它的好坏直接影响到你的面试表现。你是否使用了可能的最佳数据结构来解决这个问题？

示例

你给出了一组字符串，并想找出这些字符串中有多少个以某个前缀开头。如何有效地存储字符串以便快速计算答案？Trie是一种树状数据结构，非常适合存储字符串，并且允许你快速计算有多少字符串以某个前缀开头。

下一步

如果你还没有，我建议你查看我的免费的结构化编码面试指南，其中包含逐步指导，例如：

如何为你的编码面试准备制定有效的计划 - 包括根据剩余时间确定主题和问题的优先级
编码面试最佳实践备忘单 - 包括如何在编码面试中表现出色以展示雇佣信号
算法备忘单 - 包括你应该内化的每个数据结构的必须记住的内容