G公司 电面+onsite (被拒）

12月8号电话面试，面试的是个美国男的，问了一个数组的题目。
比如有以下一个数组 [1  0  1  2  2  3  4  2]。
要求把0全部放到最后面，连续两个相同的数字加起来放到一个的位置，中间如果隔0也算连续，最后不够的位置全部补0。
比如 1  0  1 中间隔了一个0，但是仍算连续的，就写成 2 0 0，后面的 2  2 就变成 4  0，但是所有0 最后都要放末尾， 所以最后的结果就是[2 4 3 4 2 0 0 0 0]

我用了两遍遍历，用两个指针控制位置，第一次把所有0 移到最后，用一个指针记录当前有效位置，用一个指针记录0的个数（应该说是counter）。第二次遍历将连续两个的合并，每合并一次counter个数加一，最后发现不需要这个counter, 补零就可以了。

然后他把这道题目改了一下，现在有一个新的数组，比如[1 2 3 4 5 1 3], 加上原来的数组，一共两个数组，原来的数组中把0移到最后和不够补零的条件不变。现在替换的方式变为，如果原数组中连续两个数和新的数组中某两个连续的数匹配，就替换成新数组中后面的那个数。比如，一开始的1  0  1，新数组就没有，后面 2 2 3, 新数组中有 2 3,后面的是4，原数组中 2 3就要被替换成4，所以最后的结果就是[1 1 2 4 5 2 0 0]。

我当然在原代码上修改了，还好一开始分两次遍历写的，现在只需动第二次遍历，我把判断是否连续的两个数改为是否连续的两个在新数组中出现的数，第二次遍历中加入了O(n)的运算。然后整体就是O(n^2)。

他问可不可以提高，我想了想，一开始没想出来，觉得怎么样都要遍历两个数组，然后他提示了我原数组是[2 3 2 3 ...]这种情况，我就说先用Map存新数组，每次先访问Map，这样就是可以提高，最后没时间了，他说不用写代码。

两天后受到Onsite邀请。

1月14号Onsite面试，地方真美。
第一轮是个越南人年轻人，才27岁。一开始问了一个巨简单的问题，int sum(TreeNode root, int min, int max)， 直接写出函数名，求一个binary search tree中在[min,max]区间内所有节点之和。我一开始写了个stack的DFS，发现不好写，然后就改成一个recursive的，用了一个global变量sum去记录和，后来他问可以不可以不用这个变量，我就把recursive函数改为返回int值的，改了一下就可以。然后让我设计一个贪吃蛇的游戏。不用写具体函数，写出类，各函数要实现什么。关键问题是怎么表示蛇和控制方向。我用一个二维数组存地图，用了一个queue表示蛇，他感到很满意，控制方向的逻辑也不复杂。然后他说建议以后想设计的时候不要先去想要多少类，而是一步一步的，到需要的时候再创建新类。

第二轮面试是个中国人，女的，中年吧。我彻底跪了。她的英语是所有人里面最差的，感觉还没我好，她考的是flatten iterator, 然后变了方式，比如有一个Iterator<Iterator<Integer>>是：
a : 1 2 3 4
b : 5 6
c : 7 8 9
要求最后总的iterator是 1 5 7 2 6 8 3 9 4。
我一开始光听名字以为是直接变成1 2 3 4 5 6 7 8 9，觉得这不是很容易么。唠了半天她也没给我指出哪里错了，而是一直在说不知道iterator的存贮方式，可能是在文件什么的，只能调用next()和hasNext()。我完全不懂为什么会产生这个问题，最后大概剩10分钟我终于弄明白她什么意思了，她以为我是先把整个iterator存到一个Queue中然后迭代返回，每次到头就从List的开头调出第一个iterator, 所以才会有什么iterator不够空间存贮的问题。说白了，就是不让用一个东西存最外层的iterator。早说啊，我当时就崩溃了，还剩10分钟不到的时间瞎写了一通，打算用两个queue来回倒什么的，总之都是胡扯。最后她一面笑容的离开了，我觉得她一定以为我是未谙世事的毛孩子。
现在想想这道题不难，可以用链表做，用一个O(k)维的数组（k是第一个iterator的长度）存链表的头指针，每次读都按照顺序接到对应指针下面，最后把指针数组总的串起来。示意图
加入一个新iterator d 来强化例子。
d: 10 11 12 13 14 
指针数组：
->1 
->2
->3
->4
第二次循环
->1 -> 5
->2 -> 6
->3 ->
->4 ->
第三次循环
->1 -> 5 -> 7
->2 ->6 ->8
->3 ->9
->4
第四次循环
->1 ->5 -> 7 -> 10
->2 ->6 -> 8 -> 11
->3 ->9 ->12
->4 ->13->14

现在想想，无论如何，输出的size总要是所有元素个数吧，既然没有空间给你存所有元素，怎么存输出结果啊。到现在都还是有点不明白，希望有人指点。

第三轮是个印度人，一开始态度超恶劣，一幅我是来欺负你的样子。还有个跟班实习interviewer，服了。他问了一个这样的问题,一个非单字母的单词可以表示为 “首字母”+中间字母个数+“尾字母”的形式。比如clean可以表示成c3n，international可以表示成i12l。他一开始还说了一个超长的单词interdiscip....什么的问我知不知道是什么意思，好像在示威一样的说是交叉学科XXX学，这你都没听过吗？我以为要考什么非计算机的知识呢。然后问我这个怎么方便确定一个给定的缩写是否对应唯一单词。没有给任何其他信息，我就问了字典怎么样的什么什么的，他说你想是怎么样的就是怎么样的，然后我有点明白这是要我设计一个这样的字典。我用了一个链表去存第一个字母，然后指向一个26维数组，每一个数组又是一个新的链表，指向对应的单词。后来他问我是指向对应单词还是指向对应单词的个数，我说能指向个数当然好了，但是这样字典不就没了吗，他说没关系，那就指向个数吧。然后他又问为什么要用链表，我说方便添加删除，查找最坏需要O(n)的遍历，然后问能不能提高，然后我就说改用Map，然后就没问其他的了，问了一些我做视频处理的经历，因为他也是做视频处理的。最后的感觉是越聊越好，他最好主动握手说hope to see you soon。

第四轮是个韩国人，已在那里呆了11年，现在在做research了，他语气里想告诉我这间公司其实是很drive员工的，那些街上摆的他从来没玩过。问了一个这样的奇葩问题
给定一个字符串比如airplane,一个字母列比如[a p]。
如果字符串中出现了字符列中的字母，就要可能改变大小写，返回所有可能的大小写组合。比如这里就应该返回
Airplane
AirPlane
AirPlAne
airPlane
airplane
airplAne
....
我说可以先确定有几个字母出现了，然后写出对应的二进制码，比如这里有三个就是
000
001
010
011
...
然后对每一个进行遍历，遇到1就大写，0就小写。
但是写的时候发现自己不会用O(1)的时间使每一次的二进制数列自动加1，这里耗了好久还没有想出来，被迫用了O(n)的时间加1，有点衰。现在想想应该是把1到n转化成二进制，用比特运算做的。方法他还是比较认同吧。

三四天后受到电话据信。