shopee后端开发面经

笔试：8月19日 14:30 - 16:30 15题选择题+3题编程题

=================== 一面 ===================

8月24日 11：30 - 12：30

面试官是个和蔼的大叔，每次回答完都会“嗯”一声。。就算答得菜也会点头，我询问的时候也会很积极的回答

1. 自我介绍

2. 有什么主流排序，快排的复杂度，什么情况下复杂度为O(n^2)，如何改善（这里我答了用随机轴点，然后面试官问还有呢，我就答不上来了；正确答案：给每一个元素一个编号，根据这个编号就可以判断是否相同的内容的元素发生了位置互换）

3. 哈希表散列算法，哈希冲突的解决方式。Java里面的HashMap用的是哪种哈希冲突解决方式？（链表，超过8个数字后变为红黑树）为什么用红黑树而不是平衡二叉树？为什么是两倍扩容而不是三倍扩容？（这个扩容机制答不上来...正确答案：哈希表的散列算法是利用对象的hashcode与哈希表的长度-1进行与运算（&）的，起到了与模运算（%）相同的作用，为了保证每一个空间都被利用到，减少冲突，必须是以1111...1这样的二进制相与，所以表的长度必须是二的整数次方个数)

4. MySQL里的聚簇索引和非聚簇索引的区别，最左匹配原则，主键索引，非主键索引，B+树，为什么不用二叉树？

5. 听说过MySQL的注入攻击吗？（听过，但原理完全不懂...查了一下博客，大概是在参数的部分恶意添加了MySQL指令，越过了本应有的权限，对数据库的隐私和安全造成了破坏)

6. redis里的zset和list有什么应用场景， zset用到了什么数据结构？zset的zrange和zscore的查询时间复杂度（完全没用过这两个指令，凉。具体要去看跳表的查询原理）

7. 介绍一下协程？（协程这里是看面经的，没有具体看博客，从面试官的反应来看好像说错了某些地方）进程的堆内存和栈内存是否独立的？进程里面有什么内容（凉，基本答不上，只能扯一点JVM的内存机制）

8. 虚拟内存和物理内存有什么区别，如何管理虚拟内存（段、页），虚拟内存用到了什么介质（外存，磁盘），用到了什么数据结构。答的不好，语言组织不够流畅

9. 三次握手以后，如何给字节流的包设置编号？握手以后服务器会发送什么数据给客户端（这里真的心凉啊..我完全不懂，乱答了）

10. 长连接和短连接有什么区别？HTTP的长连接和TCP的长连接有什么区别？(一脸懵逼啊，从来就没听说过这两个的长连接。查了一下博客，HTTP的长连接会调用TCP的长连接）

11. session和cookie的区别，存放在哪里，如何进行数据交互，session的数据如何保存到cookie里。这里答得不好，支支吾吾的，逻辑也不清晰

12. 了解URL的RESTFUL风格吗？他的特点在哪里？我回答的是参数通过斜杠号进行分离，成为URL的一部分。面试官问只有这个特点吗？我就说通过restful风格，程序设计的URL架构模式也不同....（这里也是只能乱说一通）

13. topK问题（我只回答了用堆的方法），时间复杂度（这里由于太紧张，把o(nlogk)答错成o(nlogn)...面试官一直问我有必要把所有的数据放到堆里面吗？我说没有必要，愣了一下才意识到说错了）

14. 最小栈如何实现（用两个栈，一个存放数据，另一个存放最小值）

15. 算法题：求100以内的孪生素数，20分钟内写出代码。问了一下算法复杂度（这里素数判断我用了普通的迭代法，看面试官的表现好像可以做的更好）