编程算法20+ 算法面试题

披露：本篇文章包含附属链接；如果您通过本文提供的不同链接购买产品或服务，我可能会收到报酬。

大家好，如果您正在准备编程工作面试或寻找新工作，那么您就会知道这不是一个简单的过程。

你必须幸运地接到电话并进入第一轮面试，不仅在你刚开始工作时，而且在你职业生涯的任何阶段。

但是，是的，当你寻找第一份工作时，初级阶段是最困难的。

这就是为什么你不能轻视机会。你必须做好准备抓住机会，为此，你必须了解面试对你的要求。面试官会问什么问题，你应该准备哪些话题等等。

我已经写了很多关于你可以在这个博客中找到有用文章的博客，但总结一下，除了数据结构问题、系统设计问题和编程语言特定问题（如Java、C++或Scala）之外，大多数编程工作面试还会问基于算法的问题。

这些基于常见的搜索和排序算法，如字符串算法、二进制搜索、图形算法等。

练习这些基于算法的问题非常重要，因为尽管它们看起来很明显和简单，但有时在实际面试中它们会变得很难解决，特别是如果你从未自己编写过代码。

面试前练习这些问题不仅能让你熟悉它们，还能让你更有信心向面试官解释解决方案，这对你的选拔起着非常重要的作用。

它还可以让您为任何扭曲的问题和替代问题做好准备，例如面试官经常喜欢要求您使用递归或迭代来解决特定的编码问题。

有时，如果你使用像我之前在 String 中查找重复字符时用到的数据结构，他们会要求你不使用 Set 数据结构来解决这个问题。这只是一个常见的例子，所以实践非常重要。

顺便说一句，如果你是数据结构和算法领域的初学者，那么我建议你先学习一门综合算法课程，例如Udemy 上的《数据结构和算法：使用 Java 进行深度探索》，它不仅会教你基本的数据结构和算法，还会教你如何在现实世界中使用它们以及如何使用它们解决编码问题。

另一方面，如果您喜欢读书或更喜欢读书而不是在线课程，那么您必须阅读一本综合性的书籍，例如Thomas H. Cormen 的《算法导论》 ，以了解常见的计算机科学算法，例如搜索、排序、密码学、图形算法和一些常见的算法，例如傅里叶变换。

程序员必问的 20 个基本算法面试题

好了，以下是一些面试中常见的搜索和排序算法问题。我附上了答案的链接，但你应该先尝试解决该问题，然后再看答案。

本文的目的是让您知道如何自己解决这些问题，但是，是的，如果您遇到困难并想比较您的解决方案，您可以查看解决方案。

1. 你能实现二分查找算法吗？（答案）
很简单，二分查找是一种分而治之的算法，将问题分解成子问题，然后逐一解决。它是一种搜索算法，这意味着它可以用来查找整数数组中的数字或目录中的条目。

实现二分搜索算法最简单的方法是使用递归，这也是解决方案链接所包含的内容，但在看到解决方案之前，您应该自己尝试一下。

值得注意的是，输入必须是排序的，我的意思是你只能在排序数组中实现二进制搜索。

2. 编写一个程序来实现线性搜索算法？（解决方案）
它甚至比二进制搜索更容易，您需要做的就是使用for 循环或递归方法遍历数组中的所有元素，并将每个元素与您要搜索的元素进行比较。当元素匹配时，您可以返回索引或true/false根据您的要求返回。

例如，如果你正在编写一个contains() 方法，你可以返回true或false来指示某个元素是否存在于数组中。由于你需要扫描整个数组来查找元素，因此该算法的时间复杂度为O(n)。

顺便说一句，如果您在计算和理解算法的时间和空间复杂度方面遇到困难，那么您应该在参加面试之前先看看像“数据结构和算法---面试”这样的课程，以便更好地理解它们。

3. 你能实现一个不使用递归的二分查找算法吗？（答案）
你可能知道，可以使用循环，有时也可以使用堆栈数据结构，将递归算法替换为迭代算法。对于二分查找，你也可以这样做，只需划分数组并比较中间元素，直到找到目标元素或数组中没有其他元素为止。

如果目标元素大于中间元素，则必须向右移动，否则向左移动。

顺便说一句，如果您难以理解递归算法或将递归算法转换为迭代算法，那么我建议您参加优秀的在线课程，例如Pluralsight 中的算法和数据结构---第 1 部分和第 2 部分，以更好地学习基础知识。

这些课程还将教您如何计算时间和空间复杂度，这对于编码面试的角度以及提高算法的性能都非常重要。

4. 实现冒泡排序算法？（解答）
这难道不是你学习的第一个排序算法吗？嗯，我确实学过，所以我记得冒泡排序就是将数组中的每个数字与其他数字进行比较，这样每次传递之后，最大或最小的元素都会冒泡到顶部。

我的意思是，这个数字找到了它的位置，并按顺序排列了。这是基本的排序算法之一，我们大多数人都是通过这个算法开始学习排序的。

它的时间复杂度O(n ^2)使得它不适用于大量数字，但适用于少量数字。

5. 编写代码实现二叉树的层级排序搜索？（解决方案）
在层级排序搜索中，你首先访问兄弟节点，然后再向下一层。你可以使用队列来实现二叉树的层级排序搜索。如果你想了解更多信息，可以查看freeCodeCamp 上的任何免费数据结构和算法课程。

如果你真的想做好，你也可以查看这份课程清单来破解你的编程工作面试

6. 稳定排序算法和不稳定排序算法有什么区别？（答案）
这是一个比较棘手的概念，我很久以前才知道。我还没有遇到过这个概念的实际用例，但从面试的角度来看，了解这个概念就足够了。

在稳定的排序算法中，即使排序之后，相同元素的顺序仍然保持不变，但在不稳定的排序算法中，这一顺序会发生变化。

一个很好的例子是快速排序和归并排序，前者是不稳定的算法，而后者是一种稳定的算法。

7. 二叉树的深度优先搜索算法是什么？（解答）
这是另一种流行的搜索算法，主要用于树和图。该算法首先深入访问节点，然后再进行同层搜索，这就是深度优先搜索算法的名称来源。

虽然实现起来比较棘手，但你可以使用 Stack 来实现 DFS 或深度优先搜索算法。如果你需要更多关于这个主题的信息，我建议你阅读Aditya Bhargava 的《Grokking Algorithms》一书，他的解释可能是对这个主题最好的解释。

8. 迭代快速排序算法是如何实现的？（解答）
显然不需要递归 :-)。如果你还记得的话，我之前告诉过你，可以使用 Stack 将递归算法转换为迭代算法，同样也可以用这种方法实现非递归的快速排序算法。如果你需要更多实现方面的帮助，可以进一步查看解决方案。

9. 如何实现计数排序算法？（解决方案）
就像我们对其他 O（n）排序算法（如基数排序和桶排序）所做的那样。

如果您不知道计数排序是另一种整数排序算法，用于根据小整数的键对对象集合进行排序。

它的O(n)时间复杂度使其在特定输入集下比快速排序和归并排序等算法更快。更多详情请参阅解决方案。

10. 如何在不使用第三个变量的情况下交换两个数字？（解答）
这又是一个棘手的问题，如果你知道诀窍，这个问题就很容易了 :-) 嗯，你可以交换两个数字，而无需使用临时变量或第三个变量，如果你可以将数字之和存储在一个数字中，然后用另一个数字减去这个数字，例如

a = 3;\
b = 5;

a = a + b; //8\
b = a --- b; // 3\
a = a --- b; //5

现在有 a = 5 和 b = 3，因此无需使用第三个或临时变量即可交换数字。

11. 基数排序算法是如何实现的？(解答)
这是另一个时间复杂度为 O(n) 的整数排序算法。根据维基百科，基数排序是一种非比较排序算法，它通过按具有相同有效位置和值的各个数字对整数键进行分组，对具有整数键的数据进行排序。

您还可以在 Coursera 上阅读 Robert Sedgewick 的《算法第一部分》和《算法第二部分》O(n) ，了解更多关于线性排序算法的信息。该课程免费提供学习和探索，但如果您还想获得认证，则需要付费。

顺便说一句，如果您计划参加多个 Coursera 课程或专业课程，那么请考虑订阅Coursera Plus，它可以让您无限制地访问其最受欢迎的课程、专业课程、专业证书和指导项目。

12. 如何实现插入排序算法？(解答)
你曾经整理过一副牌，或者整理过衣柜里的衬衫吗？这两样东西之间有什么共同点？嗯，你把下一张牌或衬衫放到它们正确的位置，或者，应该说，把下一个元素插入到它正确的位置。这就是插入排序。

13. 编写算法来检查两个矩形是否重叠？（解答）
这是一道棘手的算法题，但如果你在二维数学课上听老师讲课，就能解决这个问题。还有一个技巧，检查矩形不重叠的所有条件，如果任何条件不成立，则意味着两个矩形相互重叠。例如，如果一个矩形的上边低于另一个矩形的下边，那么由于它们是垂直对齐的，所以它们不会重叠。

14. 合并排序算法是如何实现的？（解答）
与快速排序类似，合并排序也是一种分而治之算法，这意味着你不断地分割问题，直到可以对其中最小的一个进行排序。

例如，要对一个数字数组进行排序，你需要将数组分成更小的部分，直到知道如何对它们进行排序，就像一个只有一个或零个元素的数组已经排序一样。对小数组进行排序后，将它们合并即可得到最终结果。

快速排序和归并排序的唯一区别在于，归并排序是稳定的，而快速排序是不稳定的。这意味着相等的元素在排序前后都保留其位置。

另一个值得注意的区别是，尽管两者都有O(NLogN)平均时间，但使用快速排序比合并排序更好，因为对于相同数量的输入，快速排序花费的时间更少，快速排序中的常数因子比合并排序中的常数因子更少。

15. 如何实现桶排序算法？（解决方案）
桶排序是另一种很棒的算法，它甚至无需比较元素即可对数组进行排序。

它被称为非比较排序算法，可以为所选输入提供 O(n) 性能。

如果您不了解非基于比较的排序算法，请参阅《算法简介》一书。

16. 编写算法检查两个字符串是否为字谜（解决方案）
字谜是指长度和字符匹配但顺序不匹配，例如Army和Mary，两者都具有相同数量的字符。

解决这个问题的一个技巧是对字符数组进行排序并检查它们是否相同。

17. 用你最喜欢的编程语言实现快速排序算法？（答案）
这是一个非常简单的排序算法，但前提是你练习过，否则你可能会迷失方向。记住，快速排序是一种分而治之的算法，这意味着你不断地对数组进行划分，也称为分区。然后，你在最小的层次上解决问题，也称为基准情况，例如当你的数组只包含一个或零个元素时。

19、比较排序算法和非比较排序算法的区别？（答案）
顾名思义，在基于比较的排序算法中，你必须比较元素才能进行排序，比如快速排序；但在基于非比较的排序算法中，比如计数排序，你可以不比较元素就进行排序。惊讶吗？

是的，那么我建议你看看这门课程，了解更多关于排序算法的知识，比如基数排序、计数排序和桶排序。如果你想了解更多关于这些排序算法的知识，O(n)可以进一步阅读《数据结构和算法：深入探究》 。O(n)

19. 如何检查两个字符串是否互相旋转？（答案）
有一个简单的技巧可以解决这个问题，只需将字符串与其自身连接起来，然后检查是否存在旋转。您可以使用indexOf或substring方法来实现。如果连接后的字符串包含旋转，则给定的字符串是前者的旋转。* \
*

20. 实现素数的埃拉托斯特尼筛选算法？（解决方案）
这是一个很难实现的算法，特别是如果你不记得它的话:-) 有时面试官会给你解释，但有时你需要记住它。

我希望这20个问题足以帮助你准备编程面试的算法题。如果你需要更多类似的编程问题，可以参考Gayle Laakmann McDowell撰写的《Cracking The Code Interview》等书籍，其中包含189多个编程问题及答案。这是一本在短时间内准备编程工作面试的好书。

顺便说一句，你在练习中解决的问题越多，你的准备就越充分。所以，如果你觉得这份问题清单不够，你需要更多，那么可以看看这些额外的50道电话面试编程问题，以及这些书籍和课程，以获得更全面的准备。

现在你已经准备好参加编码面试了

这些是数据结构和算法之外的一些最常见的问题，可以帮助您在面试中取得好成绩。

我也在我的博客上分享了很多这些问题，所以如果你真的感兴趣，你可以随时去那里搜索它们。

这些常见的编码、数据结构和算法问题是您在任何公司（无论大小）成功面试任何级别的编程工作时需要了解的问题。

如果您正在寻找编程或软件开发工作，您可以从这份编码问题列表开始准备。

此列表提供了很好的准备主题，也有助于评估您的准备情况，找出您的优势和劣势领域。

良好的数据结构和算法知识对于编码面试的成功至关重要，这也是您应该集中大部分注意力的地方。

面试准备资源

1. 破解密码访谈，作者：[Gayle Laakmann McDowell]
2. 数据结构和算法：使用 Java 进行深入探究
3. 从 0 到 1：Java 中的数据结构和算法
4. 数据结构与算法分析---求职面试

结束语

谢谢，你终于读完了这篇文章……祝你的编程面试好运！这当然不会很容易，但通过学习这些搜索和排序算法题，你就能比其他人更接近成功一步。

如果您喜欢这篇文章，请与您的朋友和同事分享，也不要忘记在 Twitter 上关注javarevisited ！

您可能喜欢的其他编程文章：

• 10 本准备技术编程/编码工作面试的书籍
• 每个程序员都应该读的10本算法书籍
• 面向 Java 开发人员的五本最佳数据结构和算法书籍
• 我最喜欢的深入学习算法的免费课程
• 面向 Java 开发人员的 10 门免费数据结构课程
• 破解编程工作面试的课程列表
• 10 门数据结构、算法和 SQL 课程助你轻松应对编程面试

PS --- 如果您需要一些免费资源，您可以查看此免费数据结构和算法课程列表来开始您的准备。