场景设计题 汇总 (一)
目录
TOPk系列的问题
10亿个数，找出最大的10个
有十万个单词，找出重复次数最高十个？
海量数据
10亿个数排序
10亿个数找中位数
设计一个发红包的API
分布式多个机器生成id，如何保证不重复?
扫码登录是如何实现的？
分布式集群中如何保证线程安全？
商家推荐
如何设计一个本地缓存？需要考虑哪些方面？
题目来自：
作者：代码界的小白
链接：开发岗位在面试中常见的10大场景设计题！_资源分享_牛客网
来源：牛客网
TOPk系列的问题
10亿个数，找出最大的10个
这道题的思路是，先拿10000个数建堆，然后一次添加剩余元素，如果大于堆顶的数（10000中最小的），将这个数替换堆顶，并调整结构使之仍然是一个最小堆，这样，遍历完后，堆中的10000个数就是所需的最大的10000个。
有十万个单词，找出重复次数最高十个？
集合13-TreeMap使用场景简析 - 简书
针对top k类问题，通常比较好的方案是【分治+trie树/hash+小顶堆】，即先将数据集按照hash方法分解成多个小数据集，然后使用trie树或者hash统计每个小数据集中的query词频，之后用小顶堆求出每个数据集中出频率最高的前K个数，最后在所有top K中求出最终的top K。
怎样从10亿查询词找出出现频率最高的10个_insistGoGo的博客-CSDN博客
海量数据
10亿个数排序
先划分成多个小文件，送进内存排序，然后再采用多路归并排序。
10亿个数找中位数
【海量数据处理】100亿个整数，内存足够，如何找到中位数？内存不足，如何找到中位数？ - vincently - 博客园
内存足够的情况： 可以使⽤用类似quick sort的思想进行，均摊复杂度为O(n)，算法思想如下：
• 随机选取一个元素，将比它小的元素放在它左边，比它大的元素放在右边
• 如果它恰好在中位数的位置，那么它就是中位数，可以直接返回
• 如果小于它的数超过一半，那么中位数一定在左半边，递归到左边处理
• 否则，中位数一定在右半边，根据左半边的元素个数计算出中位数是右半边的第几大，然后递归 到右半边处理
内存不足的情况：
无重复数字：bitmap方法
设计一个发红包的API
让你设计一个微信发红包的api，你会怎么设计，不能有人领到的红包里面没钱，红包数值精确到分。
设计发红包的API （ 微信红包的算法是怎样的？）_trigger333的博客-CSDN博客
分布式多个机器生成id，如何保证不重复?
分布式多个机器生成id，如何保证不重复?_trigger333的博客-CSDN博客
扫码登录是如何实现的？
扫码登录是如何实现的？_trigger333的博客-CSDN博客
分布式集群中如何保证线程安全？
分布式集群中如何保证线程安全？_trigger333的博客-CSDN博客
商家推荐
某网站/app首页每天会从10000个商家里面推荐50个商家置顶，每个商家有一个权值，你如何来推荐？第二天怎么更新推荐的商家？
我的想法：
根据权值建立小根堆，选取50个最大的商家来推荐。
使用推荐算法，根据过往的销售量，好评率等等，用户评分来确定，同时加入人工审核。
尽量分门别类的给每一块商品都有置顶的机会。因为可能存在某一类商品天然具有某种优势使得在你的推荐算法中评分比较高，结果推荐出来的商家都是卖一类商品的。
第二天不能根据第一天的算法，因为如果被推荐的50个相对于其他商家有很大的优势。
所以可以保留前一天置顶的50家中评分最高的25家，剩余25家从未被置顶的商家中选择。
如何设计一个本地缓存？需要考虑哪些方面？
缓存的设计 缓存的例子_trigger333的博客-CSDN博客
