三探希格玛

http://www.sillysnail.cn/third-trip-to-sigma-building.htm

微软在中国最核心的"大脑"，微软亚洲研究院和亚洲工程院，并不在气派堂皇高耸入云的清华科技园D座，而是在知春路上旧旧的六层希格玛大厦。两年前推研的时候，我第一次来到这里参加笔试，希望能进入微软亚洲研究院做博士生。作为物理系学生，最后结果是毫无意外地做了笔试关的分母。

一个月前到希格玛面试实习生，被问了一堆智力题和编程题，得出结论是我不会coding，遂被鄙视。看在我老板推荐的面子上给了二面的机会，让我学一个月C#先，于是今天第三次来到这里。问了几道算法的题，都挺有意思的。

热身题是给一棵双向连接的树，找出两个节点的最近公共祖先，在知道和不知道节点层数的情况下分别讨论。问题很简单，没有太多优化的余地，按下不表。

第二个题是stuart以前给我讲过的，判断一个单向链表有没有环。最简单的方法自然是在每个节点添加已访问标志，遇到标志就表示有环；如果不允许修改原链表就另行维护一个包含所有已访问节点信息的列表，每访问一个新节点就搜索一次，这个办法很笨，复杂度是O(N^2)。stuart教我的办法是设置一快一慢两个指针，慢指针一步一步走，快指针两步两步走，每轮比较两个指针是否重叠，重叠就说明有环。这个方法做起来也很容易，最坏的时间复杂度是O(N)。面试官给出了另一个巧妙的算法，利用环节点的入度为2的特性，遍历的过程中把当前节点next指针反向，有环的链表最后会终止在始节点，无环的会终止在终节点。

最后来还是编程题，简单的链表合并与二分查找，面试官希望我用C#的LinkedList来做。但是我正好没有学到这一章(惭愧啊)，只好用C来写。前一个被挑了一处小错，后一个就写得战战兢兢，还好勉强过关。听面试官的口气，应该是没什么大问题，这学期结束之后就可以过来上班了，据说我的工作将主要是代码实现和测试，怪不得对coding这么看重。

总得感觉很好，微软的员工都很nice，无论是前台还是工程师。这里的氛围让人兴奋，天才聚集的地方。

PS: sillysnailmm今天也面试了，奇虎的部门助理，据说结果还不错，我也很高兴(虽然我个人很不喜欢奇虎)。