Skip to content

处理和解决编码面试问题的顶级技巧

原文：https://www.techinterviewhandbook.org/coding-interview-techniques/

大多数候选人在编码面试中最大的恐惧是:如果我在问题上卡住了，不知道怎么做怎么办？幸运的是，有结构化的方法来处理编码面试问题，这将增加你解决这些问题的机会。从如何找到解决方案或方法，到优化时间和空间复杂性，这里有一些顶级技巧和最佳实践，将帮助您解决编码面试问题。

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

当给出一个编码面试问题时，候选人应该从提出澄清性问题开始，并与他们的面试官讨论一些可能的方法。然而，这是大多数考生容易被卡住的地方。幸运的是，有一些方法可以以结构化的方式做到这一点。

请注意，并非所有的技术都适用于每个编码面试问题，您也可以在一个问题上使用多种技术！当你在实践中应用这些技术时，你会发展出直觉，知道哪种技术对手头的问题有用。

1.把问题画出来 形象化

有没有想过为什么编码面试传统上在白板上进行，而解释编码问题答案的视频往往使用图表？白板使绘制图表变得容易，这有助于解决问题！编码的很大一部分是理解程序的内部状态是如何变化的，而图是表示内部数据结构状态的非常有用的工具。如果你很难理解解决方案是如何获得的，想出问题的可视化表示，如果必要的话，每一步的内部状态。

如果输入涉及树、图、矩阵、链表，这种技术特别有用。

例

你如何以螺旋顺序返回一个矩阵的所有元素？画出矩阵和迭代器在每个方向上需要采取的步骤，将极大地帮助你看清模式。

2.想想你会如何用手 解决这个问题

手工解决问题就是不用写任何代码就能解决问题，就像非程序员会做的那样。当你试图理解给你的例子时，这已经很自然的发生了。

有些人没有意识到的是，有时一个有效的解决方案只是手工方法的代码版本。如果你能提出一套适用于每个例子的具体规则，你就能为它编写代码。虽然这样做可能不会得到最有效的解决方案，但这是一个给你加分的开始。

例

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

3.想出更多的例子

想出更多的例子是你可以做的有用的事情，不管你是否卡住了。它帮助你加强对问题的理解，防止你过早地进入编码，帮助你识别一个可以推广到任何输入的模式，这就是解决方案！最后，在最后验证您的解决方案时，可以使用多个示例作为测试用例。

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

如果问题很大，从一个高级函数开始，把它分解成更小的组成函数，分别解决每一个。这可以防止你被同时做每件事的细节弄得不知所措，并保持你的思维有条理。

这样做也让面试官清楚地知道你有一个方法，即使你没有完成所有小功能的编码。

例

分组字谜问题可以分解成两个部分——散列一个字符串，将字符串分组在一起。每个部分都可以用独立的实现细节单独解决。您可以从以下代码开始:

def  group_anagrams(strings):  def  hash(string):  # Fill in later  pass  def  group_strings(strings_hashes):  # Fill in later  pass  strings_hashes =  [(string,  hash(string))  for string in strings]  return group_strings(strings_hashes)

并继续填写每个功能的实现。但是，请注意，有时最有效的解决方案需要您打破一些抽象，在一次输入中执行多个操作。如果你的面试官要求你根据你精心抽象的解决方案进行优化，这是一条可能的前进道路。

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

与现实世界中的软件工程不同，在现实世界中，问题通常是开放式的，可能没有明确的解决方案，编码面试问题本质上往往较小，并且被设计为在面试期间是可解决的。你也可以期待解决问题所需的知识并不在这个世界上，他们会在大学期间被教授。幸运的是，通用数据结构和算法的数量是有限的，根据我的经验，一种可行的方法是尝试遍历所有的通用数据结构，并将它们应用到问题中。

以下是需要记住和尝试的数据结构，按照它们在编码面试问题中出现的频率排列:

  • 哈希映射:有助于提高查找效率。这是面试中最常用的数据结构，你肯定会用到它。
  • 图:如果数据以实体间关联的形式呈现给你，你或许可以将问题建模为图，并使用一些常见的图算法来解决问题。
  • 堆栈和队列:如果你需要解析一个具有嵌套属性的字符串(比如一个数学方程)，你几乎肯定需要使用堆栈。
  • 堆:问题涉及到基于某种优先级的调度/排序。也有助于找到一个集合中的最大 K/最小 K/中值元素。
  • Tree/Trie :你是否需要以一种空间高效的方式存储字符串，并且非常快速地寻找字符串(或者至少是部分字符串)的存在？

套路

  • 整理
  • 二分搜索法:如果输入数组是有序的，并且你需要比 O(n)搜索更快的速度，这很有用
  • 推拉窗
  • 两点
  • 联合查找
  • BFS/DFS
  • 从后面穿过
  • 拓扑排序

在将来，我们会添加一些技巧，告诉你如何根据问题更好地识别最相关的数据结构和例程。

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

在你想出编码面试问题的初步解决方案后，你的面试官很可能会问你“我们能做得更好吗”来提示你优化解决方案。以下技术可帮助您进一步优化解决方案的时间和空间复杂性:

如何优化时间复杂度

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

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

一些简化的例子:

为什么了解 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 2 时间。但是，请注意:

  • 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 -第二次检查是第一次检查的子条件。
注意检查的顺序
  • 此检查有两个操作，持续时间不同。只要其中一个操作评估为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  # Stop comparing the rest of the array/list because the result won't change.  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  # Don't have to change the search term to lower case if there are no strings at all.  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)空间很容易地解决，方法是创建一个新数组，并以排序的方式用相应的值填充它。作为一个额外的挑战和空间优化，面试官通常会要求 O(n)时间和 O(1)空间的解决方案，其中包括就地排序输入数组。

使用原始数组作为哈希表的一个例子是第一个缺失的正问题。在第一次 for 循环之后，数组中的所有值都是正的，您可以通过在对应于某个数字的索引处对该值求负来指示该数字的存在。为了指示 4 存在，求反nums[4]。

2.改变数据结构

又是数据结构！？是的，又是数据结构！数据结构是编写面试代码的基础，对它的掌握决定了你面试的成败。对于这个问题，你是否使用了最好的数据结构？

例

给你一个字符串列表，你想知道有多少个字符串以某个前缀开头。存储字符串的有效方法是什么，这样你就可以快速计算出你的答案？一个 Trie 是一个树状的数据结构，对于存储字符串非常有效，并且允许你快速计算有多少个字符串以前缀开头。

下一步

如果你还没有，我建议你看看我的免费结构化编码面试指南，它包含了一步一步的指导，例如:

我们一直在努力

apachecn/AiLearning

【布客】中文翻译组