1. 模拟 给一个01串，可以进行两种操作00->11,10->01要求最后所有的0在1前面，求最小操作次数思路：遍历数组，找最前面的1下标，记为ln->l反序遍历，遇到01变成10，操作次数加1，遇到00变成11,操作一次加一，其他不变遍历完即可2. 异或前缀和给一个数组a1~an，和查询l,r，求al-ar区域的k进制异或和tk,求max(tk)-min(tk)，k取值2-10思路：维护S(j,k)表示0-j的k进制异或和，则tk = sub(S(r,k)-S(l-1,k),k)，sub表示不进位减法遍历k即可3. 二分给定由CM组成的字符串s{1~n},记s{1~l-1}以及s{r+1~n}的c的个数，和s{l~r}的m的个数的最大值为t(l,r)求 max{t(l,r)}思路：维护前缀和 c{0~n}和m{0~n}表示前n个字符里c和m的个数则 t(l,r) = max{c(n)-c(r)+c(l-1),m(r)-m(l-1)}注意到, 固定l, c(n)-c(r)+c(l-1)-m(r)+m(l-1)是单调的，也就是r变动一下，要么c的个数变多，要么m的个数变少利用二分求c(n)-c(r)+c(l-1)-m(r)+m(l-1)=0的r代入即为最小的t(l,r)遍历l，二分找r，求t(l,r)的最大值即可

第一题 签到题 首字符 + 偶数下标字符第二题 贪心+模拟求发货最小成本，对每天必须发完的货来说，优先按低价发（也就是在价格低的天发），遍历时按价格升序维护可发包的天，然后模拟即可维护一个有序set（TreeSet），元素i代表第i天，按发货价格排序。维护第i天发包裹使用次数ci，按天遍历，第i天，将i入set，遍历set（发货价格低到高），发货直到发包裹使用次数到x或者第i天包裹已经发完记录使用的成本，即为结果第三题求平衡序列的个数维护前i项数组和Si（包括0），注意到Si-i=Sj-j表示i~j是平衡序列，使用map统计si-i的次数v，遍历map，对C(v,2) = v*(v-1)/2求和即可第四题 贪心 + gcd求x倍下标与y倍小标差的最大值，除去x*y倍数的下标，给x安排大的，给y安排小的即可对原数组排序，维护前i项数组和S(i)，对每个x,y，求最小公倍数 t = x*y/gcd(x,y)最后结果就是 S(n)-S(n-n/x+n/t)-S(n/y-n/t)，/表示整除

面了一个月终于有offer了，感谢团子的offer，团孝子启动！timeline3.22 笔试 2.6/33.23 ai面3.24 约一面4.1 一面挂4.2 被捞约一面4.9 一面前换时间4.14 一面4.17 二面4.18 oc4.21 offer非科班(数学)太难了，暑期挂麻了

4.10 一面自我介绍介绍项目数仓分层具体每层作用hadoop hdfs yarn mr数据倾斜架构选型项目中遇到的问题sql 每个品类消费最高的用户反问==================4.17 二面二面没啥八股，纯拷打项目，也没有手撕sql，30min完事，感觉不妙

第一题 维护一颗树，求树最深节点的名称集合。递归维护树高，收集最大深度的节点名称到数组里，排序输出就行了。第二题最短路。数据量小，暴力dfs都能过。最短路算法也行第三题考察逆序对。按螺旋方向把二维展成一维，用树状数组logn时间复杂度查询逆序对，最后求和取模。

自我介绍 说说项目的核心部分项目相关问题token 和 cookie session区别加密和签名区别双token刷新流程mysql 乐观锁和悲观锁设计一个滑动窗口，限制访问次数（滑动窗口限流）手撕 堆排序反问1h 答的不好 感觉g了

部门 基础研发自我介绍项目中遇到的困难挑一个项目最核心的部分讲讲手撕 删除链表重复数字操作系统的锁机制是怎么实现的？（问懵了）mysql 隔离级别 可重复读原理输入网址到显示内容发生了什么反问30min 感觉g了

第一题 把所有回文时间按时间顺序填在数组里，然后遍历找比输入大的里最小的，做差就是结果第二题模拟模拟栈出栈入栈，同时维护入栈的id，假如在第i个操作出栈有问题，判断一下i+1是不是符合要求，符合要求则维护res=i+1否则就是待出栈元素的res=id。结果就是res-1,res第三题dp如果a[i]=0,f[i] = f[i-2]否则如果 a[i-1]*10+a[i]<=26,f[i] = f[i-1]+f[i-2]否则 f[i] = f[i-1]还得维护mod=1e9+7第四题排序加二分按l排序，遍历每个元素，二分查找l小于等于第i个元素r的最大下标j，然后结果加上j-i

1. 百万点赞，如何设计点赞系统答：user_id分片存redis，mq异步同步到数据库2. 有没有了解过Cache Design Pattern（缓存设计系统）3. 写完ES，发消息给下游，下游读ES，发现读不到，可能是什么原因？答：es一般先写入内存缓冲区，这时还没有写入磁盘，所以读不到（开始说可能有延迟，面试官说是这么回事，但是能不能专业术语。后面经面试官提醒才答出来）4. Redis持久化答：AOF，RDB5. 设计一个基于磁盘DB，要求写入性能非常高，但是数据不能丢失（用这个提醒题3）答：先写入内存缓冲区，写入内存缓存区的同时把命令追加写到log文件里，之后慢慢从内存持久化到磁盘。（面试官说这叫 TransLog，问我有没有听过）6. 那分布式场景呢，如何保证DB的数据不丢失答：我说集群模式，根据log文件offest优先选主。7. 集群模式下，N个节点，写入时写W个节点，读的时候读R个节点，满足什么条件能保证读到最新数据？答：W+R>N(面试官说这叫可调一致性，完全没了解过)8. 磁盘上有10个文件，每个文件格式：hello worldnice to meet you写一个Java程序，并发读文件，统计词频，最终返回Map res，在规定时间内没读完统计多少就返回多少总结，基本全是场景题，全程拷打。面试官很强，不会的循环渐进出题提醒我写最后一个题时在文本编辑器上写，直接gg，java 并发api基本忘了，没IDEA根本写不出来。最后用伪代码应付了事。反问阶段问建议，面试官建议我多写写java。

美团约面了，但是时间全部不合适，我给写了哪天有空，然后就没动静了。是不是还得打电话说一声。

第一题 镜像回文字符串，双指针判断 100/100第二题 初看还以为是个nlogn复杂度的题，结果我写的n^2暴力居然过了 100/100暴力做法：对每个元素，双指针统计两边大于等于和小于等于的个数，两者相等则答案加一第三题：68/100a一半，思路估计有问题

第一题 统计一下带圈字母个数，做了半天才反应过来第二题排序，二分加前缀和玄学的地方来了，我用java写的，一样的代码交了三次，通过样例70，90，100，出错原因都是超时。java运行时间这么不稳定么第三题统计数位0-9次数，然后判断数位和是不是质数，是质数则答案得算组合数，不是答案就是0