后端开发教程 - Java、Spring Boot 实战 - msg200.com
50+ 数据结构和算法面试题
披露：本篇文章包含附属链接；如果您通过本文提供的不同链接购买产品或服务，我可能会收到报酬。
有很多计算机科学专业的毕业生和程序员在 Uber 和 Netflix 等初创公司、亚马逊、微软和谷歌等大型组织以及 Infosys 或 Luxsoft 等服务型公司申请编程、编码和软件开发职位，但他们中的许多人并不知道在向这些公司申请工作时会遇到什么样的编程面试问题。
在本文中，我将分享一些来自不同工作面试的常见编程面试问题，针对不同经验水平的程序员，从刚从大学毕业的程序员到具有一到两年经验的程序员。
编码面试主要包括数据结构和基于算法的问题以及一些逻辑问题，例如，如何在不使用临时变量的情况下交换两个整数？
我认为将编码面试问题划分为不同的主题领域会很有帮助。
我在面试中最常看到的主题领域是数组、链表、字符串、二叉树，以及来自算法（如字符串算法）、排序算法（如快速排序或基数排序）和其他杂项的问题），而这些就是您将在本文中找到的内容。
虽然不能保证你会被问到这些编码或数据结构和算法问题，但它们会让你对在真正的编程工作面试中可能会遇到的问题类型有足够的了解。
一旦您回答完这些问题，您就会有足够的信心参加任何电话或面对面的面试。
顺便说一句，如果您对基本数据结构和算法没有足够的了解，或者您很久没有接触过它们，那么尝试这些问题是没有意义的。
在这种情况下，您应该参加一门好的入门课程，例如《数据结构和算法：使用 Java 深入研究》来刷新您的 DS 和算法技能。
50 个最热门算法和编码面试问题
不用多说，以下是我在编程工作面试中列出的一些最常见的编码面试问题：
1. 数组编码面试题
数组是最基本的数据结构，它将元素存储在连续的内存位置。它也是面试官们最热衷的话题之一，在任何编程面试中你都会听到很多关于数组的问题，比如反转数组、排序数组或在数组中搜索元素。
数组数据结构的主要优点是，如果知道索引，它可以提供快速的 O（1）搜索，但是从数组中添加和删除元素的速度很慢，因为一旦创建数组就无法更改其大小。
为了创建一个更短或更长的数组，您需要创建一个新数组并将所有元素从旧数组复制到新数组。
解决基于数组的问题的关键是掌握数组数据结构以及循环、递归和基本运算符等基本编程构造函数。
以下是解决基于数组的编码问题的一些技巧：
- 数组索引从零开始
- 您可以使用循环来迭代数组
- 数组元素存储在连续的内存位置，因此您也可以使用指针算法访问它们
- 数组使用索引进行搜索时性能为 O(1)
- 由于调整大小，在数组中添加或删除元素的速度较慢
以下是一些常见的基于数组的编码面试问题，供您练习：
- 如何在给定的 1 到 100 的整数数组中找到缺失的数字？（解决方案）
- 如何在给定的整数数组中找到重复的数字？（解决方案）
- 如何在未排序的整数数组中找到最大和最小的数字？（解决方案）
- 如何找到所有整数数组中和等于给定数字的对？（解决方案）
- 如果数组包含多个重复项，如何查找重复的数字？（解决方案）
- Java 中如何从给定数组中删除重复项？（解决方案）
- 如何使用快速排序算法对整数数组进行排序？ （解决方案）
- 如何从数组中删除重复项？（解决方案）
- 如何在 Java 中就地反转数组？（解决方案）
- 如何在不使用任何库的情况下从数组中删除重复项？（解决方案）
这些问题不仅可以帮助您提高解决问题的能力，还可以提高您对数组数据结构的了解。
如果您需要基于数组的更多高级问题，那么您还可以参阅编码面试训练营：算法+数据结构，这是一门关于算法的训练营式课程，专为面试准备而设计，以便在谷歌、微软、苹果、Facebook 等技术巨头那里找到工作。
而且，如果您觉得 10 个问题不够并且您需要更多练习，那么您还可以查看这份30 个数组问题列表。
2. 链表编程面试题
链表是另一种常见的数据结构，它是数组数据结构的补充。与数组类似，链表也是一种线性数据结构，以线性方式存储元素。
但是，与数组不同的是，它并不将它们存储在连续的位置；相反，它们分散在内存中的各处，并通过节点相互连接。
链表只不过是一个节点列表，其中每个节点包含存储的值和下一个节点的地址。
由于这种结构，在链表中添加和删除元素很容易，因为您只需要更改链接而不是创建数组，但搜索很困难，通常需要 O(n) 时间才能在单链表中找到元素。
本文提供了有关数组和链表数据结构之间的差异的更多信息。
它还具有多种形式，例如单链表，允许您沿一个方向遍历（正向或反向）；双向链表，允许您沿两个方向遍历（正向和反向）；最后是循环链表，它形成一个圆圈。
为了解决基于链表的问题，熟悉递归非常重要，因为链表是一种递归数据结构。
如果从链表中取出一个节点，剩余的数据结构仍然是链表，因此，许多链表问题的递归解决方案比迭代解决方案更简单。
以下是一些最常见和流行的链表面试问题及其解决方案：
- 如何一次性找到单链表的中间元素？（解决方案）
- 如何检查给定的链表是否包含循环？如何找到循环的起始节点？（解决方案）
- 如何反转链接列表？（解决方案）
- 如何在不使用递归的情况下反转单链表？（解决方案）
- 如何在无序链表中删除重复节点？（解决方案）
- 如何找到单链表的长度？（解决方案）
- 如何在单链表中查找倒数第三个节点？（解决方案）
- 如何使用 Stack 找到两个链表的总和？ （解决方案）
这些问题将帮助您培养解决问题的能力并提高您对链表数据结构的了解。
如果您在解决这些链表编码问题时遇到困难，那么我建议您通过数据结构和算法：深入研究**使用 Java**课程来刷新您的数据结构和算法技能。
您还可以查看这份包含30 个链表面试问题的列表，以获取更多练习题。
3. 字符串编码面试题
除了数组和链表数据结构之外，字符串也是编程面试中另一个热门话题。我参加过的编程面试中，从未出现过不问字符串相关问题的。
字符串的一个好处是，如果您知道数组，您就可以轻松解决基于字符串的问题，因为字符串只不过是一个字符数组。
因此，通过解决基于数组的编码问题学到的所有技术也可以用于解决字符串编程问题。
以下是我在编程工作面试中经常问到的字符串编码问题列表：
- 如何打印字符串中的重复字符？（解决方案）
- 如何检查两个字符串是否互为字谜？（解决方案）
- 如何打印字符串中第一个不重复的字符？（解决方案）
- 如何使用递归来反转给定的字符串？（解决方案）
- 如何检查字符串是否仅包含数字？（解决方案）
- 如何在字符串中找到重复的字符？（解决方案）
- 如何计算给定字符串中的元音和辅音的数量？（解决方案）
- 如何计算字符串中给定字符的出现次数？（解决方案）
- 如何找到字符串的所有排列？（解决方案）
- 如何在不使用任何库方法的情况下反转给定句子中的单词？（解决方案）
- 如何检查两个字符串是否互相旋转？（解决方案）
- 如何检查给定的字符串是否是回文？（解决方案）
这些问题有助于提升你对字符串作为数据结构的理解。如果你能独立解答所有这些字符串问题，那么你的水平就很高了。
对于更高级的问题，我建议你解决Steven Skiena 的《算法设计手册》中给出的问题，这是一本包含最难算法问题的书。
如果您需要更多练习，这里还有另一份20 个字符串编码问题列表。
4. 二叉树编码面试题
到目前为止，我们只研究了线性数据结构，但现实世界中的所有信息都不能以线性方式表示，而这正是树数据结构的用处所在。
树形数据结构是一种允许以分层方式存储数据的数据结构。根据存储数据的方式，树有不同类型的类型，例如二叉树，其中每个节点最多有两个子节点。
与其近亲二叉搜索树一样，它也是最流行的树形数据结构之一。因此，你会发现很多基于它们的问题，例如如何遍历它们、计算节点数、确定深度以及检查它们是否平衡。
解决二叉树问题的关键在于对理论的扎实了解，例如二叉树的大小或深度是多少、什么是叶子、什么是节点，以及对流行遍历算法的理解，例如前序、后序和中序遍历。
以下是软件工程师或开发人员面试中常见的基于二叉树的编码问题列表：
- 二叉搜索树是如何实现的？（解决方案）
- 如何在给定的二叉树中执行前序遍历？（解决方案）
- 如何按前序遍历给定的二叉树而不进行递归？（解决方案）
- 如何在给定的二叉树中执行中序遍历？*（解决方案）
- 如何使用中序遍历（而非递归）打印给定二叉树的所有节点？（解决方案）
- 如何实现后序遍历算法？（解决方案）
- 如何以后序遍历的方式（不使用递归）遍历二叉树？（解决方案）
- 如何打印二叉搜索树的所有叶子？（解决方案）
- 如何计算给定二叉树中的叶节点数量？（解决方案）
- 如何在给定数组中执行二分查找？（解决方案）
如果您觉得自己对二叉树编码的理解不够充分，无法自行解决这些问题，我建议您回过头来选择一门好的数据结构和算法课程，例如《从 0 到 1：Java 中的数据结构和算法》。
如果您需要更多建议，这里是我列出的一些有用的数据结构算法书籍和课程。
5. 其他编码面试问题
除了基于数据结构的问题外，大多数编程工作面试还会询问算法、软件设计、位操作和一般基于逻辑的问题，我将在本节中描述这些问题。
练习这些概念非常重要，因为在实际面试中，它们有时很难解答。事先练习不仅能让你熟悉它们，还能让你更有信心向面试官解释解决方案。
- 冒泡排序算法是如何实现的？（解决方案）
- 迭代快速排序算法是如何实现的？（解决方案）
- 如何实现插入排序算法？（解决方案）
- 合并排序算法是如何实现的？（解决方案）
- 如何实现桶排序算法？（解决方案）
- 如何实现计数排序算法？（解决方案）
- 基数排序算法是如何实现的？（解决方案）
- 如何在不使用第三个变量的情况下交换两个数字？（解决方案）
- 如何检查两个矩形是否相互重叠？（解决方案）
- 如何设计自动售货机？（解决方案）
如果你需要更多类似的编程问题，可以参考Gayle Laakmann McDowell撰写的《破解代码面试》等书籍，该书提供了 189 多个编程问题及解答。这是一本在短时间内准备编程工作面试的好书。
顺便说一句，你在练习中解决的问题越多，你的准备就越充分。所以，如果你觉得50道题不够，需要更多，那么可以看看这些额外的50道电话面试编程题，以及这些书籍和课程，以获得更全面的准备。
现在你已经准备好参加编码面试了
这些是数据结构和算法之外的一些最常见的问题，可以帮助您在面试中取得好成绩。
我也在我的博客上分享了很多这些问题，所以如果你真的感兴趣，你可以随时去那里搜索它们。
这些常见的编码、数据结构和算法问题是您在任何公司（无论大小）成功面试任何级别的编程工作时需要了解的问题。
如果您正在寻找编程或软件开发工作，您可以通过这份编码问题列表开始准备。
此列表提供了很好的准备主题，也有助于评估您的准备情况，找出您的优势和劣势领域。
良好的数据结构和算法知识对于编码面试的成功至关重要，这也是您应该集中大部分注意力的地方。
进一步学习
数据结构和算法：深入研究 Java
掌握编码面试：Andrei Negaoie 的数据结构 + 算法
深入编码面试：编码问题模式
算法和数据结构 - 第 1 部分和第 2 部分
10 本准备技术编程/编码工作面试的书籍
每个程序员都应该阅读的 10 本算法书籍
Java 开发人员的 5 本最佳数据结构和算法书籍
从 0 到 1：Java 中的数据结构和算法
数据结构和算法分析--- 工作面试
结束语
谢谢，您终于读完了这篇文章……祝您的编程面试顺利！这当然不会轻松，但遵循这份路线图和指南，您离成为一名DevOps 工程师就更近了一步。
如果您喜欢这篇文章，请与您的朋友和同事分享，并且不要忘记在 Twitter 上关注javinpaul！