一种能帮助你应对编程面试的算法 - malisper.me

banq

在过去的几年里，我面试了十几家公司，完成了大约 50 道个人算法问题。我经常收到反馈说我在算法问题上做得很好。在这篇文章中，我将分享我如何解决算法问题。
 
思考过程
我使用的一个指导原则是，每个面试问题都是为了解决而设计的。你不会被要求在面试中证明费马大定理。如果给你一些不可能的问题，那么无论如何你都不会有太多的机会。
根据我的经验，大约 80% 的算法问题会归结为几个核心数据结构和算法。我看到最多的数据结构是：
  • 哈希表
  • 链表
  • 二叉搜索树
至于算法：
  • 深度优先搜索
  • 二分查找
  • 排序算法
（您可能不会期望实现二分搜索或排序算法，但您应该知道它们存在。）
您还应该了解另外两种编程技术：
  • 动态规划
  • 递归
假设您的问题的解决方案可以使用此列表中的项目解决，我们可以想出一个简单的算法来解决问题。
 
算法
算法是这样的：
  1. 在给出算法问题后，询问您的解决方案需要的特定运行时间。几乎可以肯定，面试官会告诉你。
  2. 过滤掉明显与手头问题无关的数据结构和算法。这将消除大部分列表，通常会留下 2-3 个数据结构和算法。
    2. 您可以过滤掉速度太慢的数据结构。如果你需要在 O(1) 时间内解决一个问题，那么在解决方案中不可能使用二叉树，因为二叉树总是至少需要 O(log n) 时间。 
    3. 如果算法无法用于给定的问题，您可以过滤掉它们。如果问题中没有图形，您就知道深度优先搜索不相关。
  3. 浏览其余数据结构的用例，看看哪些与手头的问题相关。该问题的解决方案将是这些用例的组合。您需要做的就是将这些不同的用例拼凑在一起，然后您就会提出问题的解决方案。
 
案例 
让我们来看看每个数据结构和算法的运行时和主要用例。然后通过几个示例，您可以了解使用该算法是多么容易。
数据结构：哈希表O(1)
运行：插入、查找和删除。
用例：
  • 当您只需要存储和查找对象时。
  • 当您需要按某些属性对不同组的对象列表进行分区时（基本上是 SQL 中的 group by 所做的）
  • 您需要计算列表中不同项目的数量。
  
数据结构：链表O(1)
运行： 在您已经有指针指向的节点的末尾或旁边插入、查找和删除。
用例：
链表的主要用例围绕着这样一个事实，即链表维护元素的相对顺序。在编程面试中，链表主要用作堆栈或队列。
 
数据结构：二叉树O(log n)
运行： 插入、查找和删除。
用例：当您需要按排序顺序保存数据时使用。这使您可以快速回答问题，例如有多少元素落入给定范围或树中第 N 个最高的元素是什么。
 
数据结构：二分查找
运行：O(log n)
用例：
  • 您需要在最接近另一个数字的排序数组中找到该数字。
  • 您需要在排序数组中找到比另一个数字大的最小数字。
  • 您需要在排序数组中找到小于另一个数字的最大数字。
  • 如果由于某种原因无法使用哈希表，则可以使用二分搜索来检查给定元素是否在排序数组中。
 
数据结构：深度优先搜索
运行：O(n)遍历整个图。
用例：
  • 在图中查找特定元素。
  • 找出图的连通分量。
 
数据结构：排序
运行：O(n log n)
用例：
  • 如果您需要按特定顺序处理元素，则可以使用。首先按该顺序排序，然后遍历元素。
  • 可用于对稍后将执行二分搜索的数组进行排序。
动态规划和递归有点不同，因为它们是解决算法问题的通用技术，而不是特定算法本身。这意味着它们没有具体的运行时或用例。好消息是经过一些练习，识别可以用动态编程或递归解决的程序变得相当容易。我的建议是练习一些需要动态编程或递归的问题，以便您对它们有所了解。全面解释动态编程和递归超出了本文的范围。
 
复杂案例
现在让我们来看看几个不同的面试问题，以及我们如何使用算法来解决这些问题。
  • 问题 1：构建速率限制器
这是我在几家不同公司多次看到的问题。
您需要编写一个在任何 1 分钟窗口内最多只能调用 N 次的函数。例如，它在一分钟内最多可以调用 10 次。如果函数被调用超过 N 次，它应该抛出异常。该函数应该具有预期的 O(1) 性能。
看看我们可以使用的数据结构和算法，看看哪些可以用来解决问题。然后尝试看看如何使用这些数据结构来解决问题。在转向解决方案之前先试一试。
  • 哈希表
  • 链表
  • 二叉树
  • 深度优先搜索
  • 二分查找
  • 排序
  • 动态规划
  • 递归
解决方案
让我们从消除所有显然不能使用的数据结构和算法开始：
  • 哈希表
  • 链表
  • 二叉树 - 太慢了。
  • 深度优先搜索- 太慢了。也没有运行 DFS 的图表。
  • 二分查找- 太慢了。也没有排序数组。
  • 排序- 太慢了。也没有要排序的元素。
  • 动态规划 – 无法将动态规划应用于问题。
  • 递归 – 无法对问题应用递归。
只剩下哈希表和链表。如果我们查看哈希表的常见用例，似乎没有任何方法可以将它们应用于问题。我们不需要快速查找不同的对象，也不需要将对象列表划分为不同的组。这意味着我们可以从列表中划掉哈希表。
剩下的唯一数据结构是链表。查看用例，只有两个用于堆栈和队列。我们可以使用其中任何一个来跟踪函数在最后一分钟被调用的次数吗？是的！我们可以做的是保留一个队列，该队列在最后一分钟内每次调用该函数时都有一个条目。每当调用该函数时，我们都会从队列中删除一分钟前插入的所有条目。如果队列的长度仍然大于 N，我们将抛出异常。否则，我们将使用当前时间向队列添加一个新条目。通过使用计数器跟踪队列的长度，我们可以确定 O(1) 的预期时间，该函数将具有 O(1) 的预期性能。
 
  • 问题#2：字谜
给定一个单词列表，在输入中生成一个单词列表，这些单词是列表中至少一个其他单词的字谜。如果您可以重新排列一个中的字母以获得另一个，则两个单词是彼此的字谜。假设单词具有恒定长度，运行时间应该是 O(n)。
在阅读解决方案之前，再次尝试自己解决问题。以下是完整的数据结构和算法列表，供参考：
  • 哈希表
  • 链表
  • 二叉树
  • 深度优先搜索
  • 二分查找
  • 排序
  • 动态规划
  • 递归
解决方案
让我们首先从列表中删除不可能用于此问题的项目：
  • 哈希表
  • 链表
  • 二叉树 - 太慢了。
  • 深度优先搜索 – 没有图表。
  • 二分查找 – 没有排序数组。
  • 排序 - 太慢了。
  • 动态规划 – 无法将 DP 应用于问题。
  • 递归 – 无法对问题应用递归。
这让我们只剩下哈希表和链表。链表似乎与问题无关，因为堆栈或队列看起来没有任何帮助我们的方式。这样就只剩下哈希表了。
此处似乎相关的唯一哈希表用例是能够根据属性将列表中的元素拆分为单独的组。在这种情况下，如果有办法根据哪些单词是彼此的字谜将列表分成不同的组，那将给我们一个解决问题的方法：
[list=1]
  • 根据哪些单词是彼此的字谜，将单词列表分成不同的组。
  • 将包含多个单词的所有组附加在一起。这将生成一个单词列表，这些单词是输入列表中至少一个其他单词的字谜。 唯一需要解决的问题是找到一些我们可以用来将字谜组合在一起的属性。我们需要找到某个函数 f 使得当 x 和 y 互为变位词时 f(x) 与 f(y) 相同。我们可以使用两个不同的函数来做到这一点：
    • 按字母顺序对单词的字符进行排序。因为字谜都是由相同的字母组成的。对于作为每个字谜的任何一对单词，这将为我们提供相同的字符串。
    • 制作每个单词中每个字母出现的次数的字典。这个解决方案有点棘手，因为您需要以某种方式使用字典作为哈希表中的键。有些语言有办法做到这一点，而另一些则没有。
    现在我们知道如何将互为字谜的单词组合在一起，我们可以将所有内容放在一起以生成解决方案！
     
    • 问题 #3：K 排序
    给定一个部分排序的对象数组，对数组进行排序。阵列中的每个元素与其实际位置的距离至多为 k。您没有获得此问题的目标运行时。
    像往常一样，这里是算法和数据结构的列表： 
    • 哈希表
    • 链表
    • 二叉树
    • 深度优先搜索
    • 二分查找
    • 排序
    • 动态规划
    • 递归
    解决方案
    让我们首先看看我们是否可以推断出有关运行时的任何信息。我们可能实现的最快运行时间是 O(n)，因为这是遍历列表所需的时间。我们也可以始终对列表执行正常排序，这为我们提供 O(n log n) 的运行时间。让我们看看是否有可能比 O(n log n) 做得更好。是否有可能像 O(n) 一样快？好吧，如果 k=n，这个问题就变成了对列表进行排序的问题，所以不可能一直达到 O(n)。也许仍然有可能实现比 O(n log n) 更好的东西。现在让我们看看哪些数据结构和算法是相关的：
    • 哈希表
    • 链表
    • 二叉树
    • 深度优先搜索 – 没有图表。
    • 二分查找 – 没有排序的数组。
    • 排序 - 太慢了。
    • 动态规划 - 不相关。
    • 递归 - 不相关。
    在剩下的数据结构中，唯一与问题相关的数据结构是二叉树。二叉树是列表中唯一处理元素排序的数据结构。如果您稍微思考一下如何使用二叉树来解决问题，答案就很清楚了。我们可以保留最后 k 个元素的二叉树。我们反复从二叉树中删除最小的元素，并从输入数组中添加下一个元素。完整的算法如下所示：
    • 将输入数组的前 k 个元素插入二叉树。
    • 遍历输入数组的其余部分。在每次迭代中，从二叉树中删除最小的元素并将其添加到结果数组中。然后将输入列表中的当前元素添加到二叉树中。
    • 一旦我们到达输入数组的末尾，重复从二叉树中删除最小的元素，直到树为空。
    分析这个解决方案的运行时间，这给了我们 O(n log k) 的运行时间。有没有可能做得比这更好？没有更快的算法似乎很直观。什么可能的算法有 O(n) 和 O(n log k) 之间的运行时间，尤其是你在面试中不得不提出的算法？这是一个非正式的证明，你不能比 O(n log k) 更快地解决问题。鉴于提出这一点并非易事，因此您不会在面试中提出来。如果你对证明不感兴趣，你可以跳过它。
    假设您有一个比 O(n log k) 更快的算法。我们可以使用该算法提出比 O(n log n) 更快的排序算法，这是不可能的。假设我们有 n/k 个单独的列表，每个列表的大小为 k，每个列表的元素严格大于前一个列表的元素。如果将所有列表连接在一起，对它们运行 k-sorted，然后将每 k 个元素拆分为单独的列表，则您将在不到 O(n log k) 的时间内对 n/k 个列表进行排序。这意味着平均而言，您在不到 O(n/(n/k) log k) = O(k log k) 的时间内对每个列表进行了排序，这是不可能的。因此，没有任何 k 排序算法比 O(n log k) 快。

    这意味着我们已经找到了问题的最佳解决方案。
    希望此时我已经让您相信该算法是解决算法问题的有效方法。请注意，它不仅对解决面试中的问题有效，而且如果您在现实世界中遇到算法问题，您可以使用它来检查问题是否有由我们列表中的基本数据结构组成的解决方案。
    如果你想学习其他解决问题的方法，我强烈推荐《如何解决它》这本书。这本书涵盖了大量不同的方法，您可以使用它们来解决任何问题。如何解决它对我今天处理任何类型的问题的方式产生了巨大的影响。