Top K问题
10亿个数据中找出最大的10000个
最小堆法
- 先拿10000个数建堆
- 然后逐个添加剩余元素
- 如果大于堆顶的数（10000中最小的），将这个数替换堆顶，并调整结构使之仍然是一个最小堆
- 遍历完后，堆中的10000个数就是所需的最大的10000个。
- 复杂度分析：时间复杂度是O（mlogm），算法的时间复杂度为O（nmlogm）（n为10亿，m为10000）。
如果内存受限：可以直接在内存总使用Hash方法将数据划分成n个partition，每个partition交给一个线程处理，线程的处理逻辑可以采用最小堆，最后一个线程将结果归并。
有几台机器存储着几亿淘宝搜索日志，你只有一台 2g 的电脑，怎么选出搜索热度最高的十个？
【分治+trie树/hash+小顶堆】
先将数据集按照hash方法分解成n个小数据集，然后使用trie树或者hash统计每个小数据集中的query词频，之后用小顶堆求出每个数据集中出频率最高的前K个数，最后在所有top K中求出最终的top K。
海量数据排序、压缩问题
重要方法——位图法 Bitmap
位图的基本概念：用一个位（bit）来标记某个数据的存放状态。例如，有{2, 4, 5, 6, 67, 5}这么几个整数，我维护一个 00…0000（共67位）的0/1字符串，1表示该索引（=数据值）处存在数，0则表示不存在。
应用：位图法可以用于海量数据排序，海量数据去重，海量数据压缩
优点：针对于稠密的数据集可以很好体现出位图法的优势，内存消耗少，速度较快
缺点：不适用于稀疏数据集，比如我们有一个长度为10的序列，最大值为20亿，则构造位串的内存消耗将相当大250M，而实际却只需要40个字节，此外位图法还存在可读性差等缺点。
非重复排序
假设我们有一个不重复的整型序列{n1， n2， … ,nn}，假设最大值为nmax，则我们可以维护一个长度为nmax的位串。
主要过程：
- 第一遍 遍历整个序列，将出现的数字在位串（java中可以用数组实现）中对应的位置置为1；
- 第二遍 遍历位图，依次输出值为1的位对应的数字，这些1所在的位串中的位置的索引代表序列数据，1出现的先后位置则代表序列的大小关系。
重复排序
同上，只是子串中不只存在0/1，实际数量为多少，则值为多少.输出时，值为多少则输出多少遍
数据压缩
前提：数据中存在大量的冗余值
基本思路就是使用某个子串存储原数据中的海量值
如何用redis存储统计1亿用户一年的登陆情况，并快速检索任意时间窗口内的活跃用户数量
redis单独对bitmap提供了一套命令。可以对任意一位进行设置和读取。所以可以在位图中使用1表示活跃。
bitmap的核心命令：
SETBIT：设置某位为1
语法：SETBIT key offset value
GETBIT：获取某位的值
语法：GETBIT key offset
bitmap的其他命令还有bitcount，bitpos，bitop等命令。都是对位的操作。
获取某一天id为88000的用户是否活跃：getbit 2020-01-01 88000 (时间复杂度为O(1))
统计某一天的所有的活跃用户数：bitcount 2019-01-01 (时间复杂度为O(N))
-统计某一段时间内的活跃用户数，需要用到bitop命令。这个命令提供四种位运算，AND(与)，(OR)或，XOR(亦或)，NOT(非)。
以下例子求出了2019-01-01到2019-01-05这段时间内的活跃用户数。
bitop or result 2019-01-01 2019-01-02 2019-01-03 2019-01-04 2019-01-05 (时间复杂度为O(N))
资源 vs 请求问题
如果一个外卖配送单子要发布，现在有200个骑手都想要接这一单，如何保证只有一个骑手接到单子？
单机情况
- 采用volatile关键字修饰该订单采用CAS操作对其进行乐观锁操作。volatile保证可见性，CAS保证原子性
集群：
- 采用redis分布式锁加锁。
- 消息队列 实现幂等接口
多个微信用户抢红包
类似于秒杀系统
- 数据库加乐观锁、悲观锁
- 在逻辑处理界面加分布式锁
- 消息队列
1000个任务分给10个人做
- 全局队列，每一个人都从一个队列中取
- 分成10个队列对应每一个人
设计类问题
你如何设计一个消息队列?
首先这个 mq 得支持可伸缩性吧
就是需要的时候快速扩容，就可以增加吞吐量和容量，那怎么搞？设计个分布式的系统呗，参照一下 kafka 的设计理念，broker -> topic -> partition，每个 partition 放一个机器，就存一部分数据。如果现在资源不够了，简单啊，给 topic 增加 partition，然后做数据迁移，增加机器，不就可以存放更多数据，提供更高的吞吐量了？
其次你得考虑一下这个 mq 的数据要不要落地磁盘吧？
那肯定要了，落磁盘才能保证别进程挂了数据就丢了。那落磁盘的时候怎么落啊？顺序写，这样就没有磁盘随机读写的寻址开销，磁盘顺序读写的性能是很高的，这就是 kafka 的思路。
其次你考虑一下你的 mq 的可用性啊？
这个事儿，具体参考之前可用性那个环节讲解的 kafka 的高可用保障机制。多副本 -> leader & follower -> broker 挂了重新选举 leader 即可对外服务。
能不能支持数据 0 丢失啊？
可以的，参考我们之前说的那个 kafka 数据零丢失方案。
你如何设计一个缓存系统?
1.数据结构
首要考虑的就是数据该如何存储，用什么数据结构存储，最简单的就直接用Map来存储数据；或者复杂的如redis一样提供了多种数据类型哈希，列表，集合，有序集合等
2.对象上限
因为是本地缓存，内存有上限，所以一般都会指定缓存对象的数量比如1024，当达到某个上限后需要有某种策略去删除多余的数据；
3.清除策略
上面说到当达到对象上限之后需要有清除策略，常见的比如有LRU(最近最少使用)、FIFO(先进先出)、LFU(最近最不常用)；
4.过期时间
除了使用清除策略，一般本地缓存也会有一个过期时间设置，比如redis可以给每个key设置一个过期时间，这样当达到过期时间之后直接删除，采用清除策略+过期时间双重保证；
5.线程安全
像redis是直接使用单线程处理，所以就不存在线程安全问题；而我们现在提供的本地缓存往往是可以多个线程同时访问的，所以线程安全是不容忽视的问题；并且线程安全问题是不应该抛给使用者去保证；
6.简明的接口
提供常用的get，put，remove，clear，getSize方法即可；
7.是否持久化
这个不是必须的，是否需要将缓存数据持久化看需求
其他
怎么判别淘宝刷单？怎么检验手段效果？
商家角度：
营业额远高于历史平均数据
营业额远高于行业平均数据
下单的用户很多均为存在异常行为被监控的账户
顾客角度（账号维度）：判断是否存在异常行为
单次交易行为：是否精准搜索、货比三家、页面停留时间等
近期购物成功率：远高于历史时期平均购物成功率
是否可能为垫付：短时间支付宝账户内收到与下单金额相同的金额
下单的店铺很多均为存在异常行为被监控的账户
商家与顾客：
存在相近或者共同的网络环境：如ip、wifi等
如何把一个文件快速下发到 100w 个服务器
采用p2p网络形式，比如树状形式，网状形式，单个节点既可以从其他节点接收服务又可以向其他节点提供服务。广度优先遍历
如何实现两个线程交替打印
static volatile Integer count = 1;
// volatile + synchronized
public static void solution1(){
new Thread(() -> {
for (int i = 0; i < 10; ) {
while (count % 3 != 1) {
}
synchronized (count) {
if (count % 3 == 1) {
System.out.print("A");
count++;
i++;
}
}
}
}, "A").start();
new Thread(()->{
for (int i = 0; i < 10;) {
while (count % 3 != 2){
}
synchronized (count){
if (count % 3 == 2){
System.out.print("B");
count++;
i++;
}
}
}
},"B").start();
new Thread(()->{
for (int i = 0; i < 10;) {
while (count % 3 != 0){
}
synchronized (count){
if (count % 3 == 0){
System.out.print("C");
count++;
i++;
}
}
}
},"C").start();
}
