头条算法

这场是视频面试，不仅我没有经验，看起来面试官也没有视频面试的经验。总体感受下来，还是觉得视频面试相比现场面试是有劣势的。一则视频面试时，想要解释一些概念无法通过简单的数学公式来表达，只靠言语又显冗余累赘；二则面试中思考的过程无法实时同步给面试官，无论是写代码还是推公式，其间面试官只能百无聊赖地等；其三个人感觉视频面试有点怪异的尴尬，眼睛都不知道该看哪里，大概想问题时到处乱看会被当成作弊吧。

三轮面了四个小时，能回忆起来的问题记录如下。

• 一上来就手撕代码，开根号。以前没遇到过这个问题，于是写了二分查找。面试官问会不会牛顿法，现场推了下公式，结果牛顿法太久不用公式都忘了，用泰勒展开推了一下写成了拟牛顿法。。。面试官说你这个写的不太对吧。。。捂脸
  

这里倒是可以回忆下当时的思路，如果用牛顿法来优化的话，目标函数可以写成，其中y是给定要开根号的数，x是要求的数值。这个式子显然是convex，求下来一阶导为，牛顿法更新的时候应该是迭代，其中f(x)就这我们的这个convex的目标，那么更新迭代的公式应该是。其实就这么简单，当时一紧张就稀里糊涂地把目标函数求了Hessian然后求逆乘以梯度。。。蠢到螺旋***莫过如此。。。 

• 问了Adam优化和attention机制，前者我认为自己门清，然而纯粹用语言来说确实不容易说清，如果是现场面试的话列出那六个公式解释下就完了，然而视频面试很可能说了一堆不知所云的废话；后者我确实不了解，说了下soft attention和hard attention，soft attention其实我自己都搞不清，太失败了。。。
• 由于简历上有dense CRF和LevelSet，面试官让解释一下——又是不写公式说不清的东西。答曰结构化预测云云，欧拉拉格朗日方程解出最优迭代方向云云，面试官问dense CRF如何优化，回曰变分平均场近似，面试官看起来很迷茫。。。这部分面试就充分体现了学术界与工业界的脱节，贝叶斯学派应该算是比较典型的案例，理论十分优雅然工业界不温不火。
• 继续手撕代码，二维数组找最长递增路径。很简单的题，DFS即可。唯一需要注意的一个小细节是由于求的是递增路径，所以相比标准的DFS写法，不需要那个visit数组来标志某一节点是否访问过。
• 依然是手撕代码，链表采样，resevior sampling，LeetCode原题。要求在一个无限长的单向链表中采样，当遍历的节点数量充分多时，每个节点被采样到的概率应相等。思路有点trick，在面试官的提示下想出来了。。。
• 问TensorFlow如何实现并行，我讲了下PS架构，又问梯度更新时是同步还是异步，同步异步的优缺点。最后问到优缺点说明面试官经验还是非常丰富的，刨根问底可以看出你是否真的深入思考过这个问题，抑或是从别人博客看来的人云亦云。
• 三面老板出场，问GBDT原理，然后具体问了下每个叶子节点是怎么分裂的，用什么标准决定最优特征，答曰和CART一样，用Gini指数，然后写了下Gini指数的公式。老板看起来不甚满意，估计他本来想让我写的是xgboost那种带正则项的节点分裂方式吧。
• 优化搜索引擎时，如何从用户的行为上判断用户对我们提供的搜索结果的满意程度？很实际的问题，但对我而言是完全陌生的领域，估计研究推荐系统的人都懂这个，我当时绞尽脑汁：如果用户经常点开的链接不是第一个结果，而是后面的若干结果，那么说明用户对结果不满意。
• 三面手撕代码，两个排好序的数组，找中位数。这个题如果复杂度O(n)就没意义了，显然是要求写O(log n)的二分查找，写法有点trick，写了半天没写出来，在这道题中我的菜鸡本质显露无疑。

百度架构

这场面试是C++的架构。面试过程感觉百度的面试官确实非常厉害，工程经验非常丰富。这也使得我在这场面试中大有收获。

与头条的面试类似，百度的面试官也很有经验，十分擅长通过面试细节问题观察你简历是真实还是吹牛，很擅长判断你是真的有从事过相关领域的工作还是临时抱佛脚背了一堆面经。

还能记着的问题总结如下。

• C++的内存有哪几种，堆和栈的区别；
• 函数重载底层如何实现——根据形参重命名——除了形参还看什么——（绞尽脑汁）const也被考虑在重载范围内；
• 哈希表如何解决冲突，各种解决冲突方法的优缺点。举微博用户为例，分析工程实现上应该怎么做，哈希函数应以谁为键谁为值，更具体地说，应该用用户的哪个字段为键效率最高（int比char*效率高，字节对齐balabala）；
• 如何实现一个无锁的哈希表（可以用atomicCAS做一些简单的原子加减法）——详见java的concurrentHashMap，对java不熟悉，没答上来；
• 实现char* strdump(const char*)字符串拷贝，实现int str2int(const char*)字符转数字，要求考虑各种corner case，代码鲁棒性要高——比如当时我写的代码，我本以为已经考虑了足够多的异常情况了，结果漏掉了new会抛异常这个问题。实际上这个题目说明想要把代码写鲁棒还是蛮不容易的，尤其是LeetCode或者是ACM那种刷题方法，往往只以AC为目标，长期来看是不利于工程代码习惯的培养的。此外这两题我还有不少corner case没注意到不表；
• 当天最让我想钻地缝里的一道题：threeSum。。。我居然写了个O(n^2 log n)的出来，仅最里层用二分查找优化了下，堪称程序猿中的耻辱了。。。
• 问C++11对多线程的支持，有哪些类和函数对多线程提供支持，生产者消费者模式读写buffer；
• 问智能指针实现原理，优缺点，什么时候应该用什么时候不该用；大型项目中指针管理非常复杂，内存泄漏难以避免的时候是否应该用智能指针（我觉得这个是开放性问题）；什么样的代码习惯可以避免内存泄漏，如何查有没有内存泄漏；
• new operator的原理，boost里面那个内存池的原理，什么时候应当用内存池；
• 手写一个类中若干函数的函数签名，比如operator=、拷贝构造和移动构造，问深拷贝浅拷贝的区别，为什么operator=要返回一个*this；
• select、poll和epoll的原理和区别，从浏览器访问一个网址按下回车开始到浏览器把网页渲染结束，中间经历了哪些过程，用到哪些协议——可怜我考完研就忘到九霄云外的计算机网络，唯一一个想起来的DNS还是被提示的，绞尽脑汁思考的时候ARP、ICMP这些莫名其妙的词汇在我脑子里乱转，就是想不起来它们是干什么用的；

有点意外没有问template，之前因为简历上写对STL很熟悉，怕被问template看了好几天的STL各种源码细节、全特化、偏特化甚至是模板元编程。可能用的不多吧。。。

算法整体问得比较简单，可以说比算法岗的要求还低不少。比如还问了个堆排序，可以说是很基础了。

此外还会问很多工程经验的问题，很实在，比如上面怎么避免内存泄露的问题，还有问有没有写过unit test，有没有看过XXX的源码，有没有做过源码笔记，Linux上用过vim没有，有没有装插件，还有Linux上的若干命令。做过就能答得来，没做过只能胡诌。