phpfwrite回文对技巧_手写二叉树轨范员面试最常见问题TOP 48

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

编程口试题常日包含数据构造和基于算法的问题，以及一些逻辑问题，例如：如何在不该用临时变量的情形下交流两个整数？

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

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

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

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

算法和编程口试题 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）供应了更多关于数组和链表数据构造之间差异的信息。

链表还有多种变体，如单链表，即许可在一个方向（正向或反向）上遍历；双链表则许可你在两个方向（向前或向后）遍历；末了是循环链表，它形成一个循环。

要办理关于链表的问题，节制递归知识很主要，由于链表是递归数据构造。

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

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

9. 如何在一次通报中找到单链表的中间元素？

10. 如何检讨给定的链表是否包含循环？如何找到循环的起始节点？

11. 如何反转链表？

12. 在没有递归的情形下如何反转单链表？

13. 如何删除乱序链表中的重复节点？

14. 如何丈量单链表的长度？

15. 如何从单链表的末端找出第三个节点？

16. 如何利用堆栈算出两个链表的总和？

这些问题有助于你发展办理问题的技能，并提升你对链表数据构造的理解。
目前有非常多的资源可以帮助我们理解链表，例如在 GitHub 上一个交互式的编码实践中，它利用 Jupyter Notebook 供应了数据构造与算法的各种练习，个中就包括了很多链表问题及实践。

项目地址：https://github.com/donnemartin/interactive-coding-challenges

3. 字符串编码口试问题

除了数组和链表数据构造，字符串也是编程事情口试中的另一热点话题。
我参加过的编码口试基本都问过关于字符串的问题。

如果你理解数组，那么你就能轻易地办理基于字符串的问题，由于字符串便是字符数组。
因此，你通过办理数组编程问题学到的所有技巧，也能用来办理字符串编程问题。

以下是编程事情口试中常问的字符串编程问题列表：

17. 如何打印字符串中重复的字符？

18. 如何检讨两个字符串是否互为逆序？

19. 如何打印字符串中首个非重复字符？

20. 如何利用递归反转给定字符串？

21. 如何检讨一个字符串是否仅包含数字？

22. 如何搜索字符串中的重复字符？

23. 给定一个字符串，如何统计元音数和辅音数？

24. 给定一个字符，犹如打算它在字符串中涌现的次数？

25. 如何搜索一个字符串的所有排列情形？

26. 在不该用任何库的情形下，如何反转给定句子中的单词？

27. 如何检讨两个字符串是不是互为旋转（rotation）？

28. 给定一个字符串，如何检讨它是不是回文构造？

这些问题可以提升你对字符串数据构造的理解。
如果你能独立办理所有这些字符串问题，解释你的状态很好。

如果想深入理解一些更繁芜的问题，我推举你去看 Steven Skiena 的《The Algorithm Design Manual》，这本书里有最难的算法问题。

网上也有该书的 PDF 版，下载地址：http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.471.4772&rep=rep1&type=pdf

如果你须要更多的练习，这里还有其余 20 个关于字符串编程的问题：

http://javarevisited.blogspot.sg/2015/01/top-20-string-coding-interview-question-programming-interview.html

4. 二叉树编程口试问题

现在我们只理解了线性数据构造方面的问题，但是真实天下中的所有信息不可能全是线性的，这就须要树数据构造了。

树数据构造许可以层级形式存储数据。
根据存储数据的办法，有多种树类型，如二叉树。

和它的近亲二叉查找树一样，它也是最盛行的树数据构造之一。
因此，你会看到很多干系的有趣问题。
例如，如何遍历树、打算节点数量、找出深度，以及检讨是否平衡。

办理二叉树问题的关键在于深厚的理论知识，如二叉树的大小或深度、什么是叶节点、什么是节点，以及理解盛行的遍历算法。

以下是软件工程师或开拓事情口试中常见的二叉树干系编程问题：

29. 如何实现二叉查找树？

30. 如何对给定二叉树实行前序遍历？

31. 如何在没有递归的情形下对给定二叉树实行前序遍历？

32. 如何对给定二叉树实行中序遍历？

33. 如何在没有递归的情形下通过对给定二叉树实行中序遍历来打印所有节点？

34. 如何实现后序遍历算法？

35. 如何在没有递归的情形下对给定二叉树实行后序遍历？

36. 如何打印二叉查找树的所有叶节点？

37. 如何打算给定二叉树中叶节点的数量？

38. 如何在给天命组中实行二元搜索？

如果你认为自己对二叉树编程的理解不敷，无法办理这些问题，我建议你先闇练节制数据构造和算法知识，比如你可以上这门课《From 0 to 1: Data Structures & Algorithms in Java》。
同样，你也可以查阅准备 Google 口试的一套完全手册，这套 GitHub 手册前面已经先容了，但它在二叉树等数据构造上真的有非常多的案例与教程。

项目地址：https://github.com/jwasham/coding-interview-university

如果你须要更多推举，可以参考：

5. 其它编程口试问题

除了数据构造方面的问题，大部分编程事情口试也会问关于算法、设计、位运算和通用的逻辑问题。

针对性练习很主要，由于有时在实际口试中它们会有点难解。
事先练习不仅能够让你熟习这些问题，还能让你在向口试官阐明答案时更加自傲。

39. 如何实现冒泡排序算法（bubble sort algorithm）？

40. 如何实现迭代快速排序算法（iterative quicksort algorithm）？

41. 如何实现插入排序算法（insertion sort algorithm）？

42. 如何实现归并排序算法（merge sort algorithm）？

43. 如何实现桶排序算法（bucket sort algorithm）？

44. 如何实现计数排序算法（counting sort algorithm）？

45. 如何实现基数排序算法（radix sort algorithm）？

46. 如何在不该用第三个变量的条件下交流两个数字？

47. 如何确认两个矩形是否重叠？

48. 如何设计自动贩卖机？

如果你想查看更多此类编程问题，可以阅读这本书《Cracking the Coding Interview: 189 Programming Questions and Solutions》，适宜短韶光内准备编程事情口试。

下载地址：http://lib1.org/_ads/fcb49f53d5e943ce8acdc4469f63dc5d

你练习的问题越多，准备就越充分。
因此，如果你认为 48 道题不足的话，可以查看：

现在你已经准备好口试了

这部分将先容一些数据构造和算法之外的常见问题，可以帮助你在口试中取得更好的表现。

我的博客中还有很多此类问题，详见：http://www.java67.com/

这些常见的编程、数据构造和算法问题是你去任何一家公司口试都必须知道的，不管是大公司还是小公司，不管口试的职位高或低。

如果你正在探求编程或软件开拓事情，那么你可以先利用这些编程问题开始准备。
该列表供应了一些不错的口试准备话题，能够帮助你评估自己的口试准备事情是否充分。

闇练节制数据构造和算法知识是编程事情口试成功的关键，你该当更多地关注这些问题。

扩展阅读：

原文链接：https://hackernoon.com/50-data-structure-and-algorithms-interview-questions-for-programmers-b4b1ac61f5b0