FB面试经历，已拿offer，希望能帮到更多的人

cacofish 发表于 2016-9-12 07:44
最后一个M+N 怎么计算的？我想了半天，每过A的一行第二个指针得退回到开始位置，感觉无法算出M+N

因为两个vector都是排好序的，遍历一个长度较短的vector，所以如果在找第一个vector里面下标是10的元素，现在发现找到第二个vector下标大于10的时候还没有找到，其实就不用往后找了。同理，如果在第二个vector中找到了匹配的元素，那么下一次搜索第二个vector的时候就不需要从头开始搜索了。这样子的话，两个vector里面每个元素都只会被访问一遍，不知道这么说，你能不能明白。

hkc593 发表于 2016-9-12 08:21
请问dot production是不是要求两个vector的size一定是相等？A.B = A1*B1 + A2*B2 +.... An*Bn. 这样不是O(n ...

size不是相等的，两个vector中绝大多数元素都是0，不需要一个一个相乘想加

补充内容 (2016-9-12 08:32):
呃……说错了，size是相等的，但是由于他们都是sparse的，不需要一个一个相乘相加

楼主真厉害！今年明明不是好年楼主还去了这么棒的公司，而且还是强转！
佩服啊~

slashGu 发表于 2016-9-12 08:26
size不是相等的，两个vector中绝大多数元素都是0，不需要一个一个相乘想加

补充内容 (2016-9-12 08:32): ...

如果input是已经process好的index到value的map。这样也只要遍历一个map就好了，是这样吗？

int dotProduct(unordered_map<int, int>& A, unordered_map<int, int>& B) {
   int sum = 0;
   for(auto it : A) {
      int idxA = it.first;
      if (B.find(idxA) != B.end())
          sum += it.second*B[idxA];
   }
   return sum;
}

hkc593 发表于 2016-9-12 09:05
如果input是已经process好的index到value的map。这样也只要遍历一个map就好了，是这样吗？

int dotPro ...

unordered_map是无序的，我当时用的是vector<pair<int, int>>来存储vector里面非零元素的index和value

补充内容 (2016-9-12 09:19):
还有一点就是unordered_map需要占用比较多的内存空间，所以这里还是选择用vector来存pair比较好

补充内容 (2016-9-12 09:23):
当然，你这么写也可以，可以跟面试官交流，看看有什么地方需要改进的

恭喜楼主！！！！请问楼主有项目或实习经历吗

winterfly 发表于 2016-9-12 09:16
恭喜楼主！！！！请问楼主有项目或实习经历吗

多谢！去年在EMC做过Co-op

AlexPinhead 发表于 2016-9-12 08:59
楼主真厉害！今年明明不是好年楼主还去了这么棒的公司，而且还是强转！
佩服啊~

多谢多谢，也是运气好

楼主你说的每写完一个程序就出一个test case验证一下，是说对于主程序还是说所有的包括helper method之类的，有时非常common的helper method，比如swap, reverse，之类的还需要给出test case验证吗，还是说是那些更加复杂的helper method，这些需要给出test case？多谢！

samuelling 发表于 2016-9-12 10:22
楼主你说的每写完一个程序就出一个test case验证一下，是说对于主程序还是说所有的包括helper method之类的 ...

你好，我自己是在有些边界情况比较难一眼就看出来的时候，会写一个test case来验证一下，一般这些地方比较容易会有一些corner case。其他逻辑很清楚的，就在大脑里面过一下就行了，除非面试官指出来说要你口头编译一遍给他听。