shopee7月20日一面面经

面了一个小时，内容很多，也是我面过最有难度的一场面试

1 问你几道数据结构，说一下8种排序算法，稳定的有哪几种，空间复杂度O(1）的哪几种

2 讲讲归并排序和快排的思路，具体讲讲merge操作和partition操作

3 讲讲基数排序

创建一个长度为10的二维数组，遍历无序数组，将个位数为0 - 9的放在二维数组的第0-9个位置，然后按顺序将元素取出，再将十位数为0 - 9的放在二维数组的第0-9个位置，然后再取出，以此类推最后会得到一个有序数组

4 讲讲二叉搜索树的特点，以及弊端，怎么改进？

二叉搜索树可能退化成链表，用 AVL树

5 讲讲AVL树是怎么保持平衡的？

左单旋右单旋先左后右双旋转先右后左双旋转

6 讲讲红黑树

7 红黑树和AVL树的区别

红黑树与AVL树都是平衡树，但是AVL是完全平衡的(平衡就是值树中任意节点的左子树和右子树高度差不超过1

红黑树效率更高，因为AVL为了保证其完全平衡，插入和删除的时候在最坏的情况下要旋转logN次，而红黑树插入和删除的旋转次数要比AVL少。

8 了解红黑树的插入删除操作吗?(不知道）

9 问你一道算法题，只说思路

100层楼，球可能在某一层摔坏，有两个球，最坏情况下几次测试可以找到该楼层？

10 手写sql，找出a表存在，b表不存在的的数据

select distinct a.id from a where a.id not in (select id from b)

不要用子查询，换种方式实现

select a.id from a left join b on a.id =b.id where b.id is null

ok，你用了左连接，介绍一下，还有什么连接方式，分别介绍一下

11 HashMap迭代的时候删除会出现什么问题

基本上java集合类（包括list和map）在遍历时没用迭代器进行删除了都会报ConcurrentModificationException错误，这是一种fast-fail的机制，初衷是为了检测bug。

通俗一点来说，这种机制就是为了防止高并发的情况下，多个线程同时修改map或者list的元素导致的数据不一致，这是只要判断当前modCount != expectedModCount即可以知道有其他线程修改了集合。

12 你说到了快速失败，知道安全失败吗，讲讲

13 解释HashMap的容量为什么是2的n次幂？

14 讲一下五层协议，应用层传输层有什么协议？

15 TCP UDP区别

16 讲讲TCP拥塞控制算法，解释一下慢开始，发送窗口具体是什么？

开始发送窗口cwnd=1（即一个最大报文段的长度MSS）

17 讲一下滑动窗口协议

18 Http和Https的区别,思考一下怎么降低https连接开销

19 讲讲进程线程协程

20 进程通信方式线程同步方式

21 好，你提到了ReentrantLock锁，知不知道AQS，讲一下

AQS是很多线程同步工具的实现类，全称是AbstractQueueSynchronizor，抽象同步队列，虽然说是一个抽象类，但是实际上他实现了所有的方法，我们只需要重写获取和释放两个方法，就能达到不同的效果。AQS维护一个队列，这个队列中存放着线程，还维护一个资源，一般来说是一个计数器，来计数有多少线程此时在使用。新添加的元素放到队尾，队头的线程获取资源，后面的线程等待队头释放自己才能获取，以此循环实现一个队列的概念。非公平锁就是在插入队尾时可以先看一下队头有没有使用，没有使用则直接抢占。

22 知道什么索引引擎，讲讲?

23 对于count函数来说，MyISAM索引和InnoDB那个快？（不会，蒙了个InnoDB，面试官问为什么，不会，gg）

24 讲讲b+树
25讲讲悲观锁乐观锁，你说到了乐观锁通过加版本号或者时间戳来控制，那那种方式更好一点（不会，蒙了个版本号，面试官问为什么，不会，gg，以后不会就是不会，别再瞎蒙了）

26 为什么不建议用select *？

27 redis5种数据结构 8种底层数据结构，讲讲跳表，怎么实现插入查找的，和红黑树比较怎么样

28 好，写一道算法题，先序遍历二叉树，递归，非递归，把 TreeNode类补充上，把非递归方法改成中序遍历

29 具体场景题电脑版微信二维码登录原理

30 最后反问我还有哪些值得改进的地方

面试官说，没什么大问题，就是一紧张就喜欢摸头发，我一直在看你摸头发（笑）

具体什么时候能知道结果

后续会有hr通知你

总体来说面试体验很好，面试官会主动引导你，但是内容太多，节奏太快，面到最后已经不想思考了。。。可能这就是压力面吧。