手写二叉树？程序员面试最常见问题TOP 48

同学，你会手写二叉树吗?近来正值秋招季节，很多编程面试都要求手写数据结构手推机器学习算法。各位同学为了面试也会刷各种编程题，其中数据结构与排序搜索算法又是最为基础的内容。在本文中，我们为各位读者准备了 48 道基础面试题，它可以帮助我们更深地理解数据结构。本文所有面试题都提供了 Java 解决方案，并介绍了比较流行的 GitHub 面试题项目。

很多计算机科学专业毕业生和程序员都会去 Uber、今日头条这样的独角兽公司，或者亚马逊、微软和谷歌这样的科技巨头申请编程和软件开发职位。你在申请这些工作时，肯定很想知道面试官会问到哪些问题。

在本文中，作者会分享一些常见的编程面试问题，这些问题来自于针对不同经验层次的程序员的面试——从应届毕业生到具有一两年经验的程序员。

编程面试题通常包含数据结构和基于算法的问题，以及一些逻辑问题，例如：如何在不使用临时变量的情况下交换两个整数?

为了清晰，编程面试题需要划分为不同主题。我们在面试中经常看到的领域是数组、链表、字符串、二叉树以及有关算法的问题(例如字符串算法、快速排序或基数排序等排序算法)，本文将介绍这些内容。

虽然本文无法覆盖你在面试中将要面临的所有问题，但是它可以给你提供足够的思路，让你在面试时对于各种挑战有所准备。

一旦解决了这些问题，你就可以有信心面对任何电话面试或现场面试了。

当然，如果你对于基本数据结构和算法没有足够的知识储备，那么直接接触以下问题将对你没有帮助。

算法和编程面试题 TOP 48

废话少说，这里有一份「编程面试最常见的问题列表」：

1. 数组编程面试问题

数组是最基本的数据结构，它将元素储存在连续的内存空间中。数组也是面试官最喜欢问的主题之一，在任何编程面试中都能听到非常多关于数组的问题，例如反转数组、排序数组或搜索数组元素等。

数组这种数据结构的主要优点在于如果给定索引，那么它会提供 O(1) 复杂度的搜索，这种搜索速度非常迅速。但是从数组中添加或移除元素会比较慢，因为一旦创建了数组，我们就很难再更改它的大小。如果需要更长或更短的数组，我们就需要重新创建新数组，并将老数组的所有元素复制到新数组中。

解决数组问题的关键是对数组数据结构有比较深的理解，同时还需要了解循环、递归和基本运算子等常见的编程结构。以下是一些常见的数组编程面试问题：

(1) 在一个元素为 1 到 100 的整数数组中，如何搜索缺失元素?

解决方案：

(2) 给定一个数组，如何搜索重复元素?

解决方案：

(3) 给定一个乱序数组，如何搜索最大和最小元素?

解决方案：

(4) 给定一个数值，如何搜索整数数组中加和为该数值的成对元素?

解决方案：

(5) 如果数组包含多个重复值，如何搜索所有重复值?

解决方案：

(6) 给定一个数组，如何用 Java 删除重复元素?如何在不使用库的情况下移除数组中的重复元素?

解决方案：

(7) 如何使用快速排序算法对整数数组进行排序?

解决方案：

(8) 如何使用 Java 反转一个数组?

解决方案：

这些问题不仅能帮助我们提高解决问题的能力，同时也能提升我们关于数组数据结构的理解。

如果你需要了解更多基于数组的深度问题，你可以在 GitHub 或 Coursera 上多找找关于数据结构的课程与资料，例如在 GitHub 中，就有非常多关于数组的学习资料，下面我们介绍了一份中文版的谷歌的面试资料，它在 GitHub 上有 6 万多的收藏量。

项目地址：

https://github.com/jwasham/coding-interview-university/blob/master/translations/README-cn.md

2. 链表编程面试问题

链表是补充数组数据结构的另一种常见数据结构。与数组类似，它也是线性数据结构，以线性方式存储元素。

然而，与数组不同的是，它不会将元素存储在连续的位置;相反，它会将其分散存储在内存中，彼此通过节点相互连接。链表是节点列表，其中每个节点包含存储的值和下一个节点的地址。

由于这种结构，在链表中添加或删除元素变得很简单，因为你只需要改变链接而不是创建数组，但是这样会使搜索变得困难，并且经常需要 O(n) 的时间复杂度才能在单个链表中找到某个元素。

这篇文章

(https://javarevisited.blogspot.com/2013/07/difference-between-array-and-linked-list-java.html)提供了更多关于数组和链表数据结构之间差异的信息。