epoll八股
B树和B+树就是高度问题，B+有链表链接，最快磁盘IO
红黑树五个插入七个删除
输入URL到打开百度经典八股：DNS解析，DNS树递归，TCP通信，HTTP协议，期间还有四次挥手合并的问题，可以讲讲
TCP可靠传输：序列号，确认应答，拥塞控制，滑动窗口
拥塞控制的慢启动，拥塞避免，快重传、快恢复
CRC冗余校验
设计模式会多少说多少，单例，工厂，装饰器
动态多态静态多态八股
DNS我忘了
LRU沙比题

字节

2021年10月17日笔试

A简单计数，B链表模拟，C线性dp，D双指针计数

都很简单，没什么好说的，AK

美团

2021年8月15日笔试

判断输入数组是不是一个排列
给定一个字符串，你要在其末尾添加任意字符，形成一个回文，求最少的添加数目
一堆机器人在x坐标轴上，给定坐标和运动方向，每当整数时刻过去，相遇的两个机器人会碰撞毁灭，求每个机器人的生存时间
正向单源最短路+反向单源最短路
简单的二维dp

2021年8月20日一面

凉透了，在后面补正确的答案吧，口头回答不做记录了。

面试官一直在暗示我，但是我真的没学过也不可能想起来啊QAQ

操作系统

进程与线程的概念，以及它们的区别？（
进程间通信的方式。（

计网

TCP/IP协议是哪一层？（TCP传输层协议，IP网络层协议
哪些协议基于TCP，哪些常用协议基于UDP？
http request包含哪些结构，他如何组成这个协议？
http request header常见字段，你有使用过吗？
https你了解吗？
https如何进行加密解密来保证安全传输？
https的证书的本质？（非对称加密
你除了算法平时还会学习那些东西？
有有关项目的经历吗？
数据库学过吗？事务的四大特性以及事务管理级别。
你平时只用C++吗？面向对象特点。
三次握手，四次挥手。

两个编程题

给定一个数组，输出该数组所有子集
写出LRU算法

反问

面试官最看重本科生什么品质？

面试不会特别区分本科学士和硕士，研究生实习经历会比较多，本科实习经历与项目会比较少。会从OS、计网、数据库等课内知识来问，整体覆盖一下。算法不同公司有差别，美团不会特别看重。

普遍出现在本科生身上的问题有哪些？

课内基础扎实的话就没什么问题，语言什么的是工具不会做过多要求，课内基础包括算法这一块要学好。

面试遇到的算竞选手会很多吗？

我经历校招不是很多，但是也有，相对本科生总数来说占比很少。

算竞选手其他方面会比较薄弱吗？

其他方面需要稍微加强，算竞选手笔试环节很猛，面试一般来说会加一道算法题。

2021年8月24日二面

做下自我介绍
大学期间都在打竞赛？能具体讲一下吗，哪个事情比较有挑战。
你为什么从0开始打算法竞赛？
竞赛的核心以及需要的能力，有什么套路和方法吗？
你后以什么样的职业规划呢？
C++的多线程和操作系统的多线程是什么样的关系？
操作系统线程切换是怎么实现的
C++的参数传递是怎么做的，从编译的视角讲一下这个过程
同步异步、阻塞非阻塞

2021年9月7日美团打车一面

技术栈

thrift、java、spring、redis、hive、mybatis

2021年9月9日美团打车二面

学校经历，竞赛经历，你最近干了啥，暑假干了啥，其他厂子offer接没接，哪个厂子，职业生涯规划（各个时间段说一说），一个二叉树最大路径和，死缠职业规划和你暑假干了啥。然后有一个设计题，10万人同时点赞，给你100台机器，问你怎么设计B站点赞系统。

小米

网易

2021年8月21日笔试

给定一个数组，求出其中和<m的二元组数目。
字符串拼接+reverse，n<26。
n个小朋友围成环，如果两个小朋友相邻，那么年龄大的吃的饼干一定比另一个多，求出最少饼干数。
给定地图，求从 $[0,0]$ 到 $[n-1,m-1]$ 的最短距离。
简答：说出常见软件开发模型及其特点。

网易有道词典笔嵌入式客户端二面

虚函数，指向某个类型的空指针，然后各种神奇调用
this指针具体是什么
列表初始化为什么会快
单例类
菱形继承举了个实例，具体过程讲一遍
char *p = "abcd"和char p[] = "abcd"区别
手写一个智能指针
shared_ptr计数实现原理
生产者消费者模型讲一下
设计一个日志类
设计一个APP用于展示图片，每隔一定时间向服务器发请求接受图片并刷新。
网易工作PC开发，轻松愉快，预估工时按时完成。
“感谢你的时间”说了三遍。

京东

2021年8月21日笔试

我靠好难，30道选择+2道编程。选择题emm很搞心态，C/C++、操作系统、计网、数据库都考了。

网格上$n$个点每个坐标 $ [x,y] $，问处于同一对角线的二元组有多少。
小明有一个只包含0和1的字符串，现在小明希望将整个字符串尽可能的切割成多个字符串，要求是每个字符串里面0出现的次数和1出现的次数的比例是一致的。

解释：假设一个字符串出现0的次数是a次，出现1的次数是b，另一个字符串出现0的次数是c次，出现1的次数是d次，那么这两个字符串01出现次数比例相同表示 $\dfrac{a}{b}=\dfrac{c}{d}$ ，即 $a\times d=b\times c$ 。注意这里a，b，c，d都是可以为0的。

现在对于一个字符串的所有前缀字符串，输出最多可以切割成多少个符合要求的字符串。

这个第二题需要在这里额外讨论一下

附赠骗分代码，只过了6%的数组。

思路是 $O(n\ln n)$ 预处理每一个数的质因子，对于每一个前缀 $i$ ，枚举他的质因子 $p$ ，尝试根据 $p$ 来将这一段分割成尽量多的段数。

通过二分来查找下一个合法的落脚点，如果不能合法落脚的话，那么我们将该段长度 $base$ 修改为 $base+p$ ，并尝试确认这一段是否合法。

时间复杂度 $O(n\ln n \log n)$，下面这段代码的问题在于，第一段长度不一定固定为 $p$ ，而有可能是 $p$ 的倍数。

我不知道是这个做法假了，还是我单纯的实现有问题（提交结果是RE我懒得调了直接跑路）。

#include<bits/stdc++.h>
using namespace std;
const int maxn  =5e5+10;
char s[maxn];
int dp[maxn],sum[maxn];
int check(int p,int x)
{//切割[1,p]，以[1,x]为基准，x是p的一个质因子
    if(sum[p]==0||sum[p]==p)
        return p;
    int a=sum[x],b=x-sum[x],ret=1,pre=x;
    for(int i=x+1;i<=p;i++)
    {//应该把第一段也放进来切割，可能是x的倍数
        int c=sum[p]-sum[pre],d=p-pre-c;
        if(a*c!=b*d)
            return ret;
        ret++;//[pre+1,p]可以分出来
        int pos=pre,need=0;
        bool ok=0;
        do
        {
            need+=x;//这个二分很没必要
            pos=lower_bound(sum+pre+1,sum+p+1,need-sum[pre])-sum;//0比想要的少
            int num=pos-pre-(sum[pos]-sum[pre]);
            int r=lower_bound(sum+pre+1,sum+p+1,need-sum[pre]+1)-sum-1;
            if(need*a/b>=num&&need*a/b<=num+r-pos)
            {
                ok=1;
                pos=pre+need+need*a/b;
            }
        }while(!ok||pre+need<p);
        if(ok)
            pre=pos;
    }
    return ret;
}
int dfs(int p,int x)
{//以[1,r]有x块为基准
    int a=sum[x],b=x-sum[x];
    if(sum[p]==0||sum[p]==p)
        return p;
    int ret=1,pre=x;
    for(int i=x+1;i<=p;i+=x)
    {
        int c=sum[p]-sum[pre],d=p-pre-c;
        if(a*c!=b*d)
            return ret;
        ret++;
    }
    return ret;
}
vector<int> f[maxn];
bool vis[maxn];
int main()
{
    int n;
    scanf("%d%s",&n,s+1);
    for(int i=2;i<=n;i++)
    {//这个埃筛还写挫了，恶心心
        vis[i]=1;
        for(int j=i;j<=n;j+=i)
            f[j].push_back(i),vis[j]=1;
    }
    for(int i=1;i<=n;i++)
    {
        if(s[i]=='1')
            sum[i]++;
        sum[i]+=sum[i-1];
        dp[i]=1;
    }
    for(int i=1;i<=n;i++)
    {//
        for(int &j:f[i])
        {//
            dp[i]=max(dp[i],check(i,j));
        }
        /*int lim=sum[i];//一的个数,枚举因子
        for(int j=1;j*j<=lim;j++)
        {
            if(lim%j==0)
            {
                dp[i]=max(dp[i],check(i,j));
                while(lim%j==0)
                    lim/=j;
            }
            if(lim>1)
                dp[i]=max(dp[i],check(i,lim));
        }*/
    }
    for(int i=1;i<=n;i++)
        printf("%d ",dp[i]);
    return 0;
}

大概是正确答案？

我觉得没做出来我可以早点爬了

#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e5+10;
int ans[maxn];
char s[maxn];
int main()
{
    using pii = pair<int,int>;
    map<pii,int>mp;
    cin>>s+1;
    int c0=0,c1=0,n=strlen(s+1);
    for(int i=1;i<=n;i++)
    {
        if(s[i]=='0')
            c0++;
        else
            c1++;
        pii now;
        if(c0==0||c1==0)
        {
            if(c0==0)
                now=pii(0,1);
            else
                now=pii(1,0);
        }
        else{
            int g=__gcd(c0,c1);
            now=pii(c0/g,c1/g);
        }
        mp[now]++;
        ans[i]=mp[now];
    }
    for(int i=1;i<=n;i++)
        cout<<ans[i]<<' ';
    cout<<endl;
    return 0;
}

2021年8月30日一面

竞赛与项目印象最深的是那一场
学习过程中有什么印象深刻的问题
TCP/IP实践过吗
C++使用有什么印象深刻的问题
笔试的两道算法题讲一下