为工程师准备的 50 道数据结构和算法面试题 已翻译 100%

已有许多计算机科学专业的毕业生和程序员在 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 清单中获取更多练习题.