有了上次字节面试的失败经验，这次面试Unity便从容了许多，保研复习的这段时间，虽每日勤勤耕耘，但内心颇有不安，一是为身边的同学都找到了实习而焦虑，怀疑自己笨，学不会东西，学了容易忘等等，虽然有论语中“不患无位，患所以立”的言语鼓舞，但始终只是尽力维持内心的一个平衡状态，给我精神上的安慰而已；二是预推免日迫近，担心自己的各方面能力不如别人，预推免名额又很少。这种情况下，我难免产生了自我怀疑，我所决心要走的路，真的能换来我期望的结果吗？我的努力，真的配得上我的梦想吗？我一直在强调的成长，会不会只是我自我欺骗的一种方式，让我只局限于规划的自我感动里，抓不住时代的机遇呢？经过昨天的现场面试，并基本当场给offer，我心里憋着的气一下子就顺了，畅然舒怀之感贯通全身，好像我之前的所有努力，所有痛苦都make sense了，我的努力是有价值的，我是在不断成长的，我不比别人差，我能靠我的努力取得我想要的结果，我能靠我的努力换来我想要的生活，我相信这次的经历能让我以更加自信的姿态去准备保研，规划未来。

上次面试字节的时候刚开始做动规的算法题，虽然没考到动规，但是由于前面的滑动窗口，数组链表已经忘记很多了，所以面试表现不是很好。一周来我基本上每天刷5-10道动规，对背包问题，打家劫舍问题有了比较深入的了解，刷完动规之后我也会专门以我的方式总结这些问题，当我刚开始刷买卖股票问题时，Unity就通知面试了，结果考的算法题还真就是买卖股票，但是我其实只看过最基础版本的动规，甚至没编过代码，所以当面试官说出这道题的时候，一方面我庆幸是刚看过的题，还有些印象，另一方面我又很悔恨，为什么当初没有刷完这个主题再来面试，搞得现在我只知道dp数组要怎么创建，但完全不知道有冷冻期的股票要如何状态转移和更新，所以就只能现场推了。

第一轮面试

面试分为两轮，耗时大概两个小时（我做题比较慢，正常时间大概是一个半小时）第一轮是技术面试，面试官上来先让我做了自我介绍，因为是面试测开岗，所以我就比较偏重介绍软件工程和软件测试课程项目的经历，面试官也围绕着我引导的方向走，问了我一些软件工程和软件测试的问题。问了我们的项目有没有用自动化测试工具，还是说要手动去测试，我说我们的集成测试是可以点击一个按钮自动去测试所有测试用例的，第一个面试官对这点倒是没继续延伸，然后因为我是项目组长，就问我团队协作的问题，如果有问题我不会的我是如何解决的，我说了我们是敏捷开发，会有一个例会，经常沟通进度，然后用Jira做项目管理，如果有技术问题，那么我们会互相交流，互相学习；如果是分工和课程要求的问题，我会求助其他组的组长或者老师，我确实是这么做的，她听下来觉得也挺满意，就没继续问了，总之对于项目经历, 由于我在自我介绍的时候就已经挖好坑了，基本是对答入流。

之后就开始做题环节，就是上面说的买卖股票系列，我只看了最基础的，想着这最基础的用贪心不比动规方便多了，动规方法我也只看了个大概，面试官还很nice地说，如果你没做过，我们可以换一道，但是毕竟我是看过一点了，换一道可能还更难或者我不了解了，索性就硬着头皮推吧。

她上来直接说了有冷冻期，但是我为了展示我对于这个系列的题目的了解和认识，还是从最基本的给她推起，希望能 buy me some time，来思考冷冻期应该怎么做。正好借这篇面经把这个系列的题解写了吧。

买卖股票 - 一次购买

买卖股票问题的基础就是给定一个vector数组，每个数字都是当天股票的价格，可以以当天的价格买入或者卖出，对于不同的买入卖出限制，求出能取得的最大利润。

最简单的一种情况是：只能买入一次，卖出一次。这种情形很好用贪心法解决，只要找到最低点，最高点，在最低点买入，最高点卖出就好了，一次遍历就可以实现。

1
2
3
4
5
6
7
8
9
10
// 贪心
int maxProfit(vector<int>& prices) {
    int minVal = INT_MAX;
    int maxProfit = 0;
    for (int i = 0; i < prices.size(); i++){
        minVal = min(minVal, prices[i]);
        maxProfit = max(maxProfit, prices[i] - minVal);
    }
    return maxProfit;
}

只需要设置两个变量，minVal和maxProfit即可求出来了。

如果用动态规划方法的话，需要理解：对于某一天结束的时间点来说，状态无非两种：持有股票和不持有股票，这两种状态分别都可以从前一天的持有或不持有转移过来，所以我们可以为每一天设置一个二维的数组，存放持有或者不持有股票，对应的最大利润，最后输出最后一天的不持有股票获取的利润即可。

至于dp数组的递推，第一列的含义是某一天结束后状态是持有股票所付出的最少钱，显然状态更新的过程就是贪心地找最低点的过程，第二列是当天结束之后状态为不持有股票赚得的最多利润，这一过程其实就是在确实遍历过程中的maxProfit

IMG_CAC3D22FDBB3-1

1
2
3
4
5
6
7
8
9
10
// DP
int maxProfit(vector<int>& prices){
    vector<vector<int>> dp(prices.size(), vector<int>(2,0));
    dp[0][0] = -1 * prices[0];
    for (int i = 1; i < prices.size(); i++){
        dp[i][0] = max(dp[i-1][0], -1 * prices[i]);
        dp[i][1] = max(dp[i-1][1], dp[i-1][0] + prices[i]);
    }
    return dp[prices.size() - 1][1];
}

买卖股票 - 无限制购买

接下来难度升级，不限制买入卖出次数，此时用贪心算法也很简单粗暴，直接把所有能赚钱的上升阶段都赚到手，就是最大利润了。

1
2
3
4
5
6
7
8
9
10
11
12
13
// 无数次购买，贪心
int maxProfit(vector<int>& prices) {
    int profit = 0;
    int i = 0;
    while (i < prices.size() - 1){  // 当i == prices.size() - 1的时候，最后一个元素已经处理完毕，可以退出循环
        while(i < prices.size() - 1 && prices[i+1] <= prices[i]) i++;
        int low = prices[i];
        while (i < prices.size() - 1 && prices[i+1] >= prices[i]) i++;
        int high = prices[i];
        profit += high - low;
    }
    return profit;
}

如果用动态规划，和之前的方法的区别最大的一点就是：如果某一天结束后的状态是持有股票，而且这个状态是买入来的话（即，前一天不持有），因为能多次买入，所以我在更新第一列的时候，可以无数次地考虑从不持有到持有的过程, 所以状态转移公式变为：

IMG_D8DEBDFCAA75-1

1
2
3
4
5
6
7
8
9
10
// 无数次购买，DP
int maxProfit(vector<int>& prices){
    vector<vector<int>> dp(prices.size(), vector<int>(2,0));
    dp[0][0] = -1 * prices[0];
    for (int i = 1; i < prices.size(); i++){
        dp[i][0] = max(dp[i-1][0], dp[i-1][1] - prices[i]);
        dp[i][1] = max(dp[i-1][0] + prices[i], dp[i-1][1]);
    }
    return dp[prices.size() - 1][1];
}

买卖股票 - 两次购买

如果限制只能买入两次股票怎么办呢？沿用当前的数组肯定不行，因为没法控制买入多少次，所以我们需要加状态，对于某一天结束这个时间点，可能是 没有买入任何股票，买入了第一支股票并持有但还没买第二支，卖出了第一支股票但还没买第二支，买入了第二支股票并持有，卖出了第二支股票这五种状态，所以对于每一个时间点都设置一个五维的数组。由于第一个状态只能由第一个状态转移而来，其值一直是0，所以我们可以只设置一个4维数组即可。

IMG_D54A3BB34AEA-1

1
2
3
4
5
6
7
8
9
10
11
12
// 两次购买，DP
int maxProfit(vector<int>& prices){
    vector<vector<int>> dp(prices.size(), vector<int>(4,0));
    dp[0][0] = dp[0][2] = -1 * prices[0];
    for (int i = 1; i < prices.size(); i++){
        dp[i][0] = max(-1 * prices[i], dp[i-1][0]);
        dp[i][1] = max(dp[i-1][1], dp[i-1][0] + prices[i]);
        dp[i][2] = max(dp[i-1][2], dp[i-1][1] - prices[i]);
        dp[i][3] = max(dp[i-1][3], dp[i-1][2] + prices[i]);
    }
    return dp[prices.size() - 1][3];
}

买卖股票 - k次购买

与上面的两次购买同理，只需要扩展dp数组即可。

1
2
3
4
5
6
7
8
9
10
11
int maxProfitIVDP(int k, vector<int>& prices) {
    vector<vector<int>> dp(prices.size(), vector<int>(2 * k + 1, 0));
    for (int i = 0; i < k; i++) dp[0][2 * i + 1] = -1 * prices[0];
    for (int i = 1; i < prices.size(); i++){
        for (int j = 0; j < k; j++){
            dp[i][2 * j + 1] = max(dp[i-1][2*j+1], dp[i-1][2*j] -1 * prices[i]);
            dp[i][2 * j + 2] = max(dp[i-1][2*j+2], dp[i-1][2*j+1] + prices[i]);
        }
    }
    return dp[prices.size() - 1][2 * k];
}

由代码我们可以看出，加上第一列的不操作其实是简化了循环中的代码量，让我们不用再考虑第一次买入时的特殊情况。

从这里我们已经可以看出，为什么最开始的只能买一次和无数次，设置的两个状态为持有和不持有，当k -> 无穷，每一次买入都可以考虑把上一轮卖出的重新买入，可以把所有的买入列和卖出列合并，状态变为： 某一天结束以后是第n次买入且持有但还没买第n+1次的·状态（n不用管，只需取最大的利润值），既然n不用管，那就是持有的状态，同理卖出合并之后就是不持有的状态，这样就统一理论了。

买卖股票 - 含冷冻期

如果不限制买入卖出的次数，但是如果卖出之后的紧接着一天股票会进入冷冻期不能买入，这个时候可以获得的最大利润是多少呢？

面试的时候考察我的就是这题，现在想来这道题其实挺难的，虽然说不用分第几次买入卖出，但是卖出的下一天是冷冻期这个概念却不好划分状态，当时我和面试官说完最基本的 持有股票和不持有股票两种状态之后，面试官又提示我说，可以把不持有股票继续划分一下，不持有股票且处于冷冻期，不持有股票且不处于冷冻期，我后来按照这个划分推出来了状态转移公式，解释了一遍，自己编程实现，然后设计了一组测试用例现场给面试官说之后，问题基本上解决了。

但是现在回想起来，面试的时候我其实没有做全对，而且刚开始想的时候，除了上面三种状态，还需要添加一种状态，即在当天结束的时候，是不持有股票且卖出的状态，因为处不处于冷冻期是卖出这个动作决定的，所以加上这个状态之后，状态转换就很方便了。

截屏 2024-08-18 11.44.04

1
2
3
4
5
6
7
8
9
10
11
12
// 含冷冻期
int maxProfitCool(vector<int>& prices){
    vector<vector<int>> dp(prices.size(), vector<int>(4,0));
    dp[0][0] = -1 * prices[0];
    for (int i = 1; i < prices.size(); i++){
        dp[i][0] = max(dp[i-1][0], dp[i-1][3] - prices[i]);
        dp[i][1] = max(dp[i-1][0] + prices[i], dp[i-1][1]);
        dp[i][2] = max(dp[i-1][2], dp[i-1][3]);
        dp[i][3] = max(dp[i-1][3], dp[i-1][1]);
    }
    return max(dp[prices.size()-1][1], dp[prices.size() - 1][3]);
}

买卖股票 - 含手续费

这种变体相对简单，只要在每次卖出的时候减去手续费fee，更新dp数组即可。

1
2
3
4
5
6
7
8
9
int maxProfitFee(vector<int>& prices, int fee) {
    vector<vector<int>> dp(prices.size(), vector<int>(2, 0));
    dp[0][0] = -1 * prices[0] ;
    for (int i = 1; i < prices.size(); i++){
        dp[i][0] = max(dp[i-1][0], dp[i-1][1] - prices[i]);
        dp[i][1] = max(dp[i-1][1], dp[i-1][0] + prices[i] - fee);
    }
    return dp[prices.size() -1][1];
}

我做含有冷冻期的题花了挺长时间，面试官也没继续问了，就问我还有没有其他问题，根据我的经验，这一环节必须要找点东西问，以此来表达对职位的热情以及兴趣，于是我就询问了一些关于之后做的岗位的具体工作什么的，由于一面只是一个技术工程师，所以就也没有说很多，只是说有很多细分的方向可以做，说接下来是我们的leader面你，他对每个工作方向都懂，然后就进入下一轮面试了。

第二轮面试

第二轮面试开始，leader进来，我站起来，让他先坐，客气客气。然后开始自我介绍，我就开始背，然后他很自信，很胸有成竹，在我说到他感兴趣的地方的时候打断我问问题，问题简明扼要，直击重点，很有leader气质。

问了我单元测试是怎么做的，用什么可视化，有没有做自动化测试，我说java Junit做设计测试用例，用allure做测试可视化，但是对单元测试来说还是要点击按钮才能测试，并没有做那种更改了代码之后自动上传，自动测试那种，他说没关系，至少是知道，然后我还说了jenkins的基本原理，我知道一般是修改代码传到Github，jenkins服务器拉取代码，自动构建，自动部署到tomcat服务器上，然后测试工程师进行测试。其他还问了性能测试是怎么测的，我说用Jmeter去模拟发API，他问我TPS是多少，我其实不是很清楚TPS是什么（事务数每秒），然后我就说了下其他指标，响应时间，吞吐量啥的。

再之后又是一道算法题，但是比较特别，是一道英文题目，描述也很简单，生成在某个范围内的不重复的k个随机数，我第一反应就是用库函数randint，但是这种方式会生成重复的随机数，我就想到可以用哈希表来查询生成的随机数是否重复，但是如果k比较大的话就会生成很多个重复的随机数，这时候他提示我：就像一个抽奖箱一样，每次从箱子里拿一个数字出来，只要不放回去，就可以做到每次拿不同的随机数，所以说可以用一个数组存放这个范围内的所有数字，每次生成一个随机数，把最后一个数字和抽到的对应位置的数字交换，再把数组容量缩小1即可。之后我问了问GPT，GPT说其实只要随机打乱数组（fisher-Yates算法，从最后一个数字开始，随机取前面的数字与其交换，直到遍历到第一个数字），取前k个数字即可，我觉得这也是一种很好的方法。

在面试的时候这个题我并没有表现的很好，虽然说在他的提示下我想到了用容器存取这个生成的数字，每次取一个随机数，删掉这个元素，但我没想到数组和交换的道理，我想到用链表比较好删除节点，但是现在想来用链表还是太蠢了，也能看出来我对于这种基础数据结构的应用还是比较欠缺，经验不足。

一些感想与教训

这次的Offer给了我极大的鼓舞，但也暴露了许多问题。

首先就是我对于基础数据结构的不熟练，有套路的动规我相信能够应付得来，但对于一些比较灵活，考察思维的算法问题，我就难以应对。一方面可能是我反应比较慢，没法很快地想到对的解法，如果说这一点我没法改变的话，也许我可以在生活中多思考，多丰富自己对世间规律的经验，我相信积少成多，积跬步以致千里。

其次，面试礼节与引导。首先要有礼貌，让面试官先坐，和面试官先聊天，扯两句家常，要精心针对面试的岗位设计自我介绍并能够背下来，这样能够很好地引导面试官，甚至能够奠定整场面试的基调。对于自己不会的问题，一定不要说“记不清楚了”这种就没下文了，把自己所知道的一五一十地告诉面试官，然后礼貌地说：“不好意思，对于。。这块内容，我复习的不够充分，下来我会注意把这部分知识补齐的”让面试官知道，我对于这部分知识还是了解一部分的，只是刚好ta问到的那部分不太清楚，这样至少不会很减分，也会让面试官觉得是一个有礼貌，懂沟通，勤上进的人。

再次，人生是自己的，要把自己的生活写成诗，活得精彩，就不能盲目地跟从，或者被他人的声音主导，大多数时候，我们需要敞开胸怀，倾听不同的声音，吸收他们的优点，让自己成长，但是对于那些有决定性意义的瞬间，我们要学会倾听自己内心的声音，不要被外界的声音主导，我很喜欢《爱乐之城》Mia试戏时唱的： A bit of madness is key, 一点点疯狂，一点点固执，能够让我们活出自己生命的意义。这一点在我高中平行班考试的时候，在我大学上选选修课的时候，在我降级选择德强班的时候，在这次面试的时候，都有印证。

image-20240817113815397

最后，无论人生是起是伏，是贫是富，是顺是逆，有一点不会变： 路漫漫其修远兮，吾将上下而求索。

后面的人生，会更精彩。