头条三面凉经

由于实习拿了offer没去，直接三面，面试官在家里面试的我，面试时间50分钟，然后凉了。其实觉得问的都挺简单，下面给出了我的一些答案，可能答案有问题不自知，希望有大佬指点一下。

快速排序和归并排序描述一下，优缺点（描述）

快速排序：先选定一个基准元素，按照这个基准元素将数组划分，再在被划分的数组上重复上过程，最后可以得到排序结果。

归并排序：将数组不断细分成最小的单位，然后每个单位分别排序，排序完以后合并，重复这个过程就得到了排序结果

优缺点：归并排序稳定且最高最低时间复杂度都是nlogn，但是占用额外空间；不稳定，最高时间复杂度n2，最低时间复杂度nlgn，不占用额外空间

加问快速排序很多重复数字如何优化

返回基准元素位置时返回基准元素的最左和最有索引，减少排序次数。

希尔排序知道吗？为什么这么操作

改良的插入排序。插入排序在数组基本有序的时候可大大降低时间复杂度，希尔排序通过将数组分块后对每块数组进行插入排序，每次排序完成，块数减少一倍，数组也相对变得有序，知道最后对整个数组进行插入排序，则排序完成。

Hashmap描述。多线程会发生什么问题

jdk1.7时由数组和链表组成；jdk1.8时将链表改良为链表+红黑树

多线程put操作可能发生死循环或者元素丢失

加问死循环发生原因：

多个线程执行put操作时同时触发了rehash方法，可能会生成环形链

加问环形链形成过程（视频面不能画图，表示不好讲，面试官还是要求讲，就随便讲了一下，这里肯定说的很不清楚）

红黑树描述

1. 节点是红色或者黑色的
2. 红色节点的子节点必须是黑色的
3. 根节点为黑色
4. 叶子节点（Nil节点）为黑色的
5. 根节点到叶子节点的路径上的黑色节点一样多

加问为什么要使用不同颜色的点

红黑树是平衡二叉树的变形，由于平衡二叉树插入删除操作复杂特别是如果插入有序的数字时，二红黑树只要满足节点的颜色要求，在插入删除过程中满足红黑树定义要求，就能满足二叉树的相对平衡。

Springmvc的流程、handler如何找到要处理的类（流程简单讲了一下，问知道前端处理器的那个servlet叫什么吗？答：是dispatcherServlet吗，看面试官反应以为自己错了，后来查了一下好像没错。handler没答出来）

一些简单的项目问题

Post和get的区别

1. Post用来给服务器传送数据，get用来从服务端获取数据
2. Get提交直接将请求信息放在url地址上会存在安全问题
3. Get 的长度一般限制在2kb左右

逻辑题：一个岛上的居民会戴红白帽子两种帽子，每个人只能看到别人带什么帽子，不能知道自己戴什么帽子，并且互相之间不能交流。如果某人知道自己戴红帽子，当晚必须离开岛。有一天岛外来了一个人，说：“你们之中至少有一个人戴了红帽子”，请问之后的几天会发生什么事情?（说出了答案且给出分析过程。让我证明这个结论，不知道是个什么意思）

如果由n个人戴了红帽子，那么就在第n天的时候这些人都离开了

算法题：给出一个数字矩阵，寻找一条最长上升路径，每个位置只能向上下左右四个位置移动。 （没太过脑子直接写的代码实现，复杂度太高，面试官要求优化，我说了一下思路，然后就结束了）

一分钟以后hr告诉我面试结果不满意，能马上告知结果这点还是很佩服的。