一面

• 简单介绍下项目
• Redis中，字典这一数据结构的底层实现

• 我的理解：
  对Redis底层hash表的实现不熟悉，但是应该和golang中的map底层实现类似，一个buckets数组，然后对key进行hash取值得到一个长度为16位的hash值，根据低8位查找具体某个bucket（落入哈希表数组哪个索引位置处），根据高8位查找对应bucket中的具体key数据。有hash值冲突时采用链表法。

• 完整答案：
  Redis的字典使用哈希表作为底层实现，一个哈希表里可以用多个哈希表节点，而每个哈希表节点就保存了字典中的一个键值对。
  一个键值对放入哈希表时，会根据key值，计算一个hash值，然后根据hash值与哈希表大小掩码做与运算得到一个索引值，索引值决定元素放入哪个哈希桶中（落入哈希表数组哪个索引位置处）。
  在进行哈希计算的时候，不可避免会出现哈希冲突，出现哈希冲突的时候，Redis采用链式哈希解决冲突，也就是落入同一个桶中的元素，使用链表将这些冲突的元素链起来（dictEntry中的next指针）。

• Redis中跳表和压缩链表的实现原理（压缩链表的实现原理我不知道，就说是不是和golang中的map一样，为了避免内存对齐的消耗，采用key1、key2、key3…val1、val2、val3这样紧凑的结构，按照一定规则存储在内存中。以上内容我不确定）
• MySQL的叶子节点之间为什么采用双向链表的结构呢（方便范围查询）
• 3层B+树大约能存多少数据量

具体情况还跟数据的主键大小有关，主键类型所占字节数大，则Innodb的每一页16k所能存储的数据量就小，反之主键类型所占字节数小，所能存储的数据量就多，具体可参考：Innodb引擎中B+树一般有几层？能容纳多少数据量？

• Innod非叶节点中存储真实数据吗，真实数据存储在哪里呢

索引结构为B+树，它是排好序的数据结构。主键索引中，非叶子节点存储的是索引值，叶子结点存储的是行数据，普通索引中，叶子结点存储的是索引值和主键ID，同时叶子结点间是链表组成。

• MySQL中使用过乐观锁吗？什么场景下使用？有哪些方式实现乐观锁？分别是怎么实现的？

读多写少的场景下使用到。实现方式：版本比较/CAS比较并交换，或者新增表比较版本/修改时间戳

• 了解堆（完全二叉树）这种数据结构吗？大顶堆&小顶堆 的过程及原理？
• 建堆及调整堆的时间复杂度

• 建堆：O(N)，按我的理解最坏情况下，假如是一个递增序列，那么会形成一条链表，那么此时的时间复杂度就是O(N)。
  因为初始化建堆的过程，是一个杂乱无序的数组构成的完全二叉树，所以需要从倒数第一个非叶节点开始与它的叶子节点进行比较，然后移动。不是说每一层选一个根节点进行比较就可以了，是每一层的所有节点都要跟它的左右节点进行比较。这也就导致了它的时间复杂度不是logN，而是O(N)。
• 调整堆：O(NlogN)，对于重建堆的过程，因为是从最上面的根节点开始进行左右节点的比较，选择一个 较大（大顶堆）/ 较小（小顶堆） 的孩子节点进行交换。而因为只破坏了一层的有序性，另一边子树的有序性没有遭到破坏。所以，另一边子树不需要进行比较，所以，每一层只需要比较一次，一共log层，需要比较logn次。而一共会有 n-1 个这样的元素会被放到根节点进行这样的操作，近似得到 O(NlogN)。

• 在项目中，消息队列的应用场景及其作用

削峰填谷、异步化（站内信告警，避免告警逻辑阻塞正常业务逻辑返回）、解耦…

• 缓存穿透、缓存雪崩的产生原因及其解决方案
• 场景题：幂等操作，多个写请求，怎么避免重复写相同记录到db

利用MySQL的唯一索引，或者向Redis中写入标记值。

• Linux中的grep、sed、awk命令。使用Linux命令找出日志文件中访问量最大的5条url

cat *.log | awk -F" " ‘{ print $2 }’ | sort | uniq -c | sort -nrk 1 -t’ ’ | awk -F" " ‘{ print $2 }’ | head -10
参考：使用Linux命令找出日志文件中访问量最大的10个IP

• Nginx 499错误原因及解决，我不了解所以没回答出来

在nginx中 499状态码的定义是 client has closed connection，也就是客户端断开了连接。所以显然，客户端端主动关闭请求或者客户端网络断掉时，于是nginx就记录了499状态，并且断开了和后面服务端的连接（这样可能导致服务端返回数据时，因为连接断开而报错）
参考：nginx 499错误原因及解决

• git revert 和 git reset的区别

区别：
reset是彻底回退到指定的commit版本，该commit之后的所有commit都将被清除；revert仅是撤销指定commit的修改，并不影响后续的commit。
reset执行后不会产生记录，revert执行后会产生记录。

• 前端请求后端接口时，如何处理跨域问题？

我说是父子域名有继承关系，对于父域名下的所有子域名，浏览器都会自动帮其提交cookie。或者前端不使用cookie传递信息，而使用localstorage本地存储用户身份认证信息。
而面试官提示说是通过中间层的代理服务器进行请求的转发。。。我对此不是很了解

• 了解Nginx吗，我说没研究过，只知道他负载均衡的几种方式：轮询、随机、权重…
• 场景题：问答帖子的场景下，
  • 用户的问题和回复较多，如何设计分表规则。

  我说根据提问者的 user_id 去对N取模来分表，比如 N=64 时，user_id%64得到的值就是对应序号的表 …

  • 那么有一个页面，想要展示最新的20条提问帖子，那么如何得到数据？

  我说根据帖子发布的时间戳来构建一个大顶堆，大顶堆大小为20，最后扫描这64张表来填充大顶堆即可~

• 算法题：利用二分法，查找包含重复数字的有序数组，返回出现的第一个target值的下标（普通二分法查找到target值对应下标mid之后，再将 mid– 依次向前查找到第一个与target值相等的数的下标）

二面

感觉面试官并不是很想招人，相比一面的面试官体验感极差，就问了一个epoll的问题，然后就算法题，然后做出来说边界处理写的不优雅，我说我继续优化下，没给机会直接说抱歉…挂了。总之就感觉很憋屈~

• 项目介绍
• epoll多路复用介绍
• 算法题：例如字符串：IOIIOIIIOIIIIOI……，并给定长度n，问长度为n的字符串有多少个字符O出现？

package mainimport ("fmt"
)// 这是我面试结束后优化的，无需处理边界条件
func GetOCnt(n int) int {res := 0iIndex, oIndex, allCnt := 1, 1, 1for ; allCnt < n; allCnt += iIndex + oIndex {iIndex++res++}return res
}/*
// 这是我第一遍写的代码，面试官说n<=2时的边界处理不行，不优雅，然后给我挂了...
func GetOCnt(n int) int {if n <= 1 {return 0} else if n == 2 {return 1}res := 0iIndex, oIndex, allCnt := 1, 1, 0for ; allCnt < n; allCnt += iIndex + oIndex {iIndex++res++}return res
}
*/func main() {oCnt := GetOCnt(3)fmt.Println("res = ", oCnt)
}