大三日常实习面试，ACM银牌选手，计科专业
- 一面时间：2020.12.29
- 二面时间：2021.01.05
- 三面时间：2021.01.07
- HR面时间：2021.01.13
一面
自我介绍（五分钟）
你先做两道题吧
T1：
完美洗牌问题（1）
给定一个长度为偶数的数组arr，长度记为2*N。前n个为左部分，后n个为右部分。arr可以表示为\(\{L_{1}, L_{2} \ldots L_{n-1}, L_{n}, R_{1}, R_{2} \ldots R_{n-1},R_{n}\}\)。请将数组调整成\(\{R_{1}, L_{1}, R_{2}, L_{2}, \ldots R_{n}, L_{n}\}\)
这题没必要给代码了吧
T2：
用一个栈实现另一个栈的排序
一个栈中元素的类型为整型，现在想将该栈从顶到底按从大到小的顺序排序，只许申请一个栈。除此之外，可以申请新的变量，但不能申请额外的数据结构。如何完成排序？
其实\(o(n^2)\)模拟就行，稍微注意点细节
我的做法是每次找左边那个栈的最大值，然后放到右边那个栈里去。
面试官给的做法是每次把左边那个栈的栈顶拿出来，然后遍历右边那个栈，如果右边的栈顶大于拿出来的元素就不断地pop到左边去，然后把拿出来的元素插入到右边，再把刚刚pop出来的元素放回来；这样就保证了右边的栈始终是有序的。
其实我觉得时间复杂度都一样，而且代码量也差不多，说不上哪个更优雅。
#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(int i=a;i<=b;++i)
#define dep(i,a,b) for(int i=a;i>=b;--i)
#define pb push_back
int sta1[100100],top1;
int sta2[100100],top2;
int main(){
int n;scanf("%d",&n);
rep(i,1,n){
int x;cin>>x;
sta2[++top2]=x;
}
rep(i,1,n) sta1[++top1]=sta2[top2],top2--;
rep(i,1,n){
int mx=-1001000;
int tmp=top1;
while(top1){
sta2[++top2]=sta1[top1];
mx=max(mx,sta1[top1]);
top1--;
}
int fr=1;
rep(j,1,tmp){
if(sta2[top2]!=mx) sta1[++top1]=sta2[top2];
else{
if(!fr) sta1[++top1]=sta2[top2];
fr=0;
} top2--;
}
sta2[++top2]=mx;
}
while(top2) sta1[++top1]=sta2[top2--];
while(top1) printf("%d ",sta1[top1--]);
}
问：你学过数据库吗？
答：数据库是选修课，我没上过。
问：用过数据库吗？
答：用过Mysql，Memcahce，Redis，仅限于用过。
问：那你有开发经验或者项目经验吗？
答：没有。
那我问你两个实际问题吧。
给你一个场景：要你统计学生期末各科成绩、总分以及平均分，如何设计数据库表。
我：？？？？没学过数据库不知道怎么设计，如果是Excel表的话我会。
哦看出来你是真的没有学过数据库。
我：？？？？？
你写了一个接口，但是用户调用的时候经常超时，你会如何定位这个问题。
我：能解释一下调用超时具体是什么吗？
答：有些用户对于时间的要求可能会比较严格，比如他调用你的接口，但是一秒之后你还是没返回结果，他就会断开连接，这就超时了。
我：没写过接口，我可能会先检查一下是不是用户传入参数的问题。
答：用户传入参数这个过程在测试阶段肯定就做过了呀。
我：。。。。。。
面试官的答案：首先检查是不是网络导致的超时，然后在你的接口的不同地方写一些日志，去分析日志输出就好了。
哦看得出来你是真的没有开发经验。
我：？？？？？？
二面
自我介绍
先做两道题吧
T1
n个苹果，m个盘子，要求把苹果放到盘子里，盘子可以为空，1,1,5和1,5,1算一种方案，问方案数。
其实就是整数划分问题，问题可以转化为求\(0 \leq x_1 \leq x_2 \leq x_3 \leq \cdots \leq x_m\ \&\& \sum_{i=1}^m x_i =n\) 的方案数。
#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(auto i=(a);i<=(b);++i)
#define dep(i,a,b) for(auto i=(a);i>=(b);--i)
#define pb push_back
typedef long long ll;
const int maxn=(int)1e6+100;
const int mod=(int)1e9+7;
int dp[110][110][110];//前i个盘子 还剩j个苹果 最后一个放k个
int sum[110][110][110];//sigma dp[i][j][from k to m];
//x1>=x2>=x3...>=xm>=0 && sigma xi==n
int main(){
int n,m;scanf("%d%d",&n,&m);
dp[0][m][m]=1;
rep(i,0,n){
if(i){
dep(j,m,0) rep(k,0,j)//第i个放k个
dp[i][j-k][k]+=sum[i-1][j][k];
}
rep(j,0,m) dep(k,m,0)
sum[i][j][k]=sum[i][j][k+1]+dp[i][j][k];
}
int ans=0;
rep(i,0,m) ans+=dp[n][0][i];
printf("%d\n",ans);
}
T2
定义两个串相似：当且仅当其中一个串选择两个位置交换后能变成另一个串。
一个字符串可以加入一个字符串集 S 当且仅当这个串和 S 中的某个串相似。
给一个字符串集 A ，问你 A 可以分为多少个集合。
模拟就好了
#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(auto i=(a);i<=(b);++i)
#define dep(i,a,b) for(auto i=(a);i>=(b);--i)
#define pb push_back
typedef long long ll;
const int maxn=(int)1e6+100;
const int mod=(int)1e9+7;
bool eq(string a,string b){
if(a.length()!=b.length()) return 0;
int num[2][26];
memset(num,0,sizeof(num));
for(auto c:a) num[0][c-'a']++;
for(auto c:b) num[1][c-'a']++;
rep(i,0,25) if(num[0][i]!=num[1][i]) return 0;
vector<int> v;
rep(i,0,(int)a.length()-1) if(a[i]!=b[i]) v.pb(i);
if(v.size()!=2) return 0;
if(a[v[0]]!=b[v[1]]||a[v[1]]!=b[v[0]]) return 0;
return 1;
}
vector<vector<string> > v;
int main(){
int n;cin>>n;
while(n--){
string s;cin>>s;
int in=0;
for(auto &vec:v){
int f=0;
for(auto u:vec) if(eq(u,s)) in=f=1;
if(f){vec.pb(s);break;}
}
if(!in){
vector<string> t;
t.pb(s);v.pb(t);
}
}
printf("%d\n",(int)v.size());
}
好的，我没有问题了，你有什么问题吗？
然后聊了会天就结束了。
三面
自我介绍（两分钟就讲完了）
问：你打竞赛用的是什么语言？
答：C++
那我问你一点C++的问题吧。
问：了解什么是多态吗？
答：不太清楚细节，只知道C++有继承、封装、多态三个特性。而且打竞赛的时候也是写的越简单越好，不会用到这些。
问：你们打比赛的时候应该会用STL吧？
答：会的
问：那你简述一下list<int>和vector<int>的区别
答：几乎没有用过list，基本都是用vector的，因为手写链表比list要更快。vector底层其实有三个指针first,end,last，vector的内存扩容是在内存中开辟一份新的空间（在Linux中是原空间的两倍）然后将旧的数据移动到新空间中，再把旧空间删去。至于list我就不知道了。
问：说一下vector和map中erase()的区别。
答：这俩一个是顺序容器一个是非顺序容器。vector的删除是O(n)的，而map是O(logn)的，原因是vector底层其实是数组，而map底层是红黑树。其他我就不知道了。
面试官：其实主要区别还有一个就是erase()的返回值不一样，vector返回的是删除元素的下一个元素的迭代器，所以循环的时候要it=erase(it)，但是map可以写成erase(it++)。并且这两个都不能在循环删除时写it++。
PS.以后再有人问我用什么语言我就说用C了！
问：了解网络方面的知识吗？
答：了解
问：说一说TCP流量控制吧。
答：TCP流量控制主要是通过TCP头部的窗口字段实现的，接收方给发送方发送的窗口大小就规定了发送方最多只能发那么数据，这样就实现了点到点的流量控制。但是时间工作的过程中发送方的发送窗口往往是有流量控制窗口和拥塞控制窗口一起决定的，取他们两个中小的那一个。
问：那你讲讲拥塞控制是怎么实现的吧。
答：和流量控制不同，拥塞控制主要的作用是为了防止大量流量涌入网络造成网络拥塞，这是发送方自己控制自己的发送速率，而流量控制是接收方去控制发送方的发送速率，可以说拥塞控制是考虑全局的拥塞情况。具体而言，拥塞控制使用了慢开始和拥塞避免算法，还有快重传和快恢复算法。具体来说这四个算法的实现过程为...（省去介绍这几个算法的部分，真的字太多了，不想打）。
问：拥塞控制一开始确定是发送一个MSS吗？
答：是的吧，我看的所有资料都是说是一个。
面试官：其实现在的TCP协议一般都是10个，可能书上都是写1个的。
问：知道MSS的大小吗，在以太网环境中。
答：我知道MTU是1500，MSS怎么算的我忘记了。
面试官：一般是1460，1500减去TCP头部20和IP头部20就是1460。
（其实我在想那俩头部不是还有可选的选项吗）
好的给你两道题做一下。
T1
0左边必有1的二进制字符串的数量
给定一个整数n，求由“0”字符和“1”字符组成的长度为n的所有字符串中，满足“0”字符的左边必有“1”字符的字符串的数量。
\(1 \leq n \leq 2 \times 10^7 \)
这道题的题目描述有点问题，这里的左边其实指的是相邻的左边。
显然可以知道第一位必定是1，那么问题就变为了：长为\(n-1\)的不包含连续0的01串的个数。
\(dp[i][2]\)表示前\(i\)个，最后一个是(0/1)的方案数。
那么 \(dp[i][0]=dp[i-1][1],dp[i][1]=dp[i-1][1]+dp[i-1][0]\)
但是交上去MLE了，卡空间，那就用滚动数组滚掉一维。
#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(int i=a;i<=b;++i)
#define dep(i,a,b) for(int i=a;i>=b;--i)
#define pb push_back
typedef long long ll;
const int maxn=(int)2e7+100;
const int mod=(1<<29);
ll pre[2],dp[2];//前i位，最后一位是否为1
int main(){
int n;scanf("%d",&n);
n--;pre[1]=1;
rep(i,1,n){
dp[0]=pre[1];
dp[1]=(pre[0]+pre[1])%mod;
pre[0]=dp[0];pre[1]=dp[1];
}
printf("%lld\n",(pre[0]+pre[1])%mod);
}
T2
画匠问题
给定一个整型数组arr, 数组中的每个值都为正数，表示完成一幅画作需要的时间，再给定一个整数num，表示画匠的数量，每个画匠只能画连在一起(即数组内连续的一段)的画作。所有画家并行工作，请返回完成所有的画作的最少时间。
要求时间复杂度为\(O(n \log\ S)\)，其中S表示所有画作所需时间的和。
问题转换为：将长为n的数组分为连续的k段，求每段和的最大值最小的方案。
二分答案即可，看到时间复杂度的要求就更不难想到了。
题目里啥信息也没有，这个题的\(a[i]\)是1e9，没开long long还WA了一发。
#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(int i=a;i<=b;++i)
#define dep(i,a,b) for(int i=a;i>=b;--i)
#define pb push_back
typedef long long ll;
const int maxn=(int)1e6+100;
ll a[maxn];
int n,k;
bool check(ll x){
ll tot=0,sum=0;
rep(i,1,n){
if(sum+a[i]<=x) sum+=a[i];
else tot++,sum=a[i];
}
if(sum) tot++;
return tot<=k;
}
int main(){
scanf("%d%d",&n,&k);
ll sum=0,mx=0;
rep(i,1,n) scanf("%lld",&a[i]),sum+=a[i],mx=max(mx,a[i]);
ll l=mx,r=sum,ans=sum;
while(l<=r){
ll mid=(l+r)>>1;
if(check(mid)) r=mid-1,ans=mid;
else l=mid+1;
}printf("%lld\n",ans);
}
讲完两份代码之后就没了，反问时间也没问什么，问了一下他们后端的语言是什么，答曰\(go\)。
