【CSDN 编者按】面试是测查和评价人员能力素质的一种考试活动。最常问的编码算法面试问题你知道多少呢？

作者 | Rahul Sabnis

译者 | 苏本如，责编 | 刘静

出品 | CSDN（ID：CSDNnews）

在许多采访中，我经常被要求要么实现一个通用算法，要么作为一个更大的解决方案的一部分，实现一个特别的算法。你在数据结构和算法课程中学习到的典型算法在编码面试中非常常见。不了解这些算法可能会让你失去一份工作，所以我想在本文分享一些编码面试必须知道的算法。如果这篇文章对你有帮助，请订阅我的YouTube频道或在medium.com网站上关注我，以获取更多类似的内容！如果你想寻找一个很好的资源来学习这些算法，我建议你阅读这本名为Cracking the Coding Interview的书，它将涵盖所有这些内容，而且更加详尽！

免责声明：这篇文章是基于我在寻找实习生和入门级（新毕业生）开发人员角色的过程中获取的经验撰写的。在任何时候，如果我声明你需要知道一个算法，这意味着你应该能够理解这个算法上是如何工作的（包括时间/空间复杂性），并且你能够用一个例子来展示你对这个算法的理解，而且你能够用你选择的语言来实现它。好了，既然我们已经作了这些澄清，那就让我们进入正题吧！

树的遍历算法

这些算法允许你按一种结构化的顺序访问树中的每个节点。它们主要是为二叉树设计的，但是你可以调整这些概念来访问任何树中的所有节点。学习这些算法还将帮助你了解如何递归地遍历树中的所有节点。

你应该关注的三种算法分别是前序遍历（Pre-Order Traversal）、中序遍历（In-Order Traversal）和后序遍历（Post-Order Traversal）。每种算法的访问树节点的顺序各不相同。我建议大家要弄清楚这些算法中的访问一个二叉查找树中的值的顺序。

图搜索算法

这些算法工作在树上，有顶点和边的图上，以及图的任何编码上。它们采用不同的方法将你从起始节点带到目的节点。

这类算法包括深度优先搜索（DFS）、广度优先搜索（BFS）和狄克斯特拉（Dijkstra）算法。如果你还有多余的时间，我建议你也去学习一下A*算法。

查找算法

这是一类算法，实际上只有一个重要的算法：二分查找法。传统的查找是一种时间复杂度为0(n)的算法，因为一个时间你查看每个元素一次。假设你有一个有序的输入列表，那么利用二分查找法的时间复杂度会是O(log(n))。我经常被要求实现一个二分查找法，作为我面试问题解决方案的一部分，所以我强烈建议你去搞清楚这个算法。

排序算法

排序算法包括冒泡排序、插入排序、选择排序等等。所有这些都是标准算法，你应该理解并能够实现，但对于平均情况，这些算法的时间复杂度都是O(n²)。面试中最重要的排序算法是这些时间复杂度为O(n*log(n))的排序算法。这一类算法中最常用的两个算法是归并排序（merge sort）和快速排序（quick sort）。你至少应该知道其中一个，这一点很重要，当然最好两种算法你都了解。我建议从归并排序开始，因为它在最坏情况下的时间复杂度为O(n*log(n))而快速排序在最坏情况下的时间复杂度会掉到O(n²)。

英文：4 Most Commonly Asked Algorithms In Coding Interviews

原文链接：

【END】