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

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

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

---

本文的内容主要总结了《剑指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.5、栈和队列

栈的特点：先进后出
队列的特点：先进先出

面试题八：用俩个栈实现队列
用两个栈实现一个队列。队列的声明如下，请实现它的两个函数 appendTail 和 deleteHead ，分别完成在队列尾部插入整数和在队列头部删除整数的功能。(若队列中没有元素，deleteHead 操作返回 -1 )

根据栈先进后出的特性，我们每次往第一个栈里插入元素后，第一个栈的底部元素是最后插入的元素，第一个栈的顶部元素是下一个待删除的元素。为了维护队列先进先出的特性，我们引入第二个栈，用第二个栈维护待删除的元素，在执行删除操作的时候我们首先看下第二个栈是否为空。如果为空，我们将第一个栈里的元素一个个弹出插入到第二个栈里，这样第二个栈里元素的顺序就是待删除的元素的顺序，要执行删除操作的时候我们直接弹出第二个栈的元素返回即可。

用俩个队列实现一个栈
做法类似，可以先将元素插入一个队列，删除元素时，将前n-1个元素依次插入第二个队列即可

3.6、算法与数据操作

• 递归与循环
• 排序与查找：二分查找，归并排序和快速排序
• 动态规划=》存在最优解即贪婪算法
• 位运算

大数相乘，大数的排列组合等为什么要取模 1000000007是一个质数（素数），对质数取余能最大程度避免结果冲突/重复
int32位的最大值为2147483647，所以对于int32位来说1000000007足够大。
int64位的最大值为2^63-1，用最大值模1000000007的结果求平方，不会在int64中溢出。
所以在大数相乘问题中，因为(a∗b)%c=((a%c)∗(b%c))%c，所以相乘时两边都对1000000007取模，再保存在int64里面不会溢出。
这道题为什么要取模，取模前后的值不就变了吗？ 确实：取模前 f(43) = 701408733, f(44) = 1134903170, f(45) = 1836311903, 但是 f(46) > 2147483647结果就溢出了。
取模后 f(43) =701408733, f(44) = 134903163 , f(45) = 836311896, f(46) =971215059没有溢出。

取模之后能够计算更多的情况，如 f(46)

这道题的测试答案与取模后的结果一致。

总结一下，这道题要模1000000007的根本原因是标准答案模了1000000007。不过大数情况下为了防止溢出，模1000000007是通用做法，原因见第一点

面试题九：旋转数组的最小数字
把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。输入一个递增排序的数组的一个旋转，输出旋转数组的最小元素。例如，数组 [3,4,5,1,2] 为 [1,2,3,4,5] 的一个旋转，该数组的最小值为1。

方法一：遍历
方法二：二分查找（俩个递增数组）

	int minArray(vector<int>& numbers) {
        int left = 0, right = numbers.size() - 1;
        while(right > left){
            int mid = (right + left) / 2;
            if(numbers[mid] < numbers[right]){
                right = mid;//为什么不等于mid - 1 比如{4,5,3,3,3}  就找不到3了
            }else if(numbers[mid] > numbers[right]){
                left = mid + 1;//为什么mid + 1 因为确定mid的数大于右边了 mid肯定不是最小元素了 所以可以从右边开始找
            }else{
                right--;//为什么要右边-- 比如{1,3,3} 如果左边+1 那就找不到1 了
            }            
        }
        return numbers[left];        
    }

面试题十：矩阵中的路径
给定一个 m x n 二维字符网格 board 和一个字符串单词 word 。如果 word 存在于网格中，返回 true ；否则，返回 false 。单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。

面试题十一：机器人的运动范围
地上有一个m行n列的方格，从坐标 [0,0] 到坐标 [m-1,n-1] 。一个机器人从坐标 [0, 0] 的格子开始移动，它每次可以向左、右、上、下移动一格（不能移动到方格外），也不能进入行坐标和列坐标的数位之和大于k的格子。例如，当k为18时，机器人能够进入方格 [35, 37] ，因为3+5+3+7=18。但它不能进入方格 [35, 38]，因为3+5+3+8=19。请问该机器人能够到达多少个格子？

dfs的经典题目

面试题十：剪绳子
给你一根长度为 n 的绳子，请把绳子剪成整数长度的 m 段（m、n都是整数，n>1并且m>1），每段绳子的长度记为 k[0],k[1]…k[m-1] 。请问 k[0]k[1]…*k[m-1] 可能的最大乘积是多少？例如，当绳子的长度是8时，我们把它剪成长度分别为2、3、3的三段，此时得到的最大乘积是18。

思路一：动态规划

1. 我们想要求长度为n的绳子剪掉后的最大乘积，可以从前面比n小的绳子转移而来
2. 用一个dp数组记录从0到n长度的绳子剪掉后的最大乘积，也就是dp[i]表示长度为i的绳子剪成m段后的最大乘积，初始化dp[2] = 1
3. 我们先把绳子剪掉第一段（长度为j），如果只剪掉长度为1，对最后的乘积无任何增益，所以从长度为2开始剪
4. 剪了第一段后，剩下(i - j)长度可以剪也可以不剪。如果不剪的话长度乘积即为j * (i - j)；如果剪的话长度乘积即为j * dp[i - j]。取两者最大值max(j * (i - j), j * dp[i - j])
5. 第一段长度j可以取的区间为[2,i)，对所有j不同的情况取最大值，因此最终dp[i]的转移方程为
   dp[i] = max(dp[i], max(j * (i - j), j * dp[i - j]))
6. 最后返回dp[n]即可

思路二：贪心

核心思路是：尽可能把绳子分成长度为3的小段，这样乘积最大

证明可参考这个题解

步骤如下：

1. 如果 n == 2，返回1，如果 n == 3，返回2，两个可以合并成n小于4的时候返回n - 1
2. 如果 n == 4，返回4
3. 如果 n > 4，分成尽可能多的长度为3的小段，每次循环长度n减去3，乘积res乘以3；最后返回时乘以小于等于4的最后一小段
4. 以上2和3可以合并

面试题十一：剪绳子二
给你一根长度为 n 的绳子，请把绳子剪成整数长度的 m 段（m、n都是整数，n>1并且m>1），每段绳子的长度记为 k[0],k[1]…k[m - 1] 。请问 k[0]k[1]…*k[m - 1] 可能的最大乘积是多少？例如，当绳子的长度是8时，我们把它剪成长度分别为2、3、3的三段，此时得到的最大乘积是18。
答案需要取模 1e9+7（1000000007），如计算初始结果为：1000000008，请返回 1。

大数问题。注意n的范围，需要用long型接收

附上链接1.大数取余,2.循环取余,3.快速幂

面试题十二： 二进制中1的个数
编写一个函数，输入是一个无符号整数（以二进制串的形式），返回其二进制表达式中数字位数为 ‘1’ 的个数（也被称为 汉明重量).）。

1. 判断时要判断 n != 0 而不是 n>0 。 因为是无符号整数，带符号整数最高位是1时为负数。
2. 要用 n >>> 1 而不是 n >> 1。因为>>是带符号右移，当n为负数时，最高位补1
3. n&（n-1）其实就是最低位1变成零

3.3、应聘者提问环节

参考资料《剑指offer》