面试经验｜蓝湖c++后台开发实习一面、二面、三面整理
蓝湖一面，一小时，1.26下午三点
1. 自我介绍
2. 面试官介绍面试流程：算法、项目、基础
3. 问代码量有多少
4. 平时都怎么提升编程水平，答做算法题
5. 算法，先难后易，难的做出来就不用做简单的了
问：麦当劳有三种鸡块包装，分别装`7`，`13`，`29`块鸡块，让你去买`n`块鸡块，问能不能买到。
答：先分别计算`n%7`，`n%13`，`n%29`是否为零，如果是返回`true`，否则枚举`abc`，看是否存在`7a+13b+29c＝n`，存在返回`true`，否则返回`false`。
问：有其他方法吗
答：动态规划，定义`dp[i]`为`i`是否能买到，能买到就为`true`，否则为`false`，初始化`dp[i]`为`false`，`dp[7]`,`dp[13]`,`dp[29]`为`true`。之后进行一次遍历，只要`dp[i-7],dp[i-13],dp[i-29]`其中之一为真，`dp[i]`即为真，否则为假。
问：行，那你实现一下代码。
打开`ide`写代码。本来想写在`main`函数里的，过了一秒觉得不妥封装成函数，面试官也提醒封装一下。开始写：
```cpp
bool isCanBuy(int n) {
vector<int> hash = { 7,13,29 };
for (const auto& h : hash) if (n % h == 0) return true;
vector<int> dp(n+1, 0);
dp[7] = 1;
dp[13] = 1;
dp[29] = 1;
for (int i = 7; i <= n; ++i) {
if ((i - 7 >= 0 && dp[i - 7] == 1) ||
(i - 13 >= 0 && dp[i - 13] == 1) ||
(i - 29 >= 0 && dp[i - 29] == 1)) dp[i] == 1;
}
if (dp[n] == 1) return true;
else return false;
}
```
- 写完准备`main`函数里写测试，面试官说不必了，主要是这个函数的实现。
问：时间复杂度是多少？
答：`O(n)`，只需要遍历一次`7-n`即可。
问：有没有一种可能，当`n`大于某个`k`之后，所有的`n`都能购买到，也即，当大于某个数之后的所有数都可以表示成这三个质数的和
答：`emmm`，你说的有道理，但是这个数是多少呢，我想想。可以先用现有算法建表，也即，从`29`开始一直测试`n`是否满足条件，当出现连续多个，比如一百个`n`都满足条件时，我们就有理由认为之后的所有数都满足条件，当然`100`不一定准确。
问：那这个连续数是多少呢
答：暂时想不到，是三个质数的乘积或者他们的最小公倍数吗，面试官说不是。
问：实际上是`7`.
答：。。对哦，我是***，一时没想到，实际上一旦连续`7`个数都满足条件，那么之后的任意数都可以用这`7`个数连续加`7`得到。
问：行，那你实现一下先找`K`，这样大于`K`的情况都是`O(1)`，我们可以将时间复杂度降为`O(K)`。
于是开始写代码：
```cpp
int findMinK() {
for (int i = 29; ; ++i) {
if (isCanBuy(i)) {
bool isK = true;
for (int j = i; j < i + 7; ++j) if (!isCanBuy(j)) isK = false;
if (isK) return i + 6;
else i += 6;
}
}
}
```
- 问：看看你的代码是不是还可以优化，是不是浪费了什么信息
答：`emm`，没用到`7,13,29`吗？
问：你每次`isCanBuy`都要重新计算`7-i/j`，实际上是不是可以保存以前计算的结果，降低时间复杂度
答：对对对！（内心`os`，我真***，咋这都忘了），那我写一下
问：先不用了。实际上，我们现在就实现了`O(K)`的时间复杂度。行，算法考察先到这里。
6. 说一下`c++`多态
答：静态多态，动态多态，继承，虚函数，重写，父类指针/引用指向子类对象，虚函数表，虚表指针，派生类虚表，纯虚函数，抽象类。本来还想说一下虚析构，协变，为什么没有虚构造，但是感觉说得不少了，就没说了。`override`跟`final`倒是没想起来。
7. 说一下堆和栈
答：栈是操作系统管理，地址连续，堆由程序员管理，地址不连续，管理不好内存泄漏。
8. 你提到堆区容易内存泄漏，`c++`里有智能指针解决内存泄漏问题，你说一下`c++`里的两种智能指针
答：面试官实际想问`unique_ptr,share_ptr`，我提了一嘴之前还有`auto_ptr`，后来弃用了，然后分别说了一下`unique_ptr,share_ptr`，之后说到`share_ptr`的循环引用问题，又介绍了用于解决循环引用问题的`weak_ptr`。
9. 说一说项目，自己挑一个说，着重说说项目意义，要解决什么问题，用了什么技术，有哪些困难，都学到了什么。
答：吧啦吧啦。
10. 你对我们公司了解多少
答：不太多，之前打周赛看到的，投简历时也了解了一下。
11. 比赛？都取得过什么好成绩吗
答：没有，主要是练习一下限定时间状态下的编程水平，看看会不会紧张，发挥失常什么的。
12. 反问
答：这个项目主要做什么，面试官说了很多，包括这个项目，他们公司，用的技术栈。我最后问了问我有什么还需要加强的地方吗，答继续夯实`c++`基础和计算机底层原理，学一下`webassembly`，还有计算机图形学相关的东西。
然后就结束了，十分钟后`hr`通知一面过了，约了第二天下午的二面。
蓝湖二面，30分钟，1.27 下午三点半
1. 自我介绍。
2. 学校在哪，北京这么远能来吗？
3. 你感觉自己算法学得怎么样？
答：自己评价可能会跟真实水平存在较大偏差，我个人感觉的话，一般吧。
4. 行，那考考你，知道哪些排序算法？
答：冒泡，选择，插入，希尔，归并，快排，桶，（被打断了，不然我可能会讲到猴排hhh）。
5. （打断）说一说归并排序吧。
答：（被突然打断一下子就卡了，诶，归并排序是啥来着，就想不起来了。因为面试最容易要求手写快排，实际上看得最多的还是快排，其他这些排序长时间不看的话很容易忘记）额，一下子有点卡壳，好像跟快排搞混了，您让我想几秒。（过了几秒）归并排序分多路归并跟二路归并，这里以二路归并为例，吧啦吧啦。。。
6. 你说到需要对两个有序数组进行合并，实际上就是`merge`过程对吧，对n个数进行排序，需要`merge`几次？
答：（这里是表现最不好的，实际上就是个数学问题，但是可能是因为太紧张，表现实在是太差了）啥也不干脑子想想上来就先猜一个，面试官说不是，然后又想，完了面试官说你可以从一个具体的`n`开始分析，比如`n=16`的时候，`merge`多少次。于是开始在纸上画。好几次都沉不下心来，全过程还没分析完就乱写求和，导致错了好几次，到后面分析结束，得出实际上是首项为`1`，末项为`n/2`，公比为`2`的等比数列的和，完了面试官问最后答案是多少，哦豁，等比数列求和公式想不起来了。。。面试官看出来了，就说，行，那先跳过求和这个问题。实际上你求的答案是不是仅针对`n`为`2`的整数次方的情形，那对于任意`n`呢，答暂时想不到。然后面试官说行，那算法考察先到这里。
7. 职业规划。
答：c++方向的后台开发，客户端也行。
8. 最近在学什么，有什么比较有收获或者说让你眼前一亮的知识吗（这里估计想考察对技术的热情）？
答：主要是与开题相关的学习，吧啦吧啦。（然后觉得这不应该是要说的重点，又说每天都有坚持做算法题，学习算法）然后面试官又问了一遍，有什么让你眼前一亮的学习经历吗。我就讲了之前做的一个题，[LC169多数元素](https://leetcode-cn.com/circle/article/63C1Zt/)，讲摩尔投票法特别让我眼前一亮，我先讲了自己想的三种方法，排序，哈希，随机算法，最后着重描述我初次看到最优算法时那种让我眼前一亮的感觉，然后描述了算法具体内容。不过可能讲述逻辑不太对，没太讲清楚。
然后面试就结束了，5分钟后`hr`说二面通过了，约了晚上三面。
蓝湖三面，30分钟，1.27 晚上 七点半
晚上七点半三面hr面，主要是谈人生谈理想，谈到最后说我过了，希望我能在年前给答复。
查看14道真题和解析