2018头条春招笔试&面试（后台方向）
第一题（10分）
给你n个元素，输出不同的差值为 k 的个数
第一行输入一个 n 与 k
第二行输入 n 个数
输入
5 2
1 5 3 4 2
输出
3
朴素的思想就是排序后O(n^2)的做法，但是只能过80%的样例。
如果要优化就是先考虑一下差值为0的情况，计算重复数字的个数即可。
接下来新建一个 unordered_set，每次从去重后的 vector then取出一个数，把 then[i]+k放到一个 unordered_set s中，每次再比较s中是否有 then[i]，有 then[i]，答案++。
const int maxn = 1000000+10;
using namespace std;
vector<int> before;
vector<int> then;
unordered_set<int> s;
int n, k;
void read_in() {
scanf("%d%d", &n, &k);
int tmp;
for(int i = 0; i < n; i++) {
scanf("%d", &tmp);
before.push_back(tmp);
}
sort(before.begin(), before.end());
then.push_back(before.front());
for(int i = 1; i < n; i++) {
if(before[i] != before[i-1])
then.push_back(before[i]);
}
}
long long solve() {
long long ans = 0;
if(k == 0) {
int cnt = 1;
for(int i = 1; i < n; i++) {
if(before[i] == before[i-1]) {
cnt ++;
} else {
if(cnt >= 2) ans ++;
cnt = 1;
}
}
if(cnt >= 2) ans ++;
return ans;
}
for(auto& i : then) {
if(s.count(i)) {
ans += 1;
s.erase(i);
}
s.insert(i+k);
}
return ans;
}
int main() {
read_in();
long long ans = solve();
printf("%lld\n", ans);
return 0;
}
[/cpp]
## 第二题（20分）
一个裸的 dfs，题面不记得了
```cpp
int n,step=2147483647;
using namespace std;
void dfs(int s,int m,int sum)
{
if(s==n)
{
step=min(step,sum);
return;
}
if(s>n)
return;
dfs(s+m,m,sum+1);
dfs(s+s,s,sum+1);
}
int main()
{
cin>>n;
dfs(1,1,0);
cout<<step<<endl;
return 0;
}
[/cpp]
## 第三题（20分）
现场时间没写的出来，一道模拟，一个字符串只包含'+','-','*','6'四种字符，解析字符串，读出算式算出答案，然后将答案用奇怪的图形输出出来。
用两个栈，一个存数字一个存操作符，遇到乘法取出上一个字符计算上一个数字和下一个数字相乘后的结果放回栈，最后就可以得到一个只有加减法的操作，最后扫一遍搞定。
就是注意要用long long。
### 第四题（25分）
给一个包含 n 个整数元素的集合 a, 一个包含 m 个整数元素的集合 b
定义 magic 操作为, 从一个集合中取出一个元素, 放到另一个集台里, 且操作过后每个集台的平均值都大于操作前。
注意以下两点:
①不可以把一个集合的元素取空,这样就没有平均值了
②值为 x 的元素从集台 b 取出放入集和 a, 但集合 a 中已经有值为x的元素,则a的平均值不变(因为集台元素不会重复), b 的平均值可能会改变(因为 x 被取出了)
最多可以进行多少次 magic 操作?
0 <n,m<1e5,1<a[i]b[i]<1e8
输入
3 5
1 2 5
2 3 4 5 6
输出
2
从b取出3,4放到a
现场只过了70%，重写了一下
```cpp
using namespace std;
vector<int> a, b;
int n, m;
double ave1 = 0, ave2 = 0;
double sum1, sum2;
void read_in() {
scanf("%d%d", &n, &m);
int tmp;
for(int i = 0; i < n; i++) {
scanf("%d", &tmp);
a.push_back(tmp);
sum1 += tmp;
}
for(int i = 0; i < m; i++) {
scanf("%d", &tmp);
b.push_back(tmp);
sum2 += tmp;
}
ave1 = sum1 / n;
ave2 = sum2 / m;
}
bool judge(int num) {
return (sum1+num)/(n+1) > ave1 and (sum2-num)/(m-1) > ave2;
}
int solve() {
if(ave2 < ave1) {
swap(a, b);
swap(ave1, ave2);
swap(sum1, sum2);
swap(n, m);
}
int sum = 0;
long loc = ceil(ave1) > ave1 ? lower_bound(b.begin(), b.end(), ceil(ave1)) - b.begin() :
upper_bound(b.begin(), b.end(), ceil(ave1)) - b.begin();
vector<int> cal;
for(auto i = loc; i < b.size(); i++) {
cal.push_back(b[i]);
}
for(auto& i : cal) {
if(i > ave2 or i < ave1) break;
if(judge(i)) {
sum ++;
n++, m--;
sum1 += i;
sum2 -= i;
ave1 = sum1 / n;
ave2 = sum2 / m;
}
}
return sum;
}
int main() {
read_in();
int res = solve();
printf("%d\n", res);
return 0;
}
[/cpp]
## 第五题（25分）
题目描述
小T最近迷上了一款跳板小游戏
已知空中有N个高度互不相同的就板,小小阳开始在高度为0的地方,每次跳跃可以选择与自已面前高度绝对值差对小于等于H的板,跳跃过后到达以跳板为轴的镜像位置,问小T在最多跳K次的情况下最高能跳多高（任意时刻,高度不能为负）
输入描述
第一行三个整数N,区,H
下x行,每行一个整数,表示第个跳板的离地高度
输出描述
能跳到最高的高度
输入
3 3 2
1
3
6
输出
8
```cpp
using namespace std;
int n, k, h;
vector<int> v;
void read_in() {
scanf("%d%d%d", &n, &k, &h);
int tmp;
for(int i = 0; i < n; i++) {
scanf("%d", &tmp);
v.push_back(tmp);
}
sort(v.begin(), v.end());
}
int solve() {
int now = 0;
int loc = 0;
while(k) {
int lim = now + h;
for( ; loc < n; loc++) {
if(v[loc] > lim)
break;
}
if(loc == n) {
--loc;
if(v[loc] > now) {
now = v[loc] - now + v[loc];
}
break;
}
if(v[loc] <= now or loc == 0) {
break;
}
if(v[loc-1] <= now) {
break;
}
now = v[--loc] - now + v[loc];
k--;
}
return now;
}
int main() {
read_in();
int res = solve();
printf("%d\n", res);
return 0;
}
[/cpp]
总结，题目很有趣，没了。
# 面试
预约的下午三点，提前半小时签到，准时开始。
1. 先自我介绍
2. 一道题目
给你两个链表，算出和，我以为是链表相加，结果交流几次才发现是把两个链表当成竖式做。例子如下
1->3->5
+ 2->4
--------
1->5->9
交流了发现是竖式相加。
3. 一个二维数组，从上到下从左到右分别递增，问怎么找到k
atrix = [[1, 2, 3, 4],
[2, 3, 6, 8],
[3, 6, 7, 9]]
我说了从左下角向上搜索，结果面试官说还有什么别的思路，我就说了两个维度二分减少搜索区间，但不明白面试官为什么不太满意。
4. 说了项目相关的，让介绍了一下，然后询问了一下项目细节
5. 网络TCP的三次握手四次挥手
6. Http的keep alive（就是长连接）是什么，原理是什么，会出现什么问题
7. 数据库，给你一个表，包含用户姓名和订单时间，让你选出某个用户的全部订单/某个时间区间的全部订单/某个用户猴哥时间区间的全部订单，问你怎么建立索引。
8. 询问对Linux熟不熟悉，问了怎么查看某个端口是否被占用，某个进程正在访问那些文件。
9. 进程和线程是什么，有什么区别
10. 哈夫曼编码是什么，什么情况下用的到
11. 图的最短路算法是什么，dijkstra是怎么实现的
12. 做的项目中难点是什么，怎么解决的
13. 有什么自己比较擅长的但是面试中没有问到的。
面试完成后两分钟收到了电话，说不适合，秋招再见。
这个面试异常的长，在我之前有6个人半个小时我就到了队列的顶端，然后，我从3：05面到了将近3：50，问了一下群里巨佬一面都没问太多东西。
我严重怀疑这个hr把我当成应届生面了，大概就是所谓的凉凉
就是除了写代码，就是项目上还有计算机网路操作系统都要熟悉，下次再来