我们在面试程序员职位的时候，往往需要经历一段编程面试的流程，用人单位会以此来检验面试者的技术实力。然而，这些技术问题有时与我们的实际工作关系不大，这可能会给我们编程面试准备阶段带来很大的压力。曾在Facebook和微软工作过的Educative.io创始人FahimulHaq最近发表了一篇文章，总结了14种最常见的编程面试问题模式，或许可以帮助你看清各种编程面试问题背后的真相。”。对于许多开发人员来说，编程工作的面试准备可能是焦虑的来源。面试中要涵盖的内容太多，其中许多通常与开发人员的日常工作无关，只会增加压力.这种现状导致了一个后果：如今的开发人员经常要花数周时间在LeetCode等网站上学习综合数百个问题。做了更多？这就是为什么我想帮助开发人员了解每个问题背后的潜在模式-这样他们就不必担心解决数百个问题并被LeetCode累死。如果你了解面试的一般模式，你可以将其用作模板来解决各个级别略有不同的问题。在这里，我将列出最常见的14种模式，可用于解决任何编程面试问题。我还解释了如何识别每个pattern并为每个模式提供一些示例问题。这只是触及表面-我强烈建议您看一看课程《Grokking the Coding Interview: Patterns for Coding Questions》，它提供了详尽的解释、示例和编程实践。下面的模式描述假定您已经了解数据结构。如果你还不知道，你可以通过这些课程复习数据结构：https://www.educative.io/m/data-structures今天我们将解释以下14种模式：1.滑动窗口2。两个指针或迭代器3.快慢指针或迭代器4.组合区间5.循环排序6.原位反转链表7.树广度优先搜索（TreeBFS）8.树深度优先搜索（TreeDFS）9.两堆10．子集11。修正二分查找12.TopK元素13.K路合并14．拓扑排序让我们开始吧！1.SlidingWindow滑动窗口模式用于对给定数组或链表的特定窗口大小执行期望的操作，例如找到包含全1的最长子数组。从第一个元素开始滑动窗口，然后逐个元素滑动到右边，根据你要解决的问题调整窗口的长度。在某些情况下，窗口大小将保持不变，在其他情况下，窗口大小会增加或减少。以下是一些您可以用来确定给定问题可能需要滑动窗口的方法：问题的输入是线性数据结构，例如链表、数组或字符串您被要求找到最长/最短的子串，子数组或期望值您可以使用滑动窗口模式来处理常见问题：大小为K的子数组的最大总和（简单）具有K个不同字符的最长子串（中等）查找具有相同字符但顺序不同的字符字符串（困难）2。双指针或迭代器双指针（TwoPointers）是一种模式，其中两个指针以串联的方式遍历数据结构，直到一个或两个指针达到某个条件。在排序数组或链表中搜索对时，双指针通常很有用；例如，当您必须将数组的每个元素与其他所有元素进行比较时。两个指针很有用，因为只有一个指针，您必须不断循环返回数组以找到答案。这种来回使用单个迭代器在时间和空间复杂度上都是低效的——这个概念被称为“渐近分析”。这会让你得到一些类似于O(n2)的东西，尽管使用1个指针的蛮力搜索或简单的普通解决方案也可以。在许多情况下，两个指针可以帮助您找到具有更好空间或运行时复杂性的解决方案。确定何时使用双指针的方法：可用于处理排序数组（或链表）并需要找到一组满足某些约束的元素的问题数组中的元素集是成对的，三元组，甚至子数组以下是满足双指针模式的一些问题：对排序数组求平方（简单）找到总和为零的三元组（中等）用退格键比较字符串（中等）3.快指针和慢指针快指针和慢指针指针方法也称为Hare&Tortoise算法，它使用两个指针在数组（或序列/链表）中以不同的速度移动。在处理循环链表或数组时，此方法非常有用。通过以不同的速度移动（例如在循环链表中），该算法证明两个指针注定会相遇。只要两个指针在同一个循环中，快指针就会追上慢指针。您如何知道何时使用快速和慢速模式？处理链表或数组中循环的问题当您需要知道特定元素的位置或链表的总长度时，您什么时候应该更喜欢这种方法而不是上面提到的两指针方法？有些情况不适合使用两指针方法，比如在不能向后移动的单链表中。使用快速和慢速模式的一种情况是当您想要确定链表是否为回文时。以下是满足快速和慢速指针模式的一些问题：链表循环（简单）回文链表（中等）循环数组循环（困难）4.合并区间合并区间模式是处理重叠区间的有效技术。在许多涉及区间的问题中，您既需要找到重叠的区间，又需要在重叠时合并这些区间。该模式的工作原理如下：给定两个区间（a和b），这两个区间有6种不同的方式相互关联：理解和识别这六种情况可以帮助您解决范围广泛的问题，从插入区间到优化区间合并等那么如何判断何时使用合并区间模式呢？如果你被要求得到一个只有互斥区间的列表如果你听到术语“重叠区间”合并区间问题模式：IntervalIntersection(Medium)MaximumCPULoad(Hard)5.LoopSortThisMode描述了一个有趣的方法来涉及包含给定范围内的值的数组的问题。循环排序模式一次遍历数组一个值，如果正在迭代的当前值不在正确的索引处，则将其与正确索引处的值交换。可以尝试在其正确索引处替换值，但这会带来O(n^2)的复杂度，这不是最优的，因此使用循环排序模式。如何识别这种模式？涉及值在给定范围内的已排序数组的问题如果问题要求您在已排序/旋转数组中查找缺失值/重复项/最小值循环排序模式的问题：查找缺失值（简单）查找最小值缺失正值（中等）6。就地反转链表在许多问题中，您可能会被要求反转链表中一组节点之间的链接。通常，您需要就地执行此操作，即使用现有的节点对象而不占用额外的内存。这就是该模式的用武之地。该模式将一次反转一个节点，从指向链表头部的变量（当前）开始，然后变量（前一个）将指向已处理的前一个节点。反转当前节点是通过在同步移动到下一个节点之前将其指向前一个节点来实现的。此外，变量“previous”也将被更新，以便它始终指向已处理的前一个节点。如何识别何时使用此模式：如果要求您在不使用额外内存的情况下反转链表就地反转链表模式的问题：反转子列表（中等）反转每个子列表的K元素列表（中等）7.树广度优先搜索（TreeBFS）该模式基于广度优先搜索（BFS）技术，遍历一棵树并使用队列在跳转到下一层之前跟踪一层的所有节点。使用这种方法可以有效地解决任何涉及以逐级方式遍历树的问题。TreeBFS模式的工作方式是：将根节点压入队列，然后不断迭代，直到队列为空。在每次迭代中，我们删除队列头部的节点并“访问”该节点。从队列中移除每个节点后，我们还将其所有子节点插入队列中。HowtoidentifyTreeBFSpatterns:如果你被要求遍历（或按层次顺序）一棵树TreeBFS模式问题：二叉树层次顺序遍历（简单）Zigzag遍历（中等）8．树深度优先搜索（TreeDFS）树DFS是基于深度优先搜索（DFS）技术遍历树。您可以使用递归（或迭代方法的堆栈）在遍历期间跟踪所有先前的（父）节点。TreeDFS模式的工作方式是从树的根开始。如果节点不是叶子节点，需要做三件事：1.决定是处理当前节点（前序），还是处理两个子节点之间（中序），还是处理两个子节点之后(后序)2.对当前节点的两个子节点进行两次递归调用，对其进行处理3.如何识别TreeDFS模式：如果问你使用in-order,pre-orderorpost-orderDFS如果问题需要搜索节点更接近叶节点的东西，则遍历树问题的树DFS模式：路径数的总和（中）所有路径的总和（中）9。两个堆在许多问题中，我们希望将一组给定的元素分成两部分。为了解决这个问题，我们有兴趣知道一部分中的最小元素和另一部分中的最大元素。该模型是解决此类问题的有效方法。此模式使用两个堆：用于查找最小元素的最小堆和用于查找最大元素的最大堆。这种模式的工作方式是，前半部分的值存储在MaxHeap中，因为你要寻找前半部分的最大值。然后将另一半存储在MinHeap中，因为您正在寻找后半部分的最小值。任何时候，都可以从这两个堆的堆顶元素中计算出当前值列表的中间值。识别双堆模式的方法：在优先级队列、调度等场景中很有用。如果问题是你需要找到集合的最小/最大/中间元素，它有时可以用于解决二叉树数据结构的问题双堆模式：找到中间价值流（中等）10.子集许多编程面试问题涉及处理给定元素集的排列和组合。子集模式描述了一种用于有效处理所有这些问题的广度优先搜索(BFS)方法。该模式如下所示：给定一个集合[1,5,3]1。从空集开始：[[]]2。通过将第一个数字(1)添加到所有现有子集来创建新子集：[[]、[1]]3。将第二个数字(5)添加到所有现有子集：[[]、[1]、[5]、[1,5]]4。将第三个数字(3)添加到所有现有子集：[[]、[1]、[5]、[1,5]、[3]、[1,3]、[5,3]、[1,5,3]]下面是这种子集模式的可视化表示：如何识别子集模式：您需要找到给定问题集的组合或排列子集模式问题：具有重复项的子集（简单）字符串排列通过改变大小写（中等）11.改进的二分搜索给定一个排序数组、链表或矩阵，并要求查找特定元素，您可以使用的最佳算法是二分搜索。该模式描述了一种解决所有涉及二分查找问题的有效方法。对于上升集合，模式如下所示：1.首先，找到起点和终点之间的中点。一个简单的找中间的方法是：middle=(start+end)/2。但是这样很容易造成整数溢出，所以建议大家这样表达中间的位置：middle=start+(end—start)/2.2.如果键值（key）等于中间索引处的值，则返回这个中间位置。3.如果键值不等于中间索引处的值：4.检查key
