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

已有许多计算机科学专业的毕业生和程序员在 Uber 和 Netflix 等初创公司、亚马逊,微软和谷歌等大型组织,以及诸如 Infosys 或 Luxsoft 这样的服务型公司中申请过编程、编码及软件开发职位,但他们中的许多人都不知道当你在这些公司申请工作时会遇到什么样的编程面试问题

在本文中,我将分享一些常见的编程面试问题,这些问题来自于不同经验水平的程序员,囊括从刚大学毕业的人到具有一到两年经验的程序员

编码面试主要包括数据结构和基于算法的问题,以及一些诸如如何在不使用临时变量的情况下交换两个整数这样的逻辑问题?

我认为将编程面试问题划分到不同的主题区域是很有帮助的。我在面试中经常看到的主题区域是数组、链表、字符串、二叉树,以及源于算法的问题(例如字符串算法,排序算法,如 quicksort 或基数排序,以及其他杂项),这就是你能在这篇文章中找到主要内容。

我们无法保证你会被问及这些编程或数据结构和算法问题,但它们会让你充分了解在实际编程工作面试中可预期的各类问题。

一旦你知道了这些问题,你应该有足够的信心参加任何电话或面对面的面试。

顺便说一句,如果你对基本的数据结构和算法没有足够了解,或者你多年未接触相关知识,那么尝试这些问题毫无意义。

在这种情况下,你应该学习像 Robert Horvick 的算法及数据结构第1部分和第2部分这样的优秀课程以更新你的数据结构和算法技能。

50个算法和代码面试题

闲言少叙,下面就是我给出的程序类面试中最常问到的问题清单

1. 数组问题

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

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

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

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

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

  1. 在一个给定的从1到100的整型数组中,如何快速找到缺失的数字?(解决方案

  2. 如何找到一个给定的整型数组中的重复数字?(解决方案

  3. 在一个未排序的整型数组中,如何找到最大和最小的数字?(解决方案

  4. 在一个整型数组中,如何找到一个所有成对的数字,满足它们的和等于一个给定的数字?(解决方案

  5. 如果一个数组包含多个重复元素,如何找到这些重复的数字?(解决方案

  6. 用 Java 实现从一个给定数组中删除重复元素?(解决方案

  7. 如何利用快速排序对一个整型数组进行排序?(解决方案

  8. 如何从一个数组中删除重复元素?(解决方案

  9. 用 Java 实现数组反转?(解决方案

  10. 如何不借助库实现从数组中删除重复元素?(解决方案

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

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

如果你感觉 10 个问题还不够,还需要更多的联系,那就看看这个 30 个数组问题的列表。

2. 链表的编程问题

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

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

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

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

关于链表和数组的不同的更多说明,可以阅读这篇文章

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

要解决链表问题,你就必须了解递归的相关知识,因为链表是一种递归的数据结构。

如果你从链表中去掉一个节点, 剩下的数据结构仍然是链表,因此, 许多链表问题有比遍历更简单的递归解决方案.

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

  1. 在一次遍历中,怎样发现单个链表的中间元素? (答案)

  2. 怎样验证给定的链表是环形的? 怎样发现这个环的起始节点? (答案)

  3. 怎样翻转链表? (答案)

  4. 不使用递归,怎样反转单个链表? (答案)

  5. 在未排序链表中,怎样移除重复的节点? (答案)

  6. 怎样找出单个链表的长度? (答案)

  7. 从单个链表的结尾处,怎样找出链表的第三个节点? (答案)

  8. 怎样使用栈计算两个链表的和? (答案)

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

如果你解决这些链表编码题仍存在问题,我建议你通过 Data Structures and Algorithms: Deep Dive** Using Java** 课程来提升你的数据结构和算法技能.

你也可以从30 linked list interview questions 清单中获取更多练习题.

3. 字符串编程面试问题

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

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

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

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

  1. 如何输出字符串中的重复字符? (解答)

  2. 如何判断两个字符串是否互为回文? (解答)

  3. 如何从字符串中输出第一个不重复字符?(解答)

  4. 如何使用递归实现字符串反转? (解答)

  5. 如何检查字符仅包含数字字符?(解答)

  6. 如何在字符串中找到重复字符?(解答)

  7. 如何对给定字符串中的元音及辅音进行计数?(解答)

  8. 如何计算给定字符传中特定字符出现的次数? (解答)

  9. 如何找到一个字符串的全排列?(解答)

  10. 在不使用任何库方法的情况下如何反转给定语句中的单词? (解答)

  11. 如何判断两个字符串是否互为旋转? (解答)

  12. 如何判断给定字符串是否是回文?(解答)

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

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

如果你需要更多练习,这里是另外一个 20 个字符串编码问题的列表。

4. 二叉树编程面试问题

到目前为止,我们只研究了线性数据结构,但现实世界中的所有信息无法全部使用线性方式表示,而这正是树数据结构所擅长的地方。

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

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

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

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

  1. 二叉搜索树是如何实现的?(解答)

  2. 如何在给定二叉树上实现前序遍历?(解答)

  3. 不使用递归如何按照前序遍历给定二叉树?(解答)

  4. 如何在给定二叉树上实现中序遍历?(解答)

  5. 不使用递归情况下如何使用中序遍历输出给定二叉树所有节点?(解答)

  6. 如何实现后序遍历算法? (解答)

  7. 如何不使用递归实现二叉树的后续遍历? (解答)

  8. 如何输出二叉搜索树的所有叶节点?(解答)

  9. 如何在给定二叉树中计算叶节点数目?(解答)

  10. 如何在给定数组中执行二分搜索? (解答)

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

如果你需要更多推荐,请参阅我的有用数据结构算法书籍课程列表。

5. 编程面试问题之杂项

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

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

  1. 冒泡排序是如何实现的? (解答)

  2. 迭代式快排算法是如何实现的?(解答)

  3. 你如何实现插入排序算法?(解答)

  4. 合并排序算法是如何实现的?(解答)

  5. 桶排序算法是如何实现的?(解答)

  6. 计数排序算法是如何实现的?(解答)

  7. 基数排序算法是如何实现的?(解答)

  8. 在不使用第三个变量的前提下如何交换两个数?(解答)

  9. 如何检查两个矩形是否重叠?(解答)

  10. 如何设计一个自动售货机?(解答)

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

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

现在你已经准备好编程面试了

这些是数据结构和算法之外的一些最常见的问题,可以帮助你在面试中做得很好。

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

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

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

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

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