人人网算法策略技术岗三轮面［转］

人人的校招还没正式开始，我是被学校的师兄内推的。面的是技术岗，算法策略方向的，问的主要都是算法题。一共面了3轮，我下午2点过去，2点多开始面一直没间断的面到5点半才结束。

第一面的面试官是个挺腼腆的小哥，应该是刚工作吧。他就出了两个题，也不难。

第一个题是：给出一个字符串，找出其中只出现一次且位置最靠前的那个字符。

很简单吧，遍历一遍字符串，记录下来每个字符出现的次数和第一次出现的位置就好了。然后他让我写代码实现，也没什么问题。

第二个题是：有一个链表，除了正常的指向下个结点的指针外还可能有一个额外的指针指向链表中某个结点。换言之结点的数据类型是

struct node{

      int data;

      node * next;//指向下一个结点，与正常链表中next指针意思一样

      node * extra;//指向某个结点或为空

} 

我就想，先把基本的链表结构复制了，然后问题就在于怎么确定extra指针指的是哪个点，这就需要能够唯一的确认原链表中的每个结点。我一开始说给每个结点标号，但是面试官说数据类型已经封装好了不能再往里写东西了。最后用内存地址作为每个结点的key，把原表和新表的结点的地址的对应关系存起来。然后他让我写代码实现。

结果在我写代码的时候他就走了，说是找二面的面试官。于是刚才那个题的代码是二面的面试官看的。

二面的面试官算是个大叔吧，应该是中层leader，人挺好的。我先跟他说了一面面试官给我留的题目和我的思路，然后让他看我的代码。然后他就针对我的代码问。我的代码里遍历链表时有一句

while(p!=NULL){ ... }

他就问我如果p一直不等于NULL怎么办？ 我说如果是个正常的链表的话p走到尾部的时候肯定就是NULL呀。面试官说那可能是不正常的链表，比如循环链表p就永远不会是NULL。我说我没考虑到这点。如果那样的话应该先判断这个链表是否有环，如果没有就没事，如果有的话就要给每个走过的结点作标记，当访问到一个已经标记过的结点的时候说明已经遍历一遍了。

然后他就问我如何判断链表是否有环。我一开始说了一个：把访问过的结点都存起来，每当访问一个新结点的时候看这个结点是否被访问过就可以了。如果用哈希表来存那时间复杂度就是O(n)。

他说这样可以，但是要用到一个O(n)的辅助空间，还有种只用O(1)的空间也是O(n)时间的办法，不过会比我说的时间上慢一点。我一开始想不出来，让他提示了一下，然后就明白了，用两个指针在链表上跑，一个步长为1一个步长为2，如果有环的话步长为2的指针会追上步长为1的指针与之重合。

PS：回来之后在网上搜，发现这个问题其实是很常见的一个问题。不过去面试之前没看到过。  

然后关于链表他又问了几个问题，挺零碎的记不清了。

还有就是他问我如何检索地址对表会比较快，我一开始就说了一个可以先排序然后二分查找。他说有没有更快的，我想了想，想到用哈希就好了。

到这儿一面的那道题就算是完了。然后他又给我出题，因为我简历上写的项目经历有一个是数据库方向的，他就让我写一个sql的代码。其实我数据库学的不好，写的不好。

然后他又让我写一个atoi的函数，就是把一个字符串转为int。他说明了这个函数其实很简单，但是希望我能考虑的全面一些。

我就考虑到：

1.可能传进来一个空串；

2.传进来的字符串不是数字，可能有其他字符；

3.给的字符串对应的数字太大可能越界。

我先问他如果越界了怎么办，需不需要自己定义一个大整数类型作为返回结果？他说不用了报错就可以了。这样就简单多了。

然后在写代码的过程中，写到判断传进来的字符串是否都为数字的时候，我想到也许数字开头会有个'+' '-'什么的，这种形式不应该视为错误输入，应该算一下把结果输出了。

最后写好了给面试官讲了我的想法，他说我做的挺好的，考虑的非常全面。我觉得应该就是我考虑了带符号数这一点出乎了他的预期吧。他又问我那你考虑过科学计数法吗？我说这个没考虑到，不过也是可以做的。他说我随便说一下科学计数法确实挺麻烦的，你能考虑到这些已经很不错了。

然后他又问我想做哪方面的工作，前端还是做后端、想做前台的业务还是后台的数据处理。我说想做前端。貌似三面的面试官是他根据我的回答给我找的。

然后他让我问他问题。因为我不知道还有3面，就一直问他问题，问了好多，包括：他是做什么的（因为我觉得他又精通算法又懂数据库好像挺厉害的），他们部门都有什么项目，能不能从技术转产品（因为其实我不想一直当码农，想做产品经理），公司有没有培训和学习的机会（每次面试我都会问这个问题为了让面试官觉得我很好学，嘿嘿）等等。

结果他跟我说我去给你找三面的面试官吧，你如果还有别的什么问题问他好了。囧，这时我才知道居然还有一面。我本来都放松了的。

三面的面试官是个胖胖的大哥哥，人也挺好的。他先让我做自我介绍，然后我就厚着脸皮把自己夸了一番，不过我说自己好的地方都是有具体事例支撑的，所以貌似得到了他的认可。然后他问我有没有职业方面的规划，我说有啊，我想当产品经理。然后解释了一下我为啥想当产品经理（因为我不想一辈子Coding啊！我喜欢并且擅长提出有意思的点子，不喜欢别人告诉我做什么我就去做什么！），以及为啥不直接做产品要先做技术（因为我大学4年学的是计算机，不做技术又觉得学的东西浪费了——我没说做技术钱多虽然这也挺重要的）。

然后他问了我一些产品方向的问题，因为他是负责人人网的广告系统的，他就问我，怎么让商家认为他们的广告是有效的，又怎么让用户更愿意去点那些广告。

我说我是来面技术的，没想到还会问产品方面的问题，我只能随便说说了，说的不好别怪我~（其实我之前有面过产品方向的职位还是有一些了解的）我说对商家你可以给他们数据啊，现在人人网的流量还是很大的，数据应该不会太难看；然后广告要做的精准什么的，这样商家才愿意买用户也愿意点。

说到精准的时候他又问了人人网的页面广告和百度的关键字广告的比较，我说关键字广告也许更精准但是那只有主动去搜那个关键字的用户才会看到，也就是说用户是本来就有需求而百度把这个需求实现了。但人人网的广告是根据用户的兴趣爱好挖掘出来的，可能会让用户产生他们原本没有的需求。还有人人网的SNS属性有利于广告的传播，可能一个促销活动被某个同学看到了，那么他的有同好的好友也很可能被影响到，这也是关键字广告不具有的属性。

他又问可以通过哪些信息来评估用户的兴趣爱好，这些信息的重要程度如何排名等等。 

我还说可以搞有奖转发什么的，因为微博上整天都在搞。结果他又问了微博和人人的区别，我说人人是实名制的微博则没有，微博具有媒体属性而人人只是一个社区。

总之这方面一直聊了好多好多。感觉这些问题完全不亚于产品面试里的问题啊！

结果聊完了居然又让我做题......shit。

不过他给的题一点也不难，就是把1到n*n的数打印成一个方阵，按照从外层往里层转的顺序，如图：

1  2  3  4 

12  13  14  5

11  16 15 6

10 9 8 7

我说这道题其实我大学一年级的时候做过，当时的做法是一次打印一圈，每次调整起始位置参数直到起点和终点碰到一起了。他说既然你做过的话那就给你加个限制，用递归来做。

结果我做了之后才意识到，用递归比我之前用的本方法简单多了。。。不过谁叫那时候我才大一，对于递归的理解不够，只会写循环 = =

写完这个题对我的考核就结束了，他让我问他问题。我就随便问了几个，因为2面的时候问的挺多的了。我问他我如果进来的话是在他手下干吗？ 他说是的。我觉得不错因为这个面试官感觉人不错。我又问他觉得我怎么样，能不能拿到offer（因为我觉得自己表现还不错嘛所以敢这么问），当然他不会直接说定的，但他说对我还是挺满意的，嗯，那应该就是没什么问题了，挺开心的。最后我问他能不能要他电话号码，他说你要这个干嘛，我说既然我进来了是跟着你干那先多了解一下呗，他就告诉我了。

所以就是这样。3个多小时不间断的做题、说话，把我累的不行。不过好在最后结果不错，还是挺开心的。