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

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

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

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

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

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

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

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

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

算法和编程面试题 TOP 48

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

1. 数组编程面试问题

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

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

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

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

• 解决方案：http://javarevisited.blogspot.com/2014/11/how-to-find-missing-number-on-integer-array-java.html

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

• 解决方案：http://javarevisited.blogspot.com/2014/01/how-to-remove-duplicates-from-array-java-without-collection-API.html

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

• 解决方案：http://java67.blogspot.com/2014/02/how-to-find-largest-and-smallest-number-array-in-java.html

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

• 解决方案：http://javarevisited.blogspot.com/2014/08/how-to-find-all-pairs-in-array-of-integers-whose-sum-equal-given-number-java.html

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

• 解决方案：http://javarevisited.blogspot.com/2014/03/3-ways-to-find-first-non-repeated-character-String-programming-problem.html

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

• 解决方案：http://javarevisited.blogspot.com/2014/01/how-to-remove-duplicates-from-array-java-without-collection-API.html

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

• 解决方案：http://javarevisited.blogspot.com/2014/08/quicksort-sorting-algorithm-in-java-in-place-example.html

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

• 解决方案：http://javarevisited.blogspot.com/2013/03/how-to-reverse-array-in-java-int-String-array-example.html

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

如果你需要了解更多基于数组的深度问题，你可以在 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)提供了更多关于数组和链表数据结构之间差异的信息。

链表还有多种变体，如单链表，即允许在一个方向(正向或反向)上遍历;双链表则允许你在两个方向(向前或向后)遍历;最后是循环链表，它形成一个循环。

要解决关于链表的问题，掌握递归知识很重要，因为链表是递归数据结构。

如果你从链表中取出一个节点，剩下的数据结构仍然是链表，因此，许多链表问题的递归解比迭代解更简单。

以下是关于链表的一些常见问题和解决方案：

（编辑：核心网）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!