热腾腾的头条后端三面面经

紧张了一天等来了三面，人生中第一次三面，原谅我太菜。祝自己好运~

• 项目介绍 分布式锁
• 分布式锁除了 redis 还有其他实现吗，我说有数据库和 zookeeper，说了数据库的实现，zk 不了解
• 团队之间如何分工
• 题目一：链表奇数位升序，偶数位降序，如何改为有序链表
  • 遍历一次将奇数和偶数分别存储到两个列表中，然后合并
  • 如何不用额外存储空间：先遍历一遍将单向链表改成双向链表，然后分别从两头开始遍历
  • 评论区同学说可以把偶数节点连起来然后反转最后再合并两个链表，俺当时也没想出什么好做法，总之面试官的意思是想要 O(1)的空间复杂度😂
• 题目二：百万的数据，找出最大的 100 个
  • 用最小堆
  • 如果这 100 万个数据都是 0-100 之间的有什么其他办法，用一个大小为 100 的哈希结构存储数据
  • 如果数据是 100 亿，大到内存存不下怎么办，我说就分次读取
• redis 有哪些数据结构
• redis 的有序列表怎么实现
• 跳表有什么优势，比如和二叉树比较
• mysql 用的是什么数据结构存储
• b+ 数是什么样的，b 数和 b+ 数的区别，为什么用 b+ 不用 b 数
• 题目三：有一个函数 random(5) 产生随机数 0-5，如何用它来实现 random(7)
  • 产生随机数的概率得是均匀的
  • 更新一下， 好多人回复了这道题的做法，我也不知道对错，这里是leetcode里random 7实现random 10 官方题解
• 场景设计题：抖音点赞，QPS 是百万级，如何设计
  • 用 redis 做缓存
  • 数据最终写到哪：数据库
  • 怎么写：定期写入
  • 有没有不一致问题：机器出问题数据丢了就可能不一致吧
  • 怎么解决：redis 的持久存储 rdb 和 aof
  • 磁盘出问题怎么办，rdb 和 aof 都有问题：redis 集群，用多台 redis 保证高可用
  • redis 集群怎么设计的：一台写其他读

上面我给出的回答可能不是对的，只是我当时所想到的，并不完整。大家有什么想法可以在评论区指正。