G面经2

2016年09月30日 西雅图

注册一亩三分地论坛，查看更多干货！

9月30号在西雅图面的，本来应该早点发的，但是由于种种原因耽误了，现在发上来也算是攒攒人品吧，今年运气一直不算太好。

一共五轮，可以用白板，准确地说是一面白墙，也可以用chromebook.我基本上都是在chromebook上写的，因为我感觉打字要快多了。于是每一轮面试官都把我给的答案发送到他们的邮箱里了，估计是事后比较方便验证吧。

第一轮

英国人，LC418, 当时给了个O(mn)的解法，后来follow up他说要是m, n 都比较大怎么办，然后我给了个O(m)的解法。

第二轮

美国小哥，第一题问了一个数据结构的题，把一个某种格式的inputstream,利用你设计的数据结构转换成另外一种形式并输出，算法上很简单。我implement完后他看了一下也没有提什么问题就直接复制发送到了他邮箱。

第二题问了H-index，秒掉之后他验证了几个edge case, 找不出问题后 follow up 问算法复杂度多少，我说O(n), 然后他follow up说如果citation 如果本来已经排好序的话怎么做，我说可以用binary search。

第三轮

应该挂在这一轮了，美国小哥，pull char to head, 给两个String anagrams, str1 和 str2,每次只能把str2里的某一个char移到最前面，问最少需要几次这样的操作。比如给的String是 “anagram"和“naagram”,可以把第二个String的第二个‘a’移到最前面，最少操作是1. 我当时给了个BFS的解法，然后感觉他不满意，说是不需要每一种情况都要go through一遍。后来想问他给点提示，但是他和我打太极，说他也不确定。

第四轮

不太确定是哪个国家的，应该是混血，第一题要设计一个list iterator,记得比较清楚的是比如给一个list, 是{1，2，3，4}的话，iterator 给的输出应该是 2，4，4，4意即奇数位表示偶数位的value要重复的次数，input list不一定valid,要handle各种Exception。

第二题也是一个设计题，要判断一个人（node）是否能access一个file, 这个node有两个member，一个是userId, 另外一个是他能access的file的list，但每一个file可能也包含多个其他file。给出思路后没有让实现，然后问了他几个问题就结束了。

第五轮

美国小哥，LC317 变种题，敲代码的过程中大脑一抽把visit过后的点的visit[i][j]写成了false, 被他指出来了，敲完答案和和他一起过了一遍，没有发现问题然后他问了下复杂度，然后复制发到他邮箱了。.

后记

面完后的第二周周四HR打来电话，说是有一些Strong data但是feedback的discrepanycy比较大，决定不送HC。HR之前邮件说他会在我onsite的时候和我见面，但是直到面完也没有看见过他，这也是让我有一点小意外吧。

其实整个面试的体验还是不错的，报销的速度也相当迅速。