算法岗主要用机器学习东西多，所以还是投了软件开发。🙇♀
投递部门
(领域)通用软件开发工程师
(第一意向部门)中央软件院
(第二意向部门)Cloud BU
(中国/上海,中国/东莞,中国/北京,中国/南京,中国/廊坊,中国/成都,中国/杭州,中国/武汉,中国/深圳,中国/苏州,中国/西安)
笔试
- 牛客网的OJ
- 共享屏幕与摄像头
- 3道编程题共600分（具体每道题多少分值忘记了），硬件应该是做选择题
- 时间2h
- ACM式输入输出（与阿里相同，不同于之前面试中常见的只写函数模式）
- 虽然允许中途上厕所但是隔壁宿舍敲门催打扫卫生依然没有给开
- 不允许截屏等保存题目所以下文根据回忆大致复述一下题目大意
足球比赛排名
题意
双循环赛，给出每场比赛的比分，赢的加3分，平局各加1分，输的不加分，最后按先分数排名后字典序排名输出每一队的得分。
分析
结构体排序，可以用STL于是直接调用sort()就可以了。
用map保存所有出场的队伍名字，方便后期遍历。
代码
#include <iostream>
#include <string>
#include <algorithm>
#include <map>
using namespace std;
map<char, bool> mp;
struct node {
char name;
int score;
} a[30];
void init() {
for (int i = 0; i < 26; i++) {
a[i].name = 'a' + i;
a[i].score = 0;
}
}
bool cmp(node x, node y) {
if (x.score == y.score)
return x.name < y.name;
return x.score > y.score;
}
int main(int argc, const char * argv[])
{
//char s[10];
string s;
int cnt = 0;
init();
while (1) {
getline(cin, s);
if (s == "") break;
if (!mp[s[0]]) cnt++;
if (!mp[s[2]]) cnt++;
mp[s[0]] = true;
mp[s[2]] = true;
if (s[4] > s[6]) {
a[s[0]-'a'].score += 3;
} else if (s[4] < s[6]) {
a[s[2]-'a'].score += 3;
} else {
a[s[0]-'a'].score += 1;
a[s[2]-'a'].score += 1;
}
}
sort(a, a + 26, cmp);
for (int i = 0; i < cnt; i++) {
if (mp[a[i].name]) {
printf("%c %d", a[i].name, a[i].score);
if (i < cnt - 1)
printf(",");
mp[a[i].name] = false;
}
}
return 0;
}
猜帽子数量
题意
一群人，每个人都戴一种颜色的帽子，其中部分人给出其他人中有多少人和自己的帽子同一种颜色，问人群中最少有多少人能够满足上述条件。
样例
输入1
[1, 1, 2]
输出1
5
输入2
[]
输出2
0
之所以把样例放在这是因为它的输入太难搞了，卡了好久。
分析
把给出相同数字的人放在一起。假设一个人给出的数字为x，那么最多可以有x+1个人戴相同颜色帽子，如果和他给出相同数字的人多于x+1，那就要新开另一个颜色。所以对于n个给出相同数字的人，他们至少要用到的颜色样数为：
代码中用每达到x+1就清空重计数来实现：
代码
#include <iostream>
#include <string>
using namespace std;
const int max_info = 1005;
int main(int argc, const char * argv[])
{
int x, ans = 0;
int num[max_info] = {0};
getchar();
while (1) {
cin >> x;//cout<<x<<endl;
if (!cin >> x) {
cout << 0 << endl;
return 0;
}
if (!num[x]) {
ans += x + 1;
}
num[x] = (num[x] + 1) % (x + 1);
if (getchar() != ',') break;
}
printf("%d\n", ans);
return 0;
}
移动的最少步数
题意
给2个字符串（小写字母组成）和1个整数。整数代表游标位置，游标可以左右移动。从a串给出的初始位置开始，不断移动游标将b串一个一个拼出来，问最少步数。
分析
广度优先搜索+剪枝
保存每个状态：a串游标位置，b串拼到哪和步数。
拼好了就进行b串下一位，没拼好就继续探索a串的左一个和右一个，b串全拼完时跳出。
代码
写T了的dfs初稿
void dfs(int ai, int bi, int step, int last_dir) {//cout<<ai<<' '<<bi<<' '<<step<<endl;
if (bi == blen) {
ans = min(ans, step);
return;
}
if (a[ai] == b[bi]) {
dfs(ai, bi + 1, step, 0);
} else {
/*vis[ai] = true;
if (!vis[(ai - 1 + alen) % alen])
dfs((ai - 1 + alen) % alen, bi, step + 1);
if (!vis[(ai + 1) % alen])
dfs((ai + 1) % alen, bi, step + 1);
vis[ai] = false;
这里删了是因为用过一次的字母可以再一次用*/
if (last_dir != 1) {
dfs((ai - 1 + alen) % alen, bi, step + 1, -1);
}
if (last_dir != -1) {
dfs((ai + 1) % alen, bi, step + 1, 1);
}
}
}
因为判重没写好所以弃了，换写bfs。
成功AC的bfs完整版
#include <iostream>
#include <string>
#include <queue>
#include <map>
using namespace std;
string a, b;
const int maxa = 1005, maxb = 105;
int ans = maxa * maxb;
int alen, blen;
//bool vis[maxa];
typedef pair<int, int> p;
map<p, bool> mp;
struct node {
int ai, bi, step;
} st;
int bfs() {
queue<node> q;
q.push(st);
while (!q.empty()) {
node head = q.front(), tail;
q.pop();
if (head.bi == blen) {
return head.step;
}
if (a[head.ai] == b[head.bi]) {
tail.ai = head.ai;
tail.bi = head.bi + 1;
tail.step = head.step;
q.push(tail);
} else {
tail.ai = (head.ai - 1 + alen) % alen;
tail.bi = head.bi;
tail.step = head.step + 1;
if (!mp[make_pair(tail.ai, tail.bi)]) {
q.push(tail);
mp[make_pair(tail.ai, tail.bi)] = true;
}
tail.ai = (head.ai + 1) % alen;
tail.bi = head.bi;
tail.step = head.step + 1;
if (!mp[make_pair(tail.ai, tail.bi)]) {
q.push(tail);
mp[make_pair(tail.ai, tail.bi)] = true;
}
}
}
return -1;
}
int main(int argc, const char * argv[])
{
cin >> a >> b >> st.ai;
alen = a.length(), blen = b.length();
//dfs(st, 0, 0, 0);
st.bi = 0; st.step = 0;
cout << bfs() << endl;
return 0;
}
当然也要判重，不然会MLE。
判重用的pair保存两个字符串遍历到的位置（bfs中后达到的node因为step会更大所以不用理会了），比之前dfs里记录上一次转换方向要靠谱很多。
总结
1.5h做完，3道题全部100%通过率，稳过了。
综合测评
36道题，每1个里面有几个选项，比如“我擅长在压力下工作”“我喜欢团队协作”等，可以选从“非常不同意”到“非常同意”之间7个程度。如果有好几个选同一个选项，它还会再加一题问哪个最符合你。
专业面试1
形式：ZOOM视频会议
小插曲
开始意向工作地点写错了，填成西安但实际想去深圳，就不太想面，但hr来电话说之后还可能可以转，于是决定还是来试试。
很棒是看到群里有人签到之后等了很长时间，我就到时间直接面的。
面试
自我介绍
略
Q：用什么语言，C还是Java？
A：C/C++多一点，偶尔写Java。
项目
Q：社团有做过项目吗？
A：比较小，说说我的课程大作业吧：L1brary
Q：这个数据库是本地还是联网？
A：就用的华为的GaussDB云数据库。
Q：觉得很淦👍并让打开共享屏幕开始撸代码。
A：要退出一下开个权限，然后又接到了来自华为的机器人的无数面试短信和电话。
算法
有序数组二分
int l = 0, r = n, mid;
while (l <= r) { // 这里当时写错成<了，应该是<=
mid = (l + r) / 2;
if (k == a[mid]) {
cout << mid << endl;
return 0;
}
if (k > a[mid]) {
l = mid + 1;
} else {
r = mid - 1;
}
}
cout << -1 << endl;
本来我是最后判断是否是找到的值的，因为l = mid + 1与r = mid - 1会将本来找到的正确值跳过，被纠正把判断等于改到了循环里面。
很久没手写递归了，一般直接调upper_bound和lower_bound用来着。
Q：复杂度？
A：O(log2n)。
Q：分治？
A：把一个大问题分解成同样的小问题来解决。
循环有序数组二分
开始没听懂什么是循环有序数组，拐了弯路。
写了个乱七八糟不晓得在干嘛的代码：
#include <iostream>
using namespace std;
int main(int argc, const char * argv[])
{
int n = 10, a[100] = {7,8,9,0,1,2,3}, k;
int l = 0, r = n, mid;
while (l <= r) {
mid = (l + r) / 2;
if (k == a[mid]) {
cout << mid << endl;
return 0;
}
if (k > a[mid]) {
l = mid + 1;
} else {
if (k < a[l])
l = mid + 1;
else
r = mid - 1;
}
}
cout << -1 << endl;
return 0;
}
面试官：不应该先比较k，应该先比较mid和l看拐点在哪边。
我：确实。那是需要写递归吧，因为不确定k会在哪边。对连续的一边跑普通的二分查找，对循环递增的一边继续刚刚的操作。
哈希
Q：哈希？
A：一一对应的一个算法，通过键值查表。
Q：给一字符串，统计每个字母出现次数？
A：用map存，一个字母一个字母扫，扫到的加个1.
#include <iostream>
#include <string>
#include <map>
using namespace std;
map<char, int> mp;
int main(int argc, const char * argv[])
{
string s;
cin >> s;
for (int i = 0; i < s.length(); i++) {
mp[s[i]]++;
}
return 0;
}
发展思维
二进制
Q：假设有1000瓶液体，其中999瓶是水，1瓶是毒药，外观无法区分。假设你有10只小白鼠和无线多干净的试管，且假设毒药毒性极强，任何稀释都无效，如何在最短时间内找到哪瓶是毒药？
A：给小白鼠编号1-10，给瓶子也编号1-1000.比如第5个瓶子，二进制是101，所以让第1和3号小白鼠喝；这样把1000瓶都给分了。因为1000<210(1024)所以够用。最后看哪几只老鼠死了，根据它们的编号连起来是个二进制数，再转化成十进制就是毒药瓶子的序号。
一致性
Q：假设你是一个将军，你有两个突击小队A和B，现在要攻击一个城堡的南北门，A队已于南门就位，B对已于北门就位。得让A/B小队尽可能同时攻击南北门，发起攻击的时间差不能大于10分钟。
你和A/B直接都有电话线路进行沟通，但是这个电话线路不是安全的，随时有可能被敌人切断联系，A/B小队之间无任何沟通手段，彼此也不知道对方是否发起了攻击，你怎么才能实现这个攻击目标呢？
A：这是个什么方面的问题？虽然我看懂题了但是没懂要问个啥？
Q：就……如果给一个队打电话让进攻，给另一个打时候电话断了就不行。问咋办？
A：？？？那我能不能打电话给两个队都说9点进攻，这样只要9点之前电话有时间好使就行？
Q：嗯，没错就是这么回事。
A：？？？？？（就这）
Q：体现了数据库的一致性……
A：？？？？？？？（我直接迷惑）
后来觉得他应该是想问这：Two Generals’ Problem
反问
Q：做的数据库内核开发？
A：对。ACID四个特性、分布式计算保证事务独立等。
总结
有史以来参加过的最简单的一次面试。
没过多久就通知我过了。
主管面试
形式：ZOOM视频会议
面试
自我介绍
略
算法
Q：有1T的int数，有4G的内存，给它们排序？
A：先排前k个，不断往里进。每k个排一次，再把这些排好的连一起。
Q：复杂度？
A：推算ing……n2log(k)？
Q：但是会经常要访问硬盘，一个没用到的数可能会被反复鞭尸。
A：确实。（但也没想到什么别的）
Q：如果它们都是确实的100个值？
A：用hash map存下它们每个值出现的次数。
Q：100个连续的值？
A：把map改成数组就可以。
Q：（反复引导）是不是落了什么？
A：值%100保证下标>=0。
项目
A：梅开二度
Q：如何保证同一时间大量访问？
A：设隔离级别or加锁。
Q：串行不可取+锁操作没你想像那么快。
Q：预订、借阅都是怎样实现的？
A：6个存储过程。在C++代码里call它们。
Q：事务中间失败了怎么办？
A：不能让它出现这种情况。没执行成功就返回一个未成功，事务回滚。
Q：如果一键不预订直接借了？
A：没设计这个。
操作系统
Q：内核态和用户态区别？
A：忘了。
线性代数
Q：（一个没听清的词）？
A：没听过。
信号与系统
Q：傅立叶变换？
A：把时域图变成频谱图。
Q：如果一个冲击变量它的傅立叶变换是啥？
A：太久了，忘了。
反问
Q：都用些什么知识呀？C++？操作系统？
A：用C写的，操作系统之类的都用一些。
总结
答得不算完美，但很和谐愉快。
结果出得好快，过啦！第二只offer差不多到手了。
没参加今年的EC-Final（所以明天不写题解），打完银川就退役。
不过明天会请来西工大参赛的初中同学吃个饭呀！
