程序员面试的注意事项(二）：面试需要的基础知识

【版权申明】未经博主同意，谢绝转载！（请尊重原创，博主保留追究权）；
本博客的内容来自于程序员面试的注意事项(二）：面试需要的基础知识；
学习、合作与交流联系q384660495；
本博客的内容仅供学习与参考，并非营利；

文章目录

• 程序员面试的注意事项(二）：面试需要的基础知识
• 一、面试所需要的基本知识
• 1、面试官谈基础知识
• 2、编程语言
• 3、数据结构
• • 3.1、数组
  • 3.2、字符串
  • 3.3、链表
  • 3.4、树
  • 3.3、应聘者提问环节

本文的内容主要总结了《剑指offer》，并非原创。

一、面试所需要的基本知识

提示：以下部分主要介绍了面试必须掌握的编程语言、数据结构、算法和数据操作等

1、面试官谈基础知识

• 数据结构和算法******
• 编程能力******
• 部分数学知识，如概率**
• 问题的分析和推理能力***
• 算法时间、空间复杂度***
• 并发控制
• 语言的基本概念******

2、编程语言

程序员写代码总是基于某一种编程语言，因此技术面试的时候都会直接或者间接的涉及至少一种编程语言。提问的方式，要么直接问语言的语法，要么让应聘者用一种编程语言写代码解决一个问题（有的面试题会限制编程语言，建议多掌握一些语言）

这边推荐一些好的学习编程语言的网站：
菜鸟教程
JavaGuide

3、数据结构

数据结构一直是技术面试的重点，大部分面试题都是围绕着数组、字符串、链表、树、栈及队列这几种基本常见的数据结构展开的。数组和字符串是最基本的数据结构，它们用连续的内存分别存储数字和字符。链表和树是面试中出现频率最高的数据结构，由于操作链表和树需要用到大量指针，一定要留意代码的鲁棒性。栈是一个与递归紧密相关的数据结构，同样队列也与广度优先遍历算法紧密相关。

3.1、数组

数组的空间效率低

数组可以说是最简单的一种数据结构，它占据一块连续的内存并按照顺序存储数据。需要先指定数组的容量大小，然后根据大小分配内存。即使只在数组中存储一个数字，也需要为所有的数据预先分配内存。因此数组的空间效率不是很好，经常有空闲的区域没有利用。

数组的时间效率高

由于数组中的内存是连续的，可以根据下标在O(1)时间读/写任何元素，因此时间效率很高。我们可以根据数组时间效率高的特点，用数组来实现简单的哈希表：把数组的下标设为哈希表的键值（Key），而把数组中的每一个元素设为哈希表的值（Value）。有了这样的哈希表，我们就可以在O(1)时间内实现查找。

动态数组解决空间效率不高的问题

当数组元素数目超过数组的容量的时候，我们再重新开辟一个更大的空间，将之前的数据复制到新的数组中，再把之前的内存释放掉，这样就能减少内存的浪费。但是每一次扩容都要进行大量的额外操作，因此使用动态数组时要尽量减少改变数组容量大小的次数。

面试题一：数组中重复的数字
题目：找出数组中重复的数字。 在一个长度为n的数组里的所有数字都在0~n-1的范围内。数组中某些数字是重复的，但不知道哪些数字是重复的，也不知道每个数字重复了几次。请找出数组中任意一个重复的数字。
例如：如果输入长度为7的数组{2，3，1，0，2，5，3}，那么对应的输出是重复的数字2或者3

思路一：先对数组进行排序，从排序的数组中找出重复的数字是很容易的。排序数组的时间复杂度为O(nlogn)，空间复杂度为O(1)，排序算法可以参考我的这篇文章面试必会算法（1）：排序算法

思路二：利用哈希表解决问题。从头到尾扫描数组的每一个数字，没扫描到一个数字的时候，都可以用O(1)的时间来判断哈希表里是否包含了该数字。该算法的时间复杂度为O(n)，空间复杂度为O(n)。

思路三：重排这个数组。从头到尾依次扫描这个数组中的每一个数字。当扫描到下标为i的数字时，首先比较这个数字是不是等于i。如果是，则接着扫描下一个数字。如果不是，则再拿他和第m个数字进行比较。如果它和第m个数字相等，就找到了一个重复的数字；如果它和第m个数字不相等，就把第i个数字和第m个数字交换，把m放到属于它的位置。接下来再重复比较、交换的过程，直到我们发现一个重复的数字。

测试用例：1、包含一个或多个重复数字 2、 不包含重复数字3、无效输入数据（空指针，包含0~n-1之外的数字）尤其注意边界问题。

面试题二：不修改数组找到重复的数字。
在一个长度为n+1的数组里的所有数字都在1~n的范围内。数组中至少有一个数字是重复的。请找出数组中任意一个重复的数字，但不能修改输入的数组。例如，如果输入长度为8的数组{2,3,4,5,6,7,3,2}，那么对应的输出是重复的数字2或者3。

思路一：利用哈希表解决问题。创建一个长度为n+1的辅助数组，从头到尾扫描数组的每一个数字，没扫描到一个数字的时候，都可以用O(1)的时间来判断哈希表里是否包含了该数字。该算法的时间复杂度为O(n)，空间复杂度为O(n)。

思路二：可以把1~n的数字从中间的数字m分为俩部分，前面一半为1~m,后面一半为m+1~n。如果1~m的数字的数目超过m，那么这一半的区间里一定包含重复的数字；否则，另一半m+1~n的区间里一定包含重复的数字。我们就可以把包含重复数字的区间一分为二，直到找到一个重复的数字。这个过程和二分查找算法很类似，只是多了一步统计区间里数字的数目。需要指出的是，这种算法不能保证一定找出所有重复的数字。

面试题三：二维数组中的查找
在一个二维数组中，每一行都按照从左到右递增的顺序排序，每一列都按照从上到下的顺序排序，请完成一个函数，输入这样一个二维数组和一个整数，判断数组中是否包含有该整数。

思路一：从左下角或者右上角数字开始比较，切记不要从左上角和右下角比较，这样无法缩小比较范围

3.2、字符串

字符数组引用和指针引用的区别

字符串都以‘\0’作为结尾。为了节省内存，c和c++把常量字符串放到单独的一个内存区域。当几个指针同时赋值给相同的常量字符串时，他们实际会指向相同的内存地址。但是用字符数组，情况有所不同。

String的内容是不可改变的

对String的修改操作都是生成一个新的String实例

面试题四：替换空格
请实现一个函数，把字符串中的每个空格替换成“%20”。例如，输入“we are happy”，则输出“we%20are%20happy”。

思路一：从头到尾扫描字符串，每次碰到空格字符的时候进行替换。替换的时候必须要把空格后面所有的字符都后移2个字节，否则就有俩个字符被覆盖了。时间复杂度为O(n²)，这种方法并不高效！

思路二：可以先遍历一次字符串，这样就能统计出字符串中空格的总数，并由此计算出替换之后的字符串的总长度。第二步，从字符串的后面开始复制和替换，准备俩个指针，分别指向原始字符串的末尾和替换之后的字符串的末尾。向前移动指针并依次把字符复制到新字符串中，直到碰到空格时，在新字符串中插入“%20”。这个算法的时间复杂度为O(n)。

测试用例：1、多个空格 2、没有空格 3、字符串是空指针、空格字符、空字符、连续多个空格
相关题目：合并俩个有序数组为有序排序。

3.3、链表

链表的空间复杂度高

链表是一种动态数据结构，是因为在创建链表时，无须知道链表的长度。内存分配不是创建链表时一次性完成的，而是每添加一个节点分配一次内存。由于没有闲置的内存，链表的空间效率比数组高。

链表的时间效率低

链表的内存不是一次性分配的，因而我们无法保证链表的内存和数组一样是连续的。因而想在链表中找到它的第i个节点，只能从头节点开始，依次遍历。它的时间效率为O(n)，数组的时间效率为O(1)

除了简单的单链表，还有环形链表、双向链表、复杂链表

面试题五：从尾到头打印链表
输入一个链表的头节点，从尾到头反过来打印出每个节点的值。（问清楚是否允许修改链表的结构）

思路一：利用栈的“后进先出”特性，每经过一个节点的时候，把该节点放到栈中。

思路二：既然想到栈来实现这个函数，而递归在本质上就是一个栈的结构，于是很自然地想到可以用递归来实现。

当链表非常长的时候，就会导致函数调用的层级很深，从而很可能导致函数调用栈溢出，显然用栈基于循环实现的代码的鲁棒性要好一些。

3.4、树

树的逻辑很简单：除根节点之外每个节点只有一个父节点，根节点没有父节点；除了叶节点之外所有节点都有一个或多个子节点，叶节点没有子节点。父节点和子节点之间用指针连接。重点掌握二叉树。

树的遍历方式有四种：前序遍历、中序遍历、后序遍历、宽度优先遍历（层次遍历）。前三种遍历都有循环和递归俩种不同的实现方法。

二叉树有许多特例，二叉搜索树就是其中之一。在二叉搜索树种，左子节点总是小于或等于根节点，而右子节点总是大于或等于根节点。我们可以平均在O(logn)的时间内根据数值在二叉搜索树中找到一个节点。

二叉树另外俩个特例是堆和红黑树。堆分为最大堆和最小堆。在最大堆中根节点的值最大，在最小堆中根节点的值最小。有很多需要快速找到最大值或最小值的问题都可以用堆来解决。红黑树是把树中的节点定义为红、黑俩种颜色，并通过规则确保从根节点到叶节点的最长路径的长度不超过最短路径的俩倍。

面试题六：重建二叉树
输入某二叉树的前序遍历和中序遍历的结果，请重建该二叉树。假设二叉树的前序遍历和中序遍历的结果中都不含重复的数字。

测试用例：普通二叉树（完全二叉树；不完全二叉树），特殊二叉树（只有一个节点的二叉树；只有左子节点的二叉树；只有右子节点的二叉树），特殊输入（空节点，前序遍历和后序遍历不匹配）

面试题七：二叉树的下一个节点
给定一棵二叉树和其中的一个节点，如何找出中序遍历序列的下一个节点？树中的节点除了有俩个分别指向左、右子节点的指针，还有一个指向父节点的指针。

如果一个节点有右子树，那么它的下一个节点就是它的右子树中的最左子节点

如果一个节点没有右子树：有俩种情况：
如果一个节点是他父节点的左子节点，那么它的下一个节点就是它的父节点。
如果一个节点

测试用例：普通二叉树（完全二叉树；不完全二叉树），特殊二叉树（只有一个节点的二叉树；只有左子节点的二叉树；只有右子节点的二叉树），不同位置的节点的下一个节点

3.3、应聘者提问环节

参考资料《剑指offer》