为工程师准备的 50 道数据结构和算法面试题

[lietoumai]

1. 数组问题
数组是最常用的基础数据结构，它将元素保存在连续的内存中。它也是面试最喜欢的问题之一，在代码面试中你会经常听到很多关于数组的问题，例如，数组的反转、数组的排序或者查找数组中的一个元素。

数组结构的一个关键优点是在知道索引的情况能够以 O(1) 的复杂度找到一个元素。但是增加或者删除一个元素是很慢的，因为一旦创建了一个数组，你就不能改变它的大小了。

为了创建一个更长或者更短的数组，你需要创建一个新的数组，然后将所有元素从旧数组中复制到新数组中。

解决数组问题的关键是，你要对数组这种数据结构有一个深刻的认识，同时还要了解基本的程序流程如循环、递归以及基本的操作符。

下面是一些经常问到和数组相关的面试题，你可以拿来练习：

在一个给定的从1到100的整型数组中，如何快速找到缺失的数字？
如何找到一个给定的整型数组中的重复数字？
在一个未排序的整型数组中，如何找到最大和最小的数字？
在一个整型数组中，如何找到一个所有成对的数字，满足它们的和等于一个给定的数字？
如果一个数组包含多个重复元素，如何找到这些重复的数字？
用 Java 实现从一个给定数组中删除重复元素？
如何利用快速排序对一个整型数组进行排序?
如何从一个数组中删除重复元素？
用 Java 实现数组反转？
如何不借助库实现从数组中删除重复元素？

这些问题不仅可以帮助你提高解决问题的技巧，还可以帮助提升对数组结构的认识。

如果你需要更多关于数组的进阶的问题，可以参考《代码面试训练营：算法和数据结构》，这是一个训练营形式的算法课程，特别针对像 Google、微软、Apple 和 Facebook 这样的技术巨人面试准备而设计。

2. 链表的编程问题
链表是另外一个常见的数据结构，对数组结构是一个补充。和数组类似，它也是一个线性的数据结构，以线性方式存储元素。

不过和数组不同的是，链表的元素不是存储在连续位置中，而是分散在各个内存中的各个位置，通过节点链接起来。

一个链表就是一个包含了下个节点内存地址的节点列表。

基于这种结构，可以很容易实现链表中元素的添加和删除，因为只需要改变节点的指向而无需创建一个新的数组。不过链表中的查找是相对困难的，在一个单向链表中需要花费 O(n) 的时间代价来查找一个元素。

链表有几种不同的形式。首先是单向链表，在这个结构你只能向一个方向遍历（向前或者反转）；其次是双向链表，你可以双向遍历（向前或者向后）；最后是环形链表，组成一个环的形式。

要解决链表问题，你就必须了解递归的相关知识，因为链表是一种递归的数据结构。
如果你从链表中去掉一个节点, 剩下的数据结构仍然是链表，因此, 许多链表问题有比遍历更简单的递归解决方案.

下面是一些最常见和流行的链表面试问题和解决方案:

在一次遍历中，怎样发现单个链表的中间元素?
怎样验证给定的链表是环形的? 怎样发现这个环的起始节点?
怎样翻转链表?
不使用递归，怎样反转单个链表?
在未排序链表中，怎样移除重复的节点?
怎样找出单个链表的长度?
从单个链表的结尾处，怎样找出链表的第三个节点?
怎样使用栈计算两个链表的和?

这些问题可以帮助你提升解决问题的技巧，同时完善链表数据结构有关的知识.

3. 字符串编程面试问题
与数组和链表数据结构一起，字符串是编程工作面试中的另一个热门话题。我从未参加过没有问过基于字符串相关问题的编码面试。

字符串的一个优势在于，如果你了解数组，你可以很容易地解决基于字符串的问题，因为字符串仅仅是一个字符数组。

因此，在解决基于数组的编程问题中所学到的所有技术也可用于解决字符串编程问题。

以下是编程求职面试中常见的字符串编程问题的列表：

如何输出字符串中的重复字符？
如何判断两个字符串是否互为回文？
如何从字符串中输出第一个不重复字符？
如何使用递归实现字符串反转?
如何检查字符仅包含数字字符？
如何在字符串中找到重复字符？
如何对给定字符串中的元音及辅音进行计数？
如何计算给定字符传中特定字符出现的次数？
如何找到一个字符串的全排列？
在不使用任何库方法的情况下如何反转给定语句中的单词？
如何判断两个字符串是否互为旋转？
如何判断给定字符串是否是回文？

这些问题有助于提高你对字符串相关数据结构的了解。如果你可以在没有任何帮助的情况下解决所有这些 String 问题，那么你状态良好。

对于更高级的问题，我建议你解决 Steven Skiena 在算法设计手册中给出的问题，这是一本有颇具挑战的算法问题的书。

4. 二叉树编程面试问题
到目前为止，我们只研究了线性数据结构，但现实世界中的所有信息无法全部使用线性方式表示，而这正是树数据结构所擅长的地方。

树是一种支持以分层方式存储数据的数据结构。根据你存储数据的方式，有不同类型的树，例如二叉树，其中每个节点最多有两个子节点。

与它的近亲二叉搜索树一起，它们也是最流行的树数据结构之一。因此，你会发现很多基于它们的问题，例如如何遍历它们、计算节点数、查找深度，以及检查它们是否平衡。

解决二叉树问题的一个关键点是对其理论的深刻理解，例如： 什么是二叉树的大小或深度，什么是叶节点，什么是节点，以及对流行的遍历算法的理解，例如前序、后序和中序遍历。

以下是在软件工程师或开发人员的面试中流行的基于二叉树的编码问题的列表：

二叉搜索树是如何实现的？
如何在给定二叉树上实现前序遍历？
不使用递归如何按照前序遍历给定二叉树？
如何在给定二叉树上实现中序遍历？
不使用递归情况下如何使用中序遍历输出给定二叉树所有节点？
如何实现后序遍历算法？
如何不使用递归实现二叉树的后续遍历？
如何输出二叉搜索树的所有叶节点？
如何在给定二叉树中计算叶节点数目？
如何在给定数组中执行二分搜索？

如果你觉得你对二叉树编码的理解不够充分而且你无法独立解决这些问题，我建议你回过头来选择一个好的数据结构和算法课程，如从0到1：Java版数据结构及算法。

5. 编程面试问题之杂项
除了基于数据结构的问题之外，大多数编程工作面试还会询问算法、设计、位操作和基于逻辑的常规问题，我将在本节中对其进行介绍。

练习这些概念很重要，因为有时在实际面试中解决这些概念很棘手。提前练习它们不仅能让你熟悉它们，而且还让你更自信地向面试官解释其解决方案。

冒泡排序是如何实现的?
迭代式快排算法是如何实现的？
你如何实现插入排序算法？
合并排序算法是如何实现的？
桶排序算法是如何实现的？
计数排序算法是如何实现的？
基数排序算法是如何实现的？
在不使用第三个变量的前提下如何交换两个数？
如何检查两个矩形是否重叠？
如何设计一个自动售货机？

如果你需要更多类似的编程问题，你可以从像 Cracking The Code Interview 这样的书中获得帮助，此书是由 Gayle Laakmann McDowell 编著，其中提供了 189+ 个编程问题和解决方案。一本好书，可以在短时间内为编程类求职面试做准备。

顺便说一句，你在实践中解决的问题越多，你的准备就越充足。因此，如果你认为 50 道题目还不够并且你需要更多，那么请查看这些附加的 50 个编程问题，以便进行电话面试以及这些书籍和课程，和进行更全面的准备。

现在你已经准备好编程面试了
这些是数据结构和算法之外的一些最常见的问题，可以帮助你在面试中做得很好。

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

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

如果你正在寻找2018年的编程或软件开发工作，你可以使用此编程问题列表开始准备了。

此列表提供了用于“备战”的不错的主题，同时也有助于评估你的准备工作，以找出你的优势和劣势所在。

熟悉数据结构和算法对于编程面试的成功是非常重要的，而且这应该是你将注意力集中的地方。

原文

翻译