本来投的客户端，简历被刷了，被后端捡起来，没有笔试。一二面连着来的。
一面：
先谈了下项目，这是我秋招来第一次被问到实习具体细节的，别的公司可能没有相关业务,都不会问，捞我的部门好像在做相关的业务，所以问得比较细，可能是这样才捞我的吧。
项目聊得不多，5分钟左右。
然后开始问基础。
c++:
violate关键字的作用，我说不会，所以换了一个static。我就说了静态成员，静态方法，静态变量 等等。然后，难题就来了，问你，如果cpp文件链接了两个库，两个库都含有static int a这个变量，这两个变量会冲突吗？我说不冲突，他问，那如果我想两个库共享这个静态变量呢？这就触及到我的知识盲区了，没答出来。
开始写代码。给你一个字符串a，字符串b, 字符串c,问你，c是不是由a和b交叉形成的？例如，a = "abc",b = "123",c = "a1b2c3",这样叫交叉形成，即a和b的内部顺序不变。
我写了个dfs算法，大概花了20分钟，他问，这个时间复杂度多少，我答错了，应该是2的(max(m,n))次方？
然后一面就结束了。等了20分钟接着二面。
二面：（前方算法课预警！！！）
也是问了一下项目，比较关注的是项目细节，大概讲了10分钟。开始做题：两个有序数组的交集。
我一看，这个我做过啊，洋洋洒洒地写了个哈希+遍历的，他问，你这算法复杂度多少？O(m+n);
他问，怎么优化？我又想了一个，双指针，分别遍历，比较小的指针+1，相同则放入结果集中；但是又问，你这算法复杂度多少？我答错了，答案还是（m+n).
于是，问题又来了，怎么优化？我想了一下，有序，那就遍历a,每个去b中二分查找，但是时间复杂度mlog(n)不一定比（m+n)小啊，怂怂的，不敢说。他顿了顿，这思路还可以，继续，还能优化吗？
还能优化吗？想不出来了啊，空气凝固了5分钟。
他看我想不出来了，提示了下，你在数组B里可以用指针跳过一些不要的数字，你在A里再想想看？
还是想不出来，又沉默了五分钟。他又提示了一下，给了个例子，A={1,2,6,7，23,40,50}，B= {1,2,23，50}，你A里面的6,7还有必要去B里二分查找吗？
哦！是哦！在B里查找到的数tmp，可以再去A那里二分查找，缩小A的遍历范围，就是两个数组之间用二分查找反复横挑！面试官：不错，就是这样，来实现一下吧？
光是编码也有点晕乎乎的，错了好几处，让面试官提示错了的才写好。大致是这样：
首先实现一个函数upperbound(array,int k),返回array中第一个大于等于k的下标。
开始遍历A：
index = 0;
while(index<0){
int first = upperbound(B,A[index]);
if(A[findex] == B[first]){
把值加入结果集中。
index = upperbound( A, B[first+1]);//如果相等的话，如A={2, 23，27}，B = {2,27}，查找2的时候，B的下一个数27应该成为A的下一个起始地点，之间的23不应该再遍历了。
}else{
index = upperbound( A, max(A[index],B[first]);//如果不相等的话，如A={23，25，27}，B = {22,25,28}，查找23的时候，A为23，B为25，下一个遍历的数应该是max(23,25)=25。
}
返回结果集。结束。面试官又问了，这个算法的复杂度多少？我是真的晕了，没想出来，他说：今天就到这里吧。大伙来分析分析复杂度应该是多少？
总结：与其说是面试，不如是面试官给我上了一节算法课，就一个简单的问题，两个数组的交集，能问30分钟，我有20分钟属于茫然状态，啥？还能再优化？啥？还能这样优化？啥？复杂度应该是多少，不知道啊？啥？就结束了？
面试官多番提示，我还是要缓好久才能明白他在说什么，这就是我跟字节大佬的差距吗。想不凉都难。
。想不凉都难。 PS：答成这个鬼样，后续还有可能被其他部门捞吗？该不会面试官的评语就是“榆木脑袋，不可雕也”，我还能投其他岗位吗，流下了菜的泪水。
全部评论
(7) 回帖