Interview

2022 年初 | 后端开发两年经验社招面经 字节 一面 coding: 对于一个数组，仅用一次遍历，等概率地随机出一个元素（对于每一个元素，从全局看，他们被选择的概率都应该是 1/n） 对于第 i 个元素，它在第 i 轮被选中的概率是 1/i 往后，只要选择了新的元素，它就会被淘汰；以第 i+1 轮为例，它被淘汰的概率是 1/(i+1)，那么反过来它被留下的概率就是 1 - 1/(i+1) 最终每一个元素被选择的概率如下，第一个 1/i 代表它在第 i 次被选中，其他数代表它在后续的每一轮被留下 followup：等概率地随机出 k 个元素 对于第 i 个元素，它在第 i 轮被选中的概率是 k/i 往后，它唯一会被淘汰的场景是：选择了新的元素，同时从已有的选择中，等概率地选择到了它；以第 i+1 轮为例，它被淘汰的概率是 k/(i+1) * 1/k = 1/(i+1)，那么反过来它被留下的概率就是 1 - k/(i+1) * 1/k = 1 - 1/(i+1) 最终每一个元素被选择的概率如下，第一个 k/i 代表它在第 i 次被选中，其他数代表它在后续的每一轮被留下 coding: 实现 Fisher–Yates Suffle void shuffle(vector<int> v) { int n = v.size(); for (int i = n - 1; i >= 1; --i) { int j = rand() % (i + 1); swap(v[i], v[j]); } } 二面 system design：主播开播，如何把这个消息推送给他的千万级 follower 设计数据仓库（数据库也可以） 消息队列 followup：推送之后，主播已经下播，怎么处理 followup：怎么保证消息推送或被消费 followup：如何保证消息不重复 三面 DB 迁移流程 ...