字节上海tiktok面经

人在腾讯，20届海外水硕


字节tiktok
一面
- coding: 对于一个数组，仅用一次遍历，等概率地随机出一个元素
  - 对于每一个元素，从全局看，他们被选择的概率都应该是 1/n；对于第 i 个元素，以 1/i 的概率选择，计算其往后一直被保留的概率如下；1/i 代表当前被选择，其后代表在之后的行动中其他元素不被选择的概率
  - followup：随机出 k 个元素：以 k/i 的概率选择它，并以 1/k 的概率从已有的选择中随机一个去掉；往后，它唯一会被淘汰的场景只有当选择了新的元素，并从这些已有的选择中等概率地选择到了它，也就是 1 - k/i+1 * 1/k
  - 解题可以参考 https://labuladong.gitee.io/algo/4/30/117/

二面
- 系统设计：主播开播，如何把这个消息推送给他的千万级 follower
  - 数据仓库，消息队列的设计
  - 推送之后，主播已经下播，怎么处理
  - 怎么保证消息推送或被消费
  - 如何保证消息不重复


三面
- DB 迁移流程
- coding：写一个服务的大致框架
- 其他记不清了

过了吗，涨幅多少