美团一面03.21

a 2.761.求最小连续1子串，暴力ac2.数学题，分段函数。k/2作为界限，以k的倍数进行票数+1递增。ac3.估计要回溯+哈希，来不及做 04.对结构体排序完+暴力，只能过 0.76。

1.自我介绍2.视频续播怎么实现的，5S的精度还可以再提高吗，怎么实现3.Redis持久化怎么做的4.乐观锁，悲观锁(直接用synchronized会有什么问题？)5.缺页中断（问缺几页换几页？没明白啥意思，答的替换算法FIOFO，LRU），6.LFU了解不，和LRU区别，自己设计LFU怎么实现（数据机构）7.notify,notifyAll的区别，notify是随机唤醒还是FIFO，为什么8.Java并发安全队列有哪些9.spring怎么解决循环依赖10.普通工厂和抽象工厂区别11.什么是观察者模式12.短链接是怎么实现的（没看过，答用hash做映射，说是hash用冲突不行，提示用自增id）13.手撕（回溯，中等题）14.科研做了啥，自己挑个难点说15.提问环节

第一题 k路字符串 优先级队列第二题 裸的拓扑排序，注意判断是否有环第三题 一开始直接写的最长上升子序列（严格），WA，于是推断山的高度必须是整数，于是对nums[i]-i求最长上升子序列（不严格）AC第四题 样例过，提交之后过0%样例，没看出来哪里错了，贴一下代码 #include using namespace std;int main() {    //数据范围来说，至少是需要n方或者更好的算法    //注意读题，首先不是严格大于，其次需要注意交换需要前提条件，即a[i] > x，这意味着交换过程中,x的数值是原来越大的，和x交换的值的门槛也是越来越大,隐含的条件就是如果小于x的数字没有有序，那么久没办法完成操作了    //手玩一下：    //81 324 218 413 324 x = 18 如果与i>=1的位置交换，剩下的18没人可以换走，直接不可行    //18 324 218 413 324 x = 81 同理，如果与i >= 2的位置交换，剩下的81没有可以换走，直接不可行    //18 81 218 413 324 x = 324 我们选择将413与324交换    //18 81 218 324 324     //再来领悟一下样例    //0 2 3 5 4 x = 1 当前发现后面有一个4在捣乱，我们要想办法把它调整下来，但是要调整，就说明当前x = 1需要换上去到某一个位置，也就只能是和2换，这一步是固定的    //0 1 3 5 4 x = 2 同样的，捣乱的4还没有解决，所以继续要调整，当前x = 2只能换在begin，故而    //0 1 2 5 4 x = 3 begin变成了5的下标    //0 1 2 3 4 x = 5 此时发现已经解决//再来领悟一下输出-1的样例    //11 9 x = 10 当前begin = 0 end = 1,但是注意到nums[end] < x，最终不可以被移动，所以已经寄了    //以上过程说明：对于小于x的内容，如果是已经有序地位于开头，那么就已经不可行了    //对于大于x的无序的内容，如果存在多个，比如10 20 30 40 6 4 x= 3，其中6和4都是乱序的，但似乎此时并不需要决定和其中的谁交换，只能从begin开始交换    //3 20 30 40 6 4 x = 10    //3 10 30 40 6 4 x = 20    //3 10 20 40 6 4 x = 30    //3 10 20 30 6 4 x = 40 爆炸    //至此大胆提出假设：先处理得到其中单增的区间    //0 2 3 5 4 x = 1    //其中比x小的部分已经确保落在该有的位置上了    //0 [2 3 5] [4] x = 1 那么我们会把{[2, 3, 5] x = 1}变化为{[1 2 3] x = 5}，即相当于原来有序的空间中最大的没了，最小的变成原有x。花费是有序空间大小    //然后x变成了原有空间中最大的那个，然后继续这样扫描//再来手玩一下：    //4 5 6 7 8 9 10 3 x = 1     //{[4 5 6 7 8 9 10] x = 1}->{[1 4 5 6 7 8 9] x = 10} 由于次大的9还是大于无序的3，所以没办法    //总结思路：线性扫描，找到从开始到现在最长的有序集（其中小于x的部分不统计长度）int t;    cin>>t;    while(t--)    {        int n, x;        cin>>n>>x;        vector nums(n);        for (int i = 0; i < n; ++i) cin>>nums[i];        int begin = 0, end = 0, costBegin = -1;        int ans = 0;        bool flag = true;        while(begin < n)        {            //end begin costBegin x ans            while(end + 1 < n && nums[end + 1] >= nums[end])//扫描到end，并更新end            {                if (costBegin == -1 && nums[end] > x) costBegin = end;                ++end;            }            // cout<<"begin = "<<<", end = "<<<", costBegin = "<<<'\n';            //从begin 到 end 递增，且从costBegin开始大于x            if (end == n - 1) break;            if (begin != end)            {                if (nums[end + 1] < nums[end - 1]) {flag = false; break;}//没办法调整                ans += (end - costBegin + 1);                x = nums[end];                end = begin = end + 2;                costBegin = -1;            }            else            {                if (nums[end] > x && x <= nums[end + 1]) {++ans; x = nums[end]; end = begin = end + 2; costBegin = -1;}                else {flag = false; break;}            }        }        if (flag) cout<<<'\n';        else cout<<"-1\n";    }    return 0;}

分享面经，积攒好运🙏一面见之前的帖子3.10二面（过）自我介绍你们实验室做什么项目？你这个用布隆过滤器替代分布式锁访问数据库提升QPS的，介绍一下Redisson的底层是什么样的？你这个短链接是怎么生成的？有没有了解过别的生成算法开放题：我现在要提升你这个系统的QPS，你怎么从0开始设计？你说加机器，那你数据库支持水平拆分吗介绍一下这个ShardingSphere的原理？你有没有了解过逻辑sql怎么转真实sql的？ShardingSphere支持自动迁移数据吗？如果我使用了order by，那ShardingSphere会这么处理？查32个表吗？讲一下你认为的项目亮点你说一下这个读写锁的应用场景，我感觉不需要啊？Redisson这个读写锁是什么原理你知道吗？如果我发一个消息到MQ，十分钟后才被消费，怎么办？期间分组被改了怎么办？你这个RPC介绍一下你介绍一下这个自定义协议，为啥要自定义协议？头部有哪些字段？你用的什么网络框架？你知道netty是哪种网络模型吗？阻塞/非阻塞？同步/异步？Socket用过吗？说一下系统调用是什么？MySQL索引为啥用b+树？redis单线程，为什么还这么快？大模型用过吗？除了工作部分，还用大模型做些什么？手撕：布隆过滤器3.13三面（挂）自我介绍你的项目的技术难点在哪里？你数据表是怎么设计的？表里的索引怎么设计的？缓存空间有多大（？）你怎么统计用户的访问数据？用消息队列？消息队列会阻塞吗？就是满了怎么办？（？）短时间内大量请求打满消息队列怎么办？（答了扩容+加消费者）如果是集群，负载均衡你会怎么设计？讲一下一致性哈希讲一下你这个重试策略数据库热点问题你怎么解决？慢sql问题你怎么解决？你分析过慢sql吗？explain？我设计的系统如果想接入微信扫码登陆，你会怎么做？了解过微信支付宝的授权登录协议没有？手撕：sql：抖音活跃用户分析（完全没准备sql，写的一坨）手撕：128. 最长连续序列