百度实习生面试总结

啊。。。虽然结果还没出来。。。不过回想发现有些细节已经有些记不清了。。。

所以打算先记录一下？ 就算过不了。。。也算是积累一些经验。

一面：

先是简单自我介绍。。。

然后问了2-sum...?(。。。我之前真不知道这是套路题。。。花了较长时间。。。被面试官姐姐（or适牛？）吐槽不够smartQAQ

姐姐表示没听过。。我说就是two-pointer...之后要求我实现一下尺取做法的代码。。。

有点久没写尺取竟然写残了。。。？面试官姐姐看了之后说。。。你的two pointer 怎么head和tail都在一端啊。。。不应该在两端吗。。。我表示喵喵喵喵喵？ 我写了好多尺取都是在一端。。。不过这倒是提醒了我。。。改对了代码。。。一头一尾。。。难道说这不叫two pointer? 还是说。。。尺取和two pointer根本不是一个东西。。。

之后好像问了道有很多人买5元一瓶的饮料。。。但是有一半人手里是有5元钱的，有一半人手里只有10元。初始饮料店老板手里没钱。。问合法的方案数？

听懂题目以后直觉和母函数有关系。。。就试探性问了句面试官姐姐。。。

发现果然是对的。。。然后面试官姐姐直接就说出了关键字catalan数....说是本打算让我自己推倒一遍的。。。

嗯。。虽然当时啃《组合数学》的时候母函数这部分我看得很细。。catalan数也是ACM题目的常客。。。。以及16年以前网上能找到的普通型母函数和指数型母函数的题目我基本A光了。。。但是感觉真让我推一遍。。。在面试的紧张气氛里。。。说不定就gg了。。。。。

好像算法题就这两个？

之后好像问了一个。。。大概是说同一个新闻可能会被不同站点报道。。。怎么去判断两个新闻稿件的相似度。。。

我说新闻稿件一般都会有图片。。。一张图片某些关键信息可以作为该图片的特征值。。。一般会有多张图片。。。然后算个n维向量的余弦值。。。。

然后文字部分。。。首先stop word什么的肯定要去掉。。。然后同一个新闻的不同稿件。。。时间地点人物什么的都应该一样。。。没有意义。。。

不同稿件应该是观点不同？ 所以我觉得应该重点关注那些表示观点的词。。。由于中文表示观点的词应该还算相对有限？ 可以打个表把不同类别的词赋值成不同的值。。。然后hash一下。。。？

（感觉自己全程口胡。。。。

其实一面应该还问了其他问题。。。？ 我实在不记得了。。。这几个问题是印象比较深刻的。。。

然后挂了一面电话没几分钟。。。就接了二面电话。。。。上来就面试问问题。。。被效率吓到。。。以至于我以为是哪里搞错了。。。还问了句。。。请问这是什么面试2333.

二面：

一开始好像问了个。。将一个数组的奇数放在前半部分。。。偶数放在后半部分。。。要求 原地完成。。。

这个还好。。。就是两个指针一前一后搞一搞。。。

然后问了。。。搜索中的敏感词问题。。。

问怎么把正文中的敏感词全部替换成星号。。。

我问敏感词多吗?好像是说1000个？反正不多。。。

我就说AC自动机就好。。。敏感词建一个AC自动机。。。然后正文扔进去跑。。。

面试官问我复杂度。。。。啊。。我。。。真的不记得。。。想了下说应该是O((n+m)*L)吧。。。L是字符表的大小。。。。

面试官说这效率不够好。。。让我再想想。。。。

我想到了hash....说把敏感词hash一下。。。？ 面试官问我正文怎么办。。。要把每个词也都hash吗。。。

我当时绝逼脑子短路了。。。以为两个字的词是把n个字两两组合。。。。。我怎么这么傻。。。然后觉得这复杂度显然炸了啊。。。不行。。。

实际上就是O(n)好么。。。再加上敏感词一般都不长。。。

于是我就放弃hash的思路了。。。。

黔驴技穷。。。最后给出了个口胡的统计上的思路。。。

就说统计敏感词的那些字的出现概率。。。以及每个敏感词的字的前后都是那些字（因为这些字出现在一起才敏感）。。。

根据马尔科夫假设。。。每个字出现的概率只和其前面一个字有关blablabla....

然后面试官说。。可以。。但是做不到精确。。。有没有精确的做法。。。

我又想了下。。说除了AC自动机我想不出别的做法了。。。

然后就问下一道题了。。。

说是一个随机数发生器。。。得到0的概率是p，得到1的概率是1-p，问如何等概率生成0和1.。

我想了下说好像和之前遇到的一个问题有点像。。。那道题是给你rand5()的随机数发生器让你生成rand7()的随机数发生器。。。

然后面试官说那就先说说你这道题吧。。。

内心：呜呜呜让你多嘴。。。

然后。。。不知道是紧张还是什么原因。。。明明面hypereal完美回答的问题竟然突然忘记该怎么生成了。。。？

关键就是那个等概率函数怎么构造。。。。

完全不记得当时怎么构造的了。。情急之下。。。竟然又想出另一种？

大概是把每个生成的rand5()看成五进制数某一位数字。。。这样就是等概率的了。。。结果%7就好。。。

不过这个思路貌似对于等概率生成0,1的原始题目也有用？

我可以直接生成二进制数啊。。。00,01,10,11...然后扔掉00和11.。。岂不是美滋滋？

之后又给了我一段代码。。。问我有没有什么问题。。。当时没有看出来。。。。最后知道。。。是在考vector的底层实现。。。

于是最近打算稍微看下STL那些东西的原理。。。

然后。。。大概就是这些。。。每次面试都能暴露自己蛮多问题。。。蛮不错的。。。