蓝湖一面

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函数里的，过了一秒觉得不妥封装成函数，面试官也提醒封装一下。开始写：

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)。
  于是开始写代码：

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通知一面过了，约了明天下午的二面。