面经
作者：渺万里层云.
链接：https://www.nowcoder.com/discuss/344311
来源：牛客网
[网络：
1、OSI七层模型与TCP/IP 五层模型,
2、常见应用层协议和运输层、网络层协议，以及硬件如路由器之类在哪一层
3、TCP与UDP区别和应用场景，基于TCP的协议有哪些，基于UDP的有哪些
4、TCP可靠传输的保证，拥塞控制目和过程
5、TCP粘包现象原因和解决方法
6、TCP三次握手过程以及每次握手后的状态改变，为什么三次？为什么两次不行？如果你的答案是防止已失效的请求报文又传送到了服务端，建立了多余的链接，浪费资源，但这个答案被否定了，你还能给出什么答案？
7、TCP四次挥手过程以及状态改变，为什么四次？CLOSE-WAIT和TIME-WAIT存在的意义？如何查看TIME-WAIT状态的链接数量？为什么会TIME-WAIT过多？解决方法是怎样的？
8、TCP、UDP、IP、以太网报文格式以及重要字段，报文从一端到另一端传递的过程。
9、浏览器输入URL并回车的过程以及相关协议，DNS查询过程。
10、HTTP1.0、1.1、2.0之间的区别
11、HTTP与HTTPS之间的区别，HTTPS链接建立的过程，了解对称加密算法和非对称加密算法不？
12、HTTP请求有哪些，多说点。Post和get区别。
13、HTTP常见响应状态码，从1xx到5xx都要说。如304,301,302，504，
14、重定向和转发区别
15、cookie和session区别。
操作系统：
1、进程和线程的区别
2、协程呢？
3、进程间通信方式IPC
4、用户态和核心态
5、操作系统分配的进程空间是怎样的？线程能共享哪些？
6、操作系统内存管理方式，分页分段以及段页式的优缺点
7、页面置换算法有哪些，FIFO为什么不好？如何改进?LRU思想，手写LRU
8、死锁条件，解决方式。
](https://www.nowcoder.com/discuss/344311)
1、事务4大特性，一致性具体指什么？这4个特性mysql如何保证实现的？
2、事务隔离级别，4个隔离级别分别有什么并发问题？
3、Mysql默认隔离级别？如何保证并发安全？
4、RR和RC如何实现的？RR使用场景？对比volatile可见性，为什么RR的事务要设计成不能读另一个事务已经提交的数据？
5、隔离级别的单位是数据表还是数据行？如串行化级别，两个事务访问不同的数据行，能并发？
6、存储引擎Innodb和Myisam的区别以及使用场景
7、 介绍Inodb锁机制，行锁，表锁，意向锁
8、介绍MVCC.
9、哈希索引是如何实现的？
10、B树索引为什么使用B+树，相对于B树有什么优点？为什么不能红黑树？要提到磁盘预读
11、聚簇索引和非聚簇索引区别
12、回表查询和覆盖索引
13、如何创建索引？
14、如何使用索引避免全表扫描？
15、Explain语句各字段的意义
16、最左前缀！！联合索引B+树是如何建立的？是如何查询的？当where子句中出现>时，联合索引命中是如何的? 如 where a > 10 and b = “111”时，联合索引如何创建？mysql优化器会针对得做出优化吗？
17、MySQL中一条SQL语句的执行过程
18、数据库几大范式
19、数据库基本查询关键字使用，如left join on,where,beteen and,group by,having,limit,聚合函数等。
20、left join,right join,inner join,outer join的含义及区别
21、mysql主从复制过程，binlog记录格式，复制的异步半同步同步模式区别
22、主从复制或读写分离等数据不一致性问题以及如何解决
23、银行的话，可以会考mysql数据类型，如余额要用decimal
Redis问题：
1、为什么使用Redis
2、分布式缓存和本地缓存有啥区别？让你自己设计本地缓存怎么设计？如何解决缓存过期问题？如何解决内存溢出问题？
3、redis和mem***d的区别
4、redis常用数据结构和使用场景
5、Zset底层实现？跳表搜索插入删除过程？
6、redis过期淘汰策略
7、redis持久化机制？都有什么优缺点？持久化的时候还能接受请求吗？
8、redis事务
9、缓存雪崩和缓存穿透，以及解决方法
10、如何保证缓存和数据库的数据一致性？
11、redis是单线程还是多线程？为什么那么快？
12、五种IO模型的区别
13、select、poll、epoll的区别？
14、redis热key问题？如何发现以及如何解决？
15、redis数据分布方式？有什么优点？一致性hash呢？
16、redis主从复制，主从切换，集群
No3.数组中重复的数字。n个数，范围0到n-1,找到任意一个重复的,时间复杂度O(1);
No4,二维数组查找，从左到右递增，从上到下递增。
No5,字符串空格替换，如果有空格，就将他替换成%20
No6,从尾到头打印链表,递归和非递归方法
No7 重建二叉树,前序遍历和中序遍历重构二叉树
No8 二叉树的下一个节点。中序遍历的二叉树下一个节点，这个树的节点，有指向父指针;
No9,两个栈实现队列
No10 斐波那契数列;
No 10-1,青蛙可以挑一阶，也可以2阶，跳到n阶，几种做法
No10-2,变态跳，可以跳1-n阶，随便跳。求n阶几种方法;
No11,旋转数组最小的数字：非减排序的数组，可能存在重复
No12,矩阵中的路径。矩阵有字符，可以从任意开始，上下左右任意走，但不能走走过的格子，求是否存在一条包含给定字符串的路径。
No13,机器人的运动范围，从(0,0)开始，上下左右移动，但不能进入行坐标和列坐标数位之和大于k的格子，给定k,能打几个格子。
No14,剪绳子，长为n，剪m段（m,n都是整数，且m>1），所有的长度的乘积最大为多少。
No15,二进制中1的个数;
No16, 数值的整数次方
No17, 打印从1到最大的n位数
No18-1,删除节点。给定一链表头结点和指定节点，O(1)时间内，删除指定节点
No18-2.删除重复的节点。存在的重复节点，全都删了。
No19,实现函数来匹配包含‘.’和‘*’的正则表达式.
No20实现一个函数来判断字符串是否表示数值。
No20-2将字符串转换成整数；不合法返回0；
No21,调整数组顺序使得奇数位于偶数之前。
No22,返回链表的倒数第k个节点。
No23,链表中环的入口节点;
No24,反转链表,并返回反转之后的头结点。
No25,合并两个有序的链表，重建一个新的，包含所有的两个链表。--->单调不减
No26,输入A和B两个树，判断B是A的子树。空树不是子树
No27,二叉树的镜像。输入一个二叉树，将他变成他的镜像
No28,输入一个二叉树，判断二叉树是不是对称的。
No29,顺时针打印矩阵。
No30,包含min函数的栈
No31,栈的压入弹出序列,第一个表示压入序列，判断第二个是不 是弹出序列。
No32,从上到下打印二叉树
No33,输入一个整数数组，判断是不是二叉搜索树的后序遍历序列
No34,二叉树中和未某一值得路径
No35复杂链表的复制;链表不仅有val,next,还有一个指向任意节点random
No36二叉搜索树和双向链表;二叉搜索树转换成一个排序的双向链表，不能创建新的节点,只能调整指针顺序。
No37实现函数序列化二叉树和反序列二叉树
No38输入一个字符串，给出所有的排列;
No39,数组中出现超过一半的数字,如果不存在，返回0；
No40，最小的k个数
No41，数据流中的中位数，奇数个，中间那个。偶数个，中间俩的平均.
No42,连续子数组的最大和，数组中有正数有负数，求所有连续子数组的最大和。
No43,1-n所有数中，求所有十进制位出现1个总数
No44，从0-n,所有的从前到后排到一块，实现一个函数，求第k位的数字是几？
No45,给定一个数组，求组合到一块的最小数字
No46,0-25翻译成a-z,给一个数字，求有几种翻译方法
No47,礼物的最大价值，矩阵，每一步都有一个值，从左上到右下，只能向右或向下移动，求最大和
No48，最长不含重复字符的子字符串，
No49,只含2,3,5因子的数是丑数，1也是，求第n个丑数
No50，第一个只出现一次的字符,返回的是位置
No51，数组中的逆序对,归并排序！！！
No52,两个链表的第一个公共节点。
No53,在排序数组中查找数组，一个数字出现了多少次
No54,二叉搜索树中，第K小节点
No55-1，二叉树深度
No55-2,是不是平衡二叉树
No56-1,一个数组，一个出现一次，其他出现两次，求一次的。
No56-2,数组，一个出现一次，其他出现三次。求一次
No57-1，递增排序的数组，和target.找出一对和为target的数字
No57-2,正数s,给出连续正数序列，其和未s.所有的序列。序列最少有俩。
No58-1,翻转单词顺序
No58-2,左旋转字符串
No59-1给出数组和窗口大小，求滑动窗口的最大值。
No59-2,实现带有max函数的队列，出入队和max都是O(1)
No60,n个色子，点数和为s，s所有可能出现的值得概率
No61,扑克牌抽5个数，是不是顺子。大小王可以为任何;
No62,0到n-1,围一圈，从0开始，删除第m个数字。求最后的数字；
No63,数组，值为股票当时的价格，求最大利润
No65,不用加减乘除做加法
No66，构建乘积数组。
LeetCode的一些题目：
Two Sum:给定数组和target,返回两个元素之和为target的元素index;
Add Two Numbers：他是一个反转的链表，求真正链表代表数字的和的链表的翻转；
Longest Substring Without Repeating Characters：字符串最长的不重复子序列长度：
Longest Palindromic Substring：字符串最长的回文序列。
ZigZag Conversion：一个字符串，一个行数。然后字符竖折竖折来排序。然后一层一层的组合字符。
Reverse Integer：将整数值反转，如120变21，-21变-12，考虑值超过int溢出。
String to Integer (atoi)：将字符串转化为整数
Palindrome Number，一个数，正反来是否一样。负数不一样。
Integer to Roman，给定一个数，转化成罗马数字。
Longest Common Prefix；N个字符串，求这N个字符串最长公共前缀
3Sum,数组中，找3个和为0为三个数，每个数不能用两次。要考虑重复的问题。
3Sum Closest:一个数组，找出3个和最进阶target的。
Letter Combinations of a Phone Number，给定数字，求九宫格拼音下的所有组合。回溯
4Sum.数组中4个数之和为0，考虑重复的数.
19,删除倒数第k个节点
20、括号序列是否匹配：
21、合并两个有序链表，递归和非递归方式。
22、n对小括号的全正确排序：回溯
- 成对的翻转链表
26、有序数组，删除多余的重复数组，in-place删除，然后返回长度。
27、数组，删除指定的数字；
28、实现indexOf(String s1,String s2);
33、左移一部分的有序数组中，查询target。二分查找的经典题目
34、有序数组中，查询一个target第一次和最后一次出现的位置；二分查找的经典题目
35、将一个数插入到有序数组中，求位置
39：非重复数组，找出和为target的数组，一个不能用两次；回溯。
40，带有重复的数组，找出和未target的数组组合，一个不能用两次；回溯+组合
43，两字符串的数字，相乘，得到结果，输出字符串。
46,不重复数组的，所有全排列；回溯+排列
47，带有重复的数组，全排列；回溯+排列+去重
48：n x n矩阵，顺时针转动90度。
49，一群字符串，有些字符串字母组成一样，有的不一样，将一样的放一块；
50：计算power(x,n); x在正负100，n在正负 2^31;
54:一圈圈顺时针打印数组。
58：最后一个单词的长度。
59：给一个N,将1-N^2,整成上面外圈顺时针到里圈的矩阵。
60：1-N这n个数字的全排列，求第K小的；
61、翻转链表，链表右移K为，可以循环多移；
62、矩阵移动，mxn矩阵从左上角移动到右下角，只能横移和竖移，共有多少方法；
63、矩阵移动，从左上移动到右下：横竖移动，矩阵值为1的不能走；求多少种移动方式。
64、矩阵，从左上到右下，最短的路径和多少。
66、数组表示的数+1，然后返回之后的。
67、两个二进制字符串相加，得到的二进制字符串。
- Sqrt(x) 实现int sqrt(int x)；
73、MxN的数组，如果有一个为0，那么就让起其所有列和行都为0，求最后的数组；
74、mxn的矩阵，层序遍历就是有序的数组。在矩阵中搜索target;
75：一个只有2、1、0的数组，将0分到左边，2移动右边。
77:1-N，挑选K个进行排列；
78：求数组的所有子集合。
80：删除有序数组中过于多余的数字，最多每个出现两次。
81：翻转部分的有序数组，可能存在重复，搜索target;
82：删除有序链表，将重复的全都删了；
83：删除有序链表多余的节点，重复的保留一个。
86：链表，给定target，将比target小的节点移动到左边。大的和等于的移动到后面。其他相对位置不变。
88：将两个有序数组合到第一个数组中；
90：可能有重复元素的数组，求所有的组合。
91：将数字解码成A-Z;1-26;给出数字字符串，有几种解码方式：
92：逆转链表的m-n这部分；
93：给定一数字字符串，输出可能的IP地址列表。
94,二叉树中序遍历：
96：n个节点，共有多少种二叉搜索树。
98:判断一个树，是否是二叉搜索树。
100：判断两个树是否一致。
101：判断一个树是否对称。
102：二叉树层序遍历。
103,之字形打印二叉树
104:二叉树的深度:
105：前序和中序构成二叉树。
106：中序和后序构成二叉树
107：层序遍历：从底层到上层；
108: 将有序数组转化成二叉搜索树
109：将有序链表转化成二叉搜索树：
110:是否平衡二叉树：
111：叶节点到根节点的最短路径。
112：二叉树是否存在从根节点到叶节点的路径和为target:
113:找出所有路径和为target的序列
114：将二叉树往一边偏；
116：满二叉树，将为每个节点加上next，就是每层的右边那个。
117：二叉树，将为每个节点加上next，就是每层的右边那个。
125：字符串是否回文，只考虑数字和字母，大小写不论。
129：二叉树，从头结点到尾节点：拼接成数字，然后所有的加一块。
136,一个数组，一个出现一次，其他的出现两次，求一次的那个
137：数组，有人出现三次，有人出现一次，求一次的。
138：带有random指针的复杂链表的复制：
- 链表是否有环：
142：链表环入口节点
143：重排链表：1-2-3-4-5；先第一，再最后一个，先第二个，再倒二，就这样。
144：前序遍历二叉树：
- LRU Cache
147：对链表进行插入排序，
148：NlongN的时间排序链表。
150、逆波兰
151、单词逆序：
155、带有最小值函数的栈
160：两个链表的相交点
165：比较版本号大小。如10.2.2大于3.1.2；
167：有序数组，找出两数之和为target的索引。
168：数字转化为26进制的A-Z；
- Majority Element，超过一半的数字
171：26进制A-Z转化为十进制数字
172：Given an integer n, return the number of trailing zeroes in n!.
179：整数数组，求组合到一块的最大值。
189：数组左移K位
199：二叉树，从右边看到的节点数组。也就是每层最右边那个。
200：dfs求岛屿的个数。1表示陆地，0表示岛屿。
201：N-M数组的连续数，逐个&；求最后的结果。
209 : 最短的连续子序列之和大于等于target;
215：无序数组中找出最K大的数字：
216：1-9的数，选出n个，之和为k。求所有N的组合，一个数不能用两次
220：一个数组，是否存在不同的数i和j,使得nums[i]-nums[j]的绝对值最大是t,而i-j的绝对值最大是k;
221：矩阵，有0有1；找出最大的正方形，其里面数值都1；
222：给定一完全二叉树，求节点总个数。
223：以(A,B)和（C,D）为对角顶点，构建矩形，以EF，GH构建，求纵的矩形面积。
227：非负整数，有+-*/和空格数字的字符串组成的表达式，求表达式的值；
228：给出排序好的数组，没有重复，将连续的整成0->2的形式，求所有的连续范围段。
229，数组中超过n/3的次数的数。
230:BST二叉搜索树中，第K小的节点，递归和非递归方式
236：二叉树中，两个节点最近的公共祖先节点。
238：构建乘积数组
240：在矩阵中遍历，每行都增加，每列都增加。
241：数字和操作符，+-*,请随便加括号改变计算顺序，然后得出所有可能的结果。
260：数组，只有两个出线一次，其他的出现两次，求出现一次的那俩
264：第K个丑数，因子只有2,3,5的数；
274：if h of his/her N papers have at least h citations each, and the other N − h papers have no more than h citations each.
275：同上，也是求H。但这个数组是有序的；
287：N+1数，都是1-n之间，求重复的那个数。
300：最长递增序列，可以不连续。但是前面的index比后面的小
306：数字字符串，我们将字符串分割最少三个数字，然后Fn = Fn-1+Fn-2;
313：求第N个超级丑数，并且给出数组因子，只有只包括该数组因子的数才是超级丑数
318: 字符串数组，求两个没有公共字母的字符串长度乘积的最大值；
319：开关转换，刚开始有N的灯，最初都是灭的，第一轮，每一个都按一个。第二轮每二个按一个开关。第N轮之后，亮着的灯的个数。
322：给一堆零钱，可以重复使用，然后给整钱。将整钱换成零钱，求最小的零钱数，如果不能换，返回-1；
324：无序数组重排序：nums[0] < nums[1] > nums[2] < nums[3]....
328：链表重排序，将奇数位index,而不是奇数值的放到前面。偶数index的放后面：
331：将一个二叉树，他的空子节点记成#，给定一个字符串，问这个是不是前序遍历；
332 : 航班信息[from,to],一些列的这种数组信息，这人从JFK出发，求他的真正路线一次经过的城市；
334：数字数组，是否存在三个子序列，可以不连续，是递增的；
338：给定一num.求0-num这些数每个的二进制中1的个数。
347，TopK出现频率最高的数字，一个数组，每个数字可能出现多次，求最K多出现的那k个
343：给定一个整数，将他分成最小二段，和为这个整数，求这些段乘积的最大值。
357:n位数的数，求没有重复数字的总个数。11,121这种就不行。
面经中遇到的题：
1、数组的逆序数
2、LRU //hashMap加双向链表，双向链表有头尾节点，
3、最长回文序列 leetocde 5
4、矩阵中的最长递增路径，可以上下左右一起都走； leetcode329
5、判断一个二叉树是另一个二叉树的子树
6、归并排序的时间复杂度 // NlongN
7、求给出01矩阵中的最大正方形面积（全为1） lc221
8、求二叉树中距离最远的节点 leetcode543
9、判断字符串是否为合法IPV4地址 lc468
10、数组值为1-n，各出现一次，先加入x（x也是1-n的范围），找出x
11、给定n，计算15n，不用+*/
12、给定字符数组chars，将其右移n位
13、100层楼，只有两个鸡蛋，找出鸡蛋会在哪一层楼被摔碎
14、reverse linked list in a group of k
15、如何空间O(0)实现两个数的互换
16、IP地址的Regex
17、the longest path in a binary tree lc124
18、the largest consecutive sum in an array
19、LeetCode 41 Find mis sing positive
20、给一个小于一亿的中文数字字符串,转化成数字格式
21、一个数组,把所有的0都移动到末尾,还要保持顺序不乱 维持临界点j,如果当前遍历不是0，就和j互换
22、罗马数字转整数 leetcode13
23、二叉树的序列化和反序列化
24、输入一个数组，输出数组中满足条件的数字，条件为：数组中当前元素的值大于等于它前面所有的元素，小于等于它后面所有的元素。
25、给出一个数字，对数字的两位进行交换，只能交换一次，输出可能结果中的最小数字
26、输入一个字符串，字符串中字符全部为数字，在字符串中插入 '.' 使得结果为合法的ip地址，输出全部可能的结果
27、基数排序
28、链表是否为回文结构。不能用栈
29、最大不重复子串
30、复杂链表复制
31、长度为n的数组，元素大小是0~n-1,判断数组元素是否有重复的
32、list1/list2交替打印元素
33、36进制加法
34、合并区间
35、快排
36、生产者-消费者 模型
37、排序一个字符串时间要求O(n)
38、给一个有重复数字的数组，求集合{(a,b,c) | a+b+c=0}
39、两个栈实现队列
40、二叉树转化为双端链表
41、手写线程池
42、之字形打印二叉树
43、给定一个数组，调整该数组，使其满足堆的性质
44、给定n个单词，如果单词组成一致但是元素顺序不一致，该对单词为同位词，例如：abc,bca为同位词．求所有同位词的集合输出
45、链表，两个链表的公共点
46、二叉树的后续遍历非递归形式
47、买卖股票的最佳时机，只能一次买入和一次卖出
48、可以进行多次交易的结果，求赚取的最大利润
49、(A,B)(A,C)(B,D)(D,A)判断是否有循环引用，提示用拓扑排序
50、数组找是否存在和为M的两个数
51、KMP
52、实现一个阻塞队列（生产者消费者模型）
53、找出10000个数据中第 k 大的数
54、输入一个字符串，包含数字、加减乘除和括号，输出结果，编程
55、给定一个数x，要求使用k个数字求和可以得到x，数字从1-9中选择，不能重复。
56、输入一个正整数 N，返回 N 个 '(' 和 N 个 ')' 的所有可能情况
57、76.minimum-window-substring、30.substring-with-concatenation-of-all-words、42.trapping-rain-water，
58、求树的最左下节点
59、无序数组中第k大的数（quick select）
60、求旋转数组找最小值（二分）
61、判断二叉树是否镜像（递归）
62、给定一个矩阵，从左上角开始只能往下或者右走，求到达右下角的最小权值路径
63、字符串转Int，如果越界就返回0
64、lc400
65、单向链表实现加法
66、打家劫舍
67、收到礼物最大值
68、五张牌，其中大小鬼为癞子，牌面为 0，判断这五张牌是否能组成顺子
69、给定一个字符串打印所有的子串，要求不重复
70、自然数1-n,排一块组成的字符串，求第k位是什么。
71.如果a[0]<a[1],a[n-2]>a[n-1]，那么请找出任意一个点使得a[i-1]<a[i]>a[i+1] 要求logN
72、a[-1]和a[n+1]设为负无穷大，二分查找找到数组中的一个峰值。
73、如果有一组数字，按照“拿出第一个数在桌上并然后将下一个数放到队尾”一直操作直到数字全部放在桌子上，给你最后在桌子上的数字，请返回最开始数字的顺序。
74、有序数组找到第一个小于0的数和第一个大于0的数
75、合并两个排序数组并去重
76、两个排序数组找中位数
77、两个超大整数的字符串做减法运算。
78、1~10000中7出现的次数，如17算1个，77算2个。
79、给一个字符串数组，统计每一个字符串出现的次数，要求不能用set,map.时间复杂度O(n).
80、手撕最大堆，实现对应的push和pop操作
81、找出一个字符串中所有的回文子串
82、重复次数最多的最长连续子串（即找到重复次数最多的子串，若有多个，输出最长的）
83、长度为n的数组，有一个长度为k的滑动窗口，询问各个滑动窗口内的中位数。
84、区间最大最小值。两个长度为n的序列a,b,问有多少区间[l,r] 满足max(a[l,r])<min(b[l,r])。即a[l,r]的最大值小于b[l,r]的最小值
85、8皇后问题共有多少种解法
86、一个数字串删除指定个数的数字字符，剩下的组成一个最大的数
87、N个长度为K的有序链表合并，时间复杂度，空间复杂度
88、N个长度为K的有序数组合并，时间复杂度，空间复杂度
89、用一个栈去排序另一个栈
90、一个数组实现两个栈
91、一个n位数，现在可以删除其中任意k位，使得剩下的数最小
92、实现有符号大数链表加法，靠近头结点位置为高位
93、找出来数组中每个元素后边第一个比它大的值
94、完全二叉树的最大深度与节点个数
95、两个有序数组交集、并集
96、用二分法对一个数字开根号
97、一个无序有正有负数组，求乘积最大的三个数的乘积
98、实现链表，无序链表，对链表值奇偶分离并排序，空间复杂度O(1)
99、无序数组构建一棵二叉排序树
100、打印出根节点到叶子节点的最长路径
101、字符串形式自定义进制大数相加
102、LeetCode 1038
103、任意一个整型数组，判断是否可以将数组分为三个区间，每个区间中数值的和相同
104、二叉树逆时针打印最外层节点
105、无向图最短路径
106、输入一个矩阵，起始点和目标点，判断是否存在可达路径
