Google Onsite 11.23

原帖地址:一亩三分地

上周五hr通知说过了hc了,发一下面经攒攒人品!
第一轮
白人大叔
input:
G . . G
X . . .
. G . .
G是终点,.是可走的点,X是不可走的点
output:
求出每个可走的点到终点的最短距离(每一步可上/下/左/右一步)

我的做法是经典的BFS。先构造一个距离矩阵,所有G的点对应的是距离为0,其他点为MAX_INT。然后将G的点放入Queue中进行BFS,修改距离矩阵。

follow up:
如果每一步可走两步/三步怎么办?
如一步可走:左左,左上,右下,。。。
我说应该画出解空间树,然后DFS遍历解空间树,DFS的返回值是从该点出发最少需要几步到达一个G点。大叔说make sense。

第二轮
白人Geek小哥
input:
string stream
如 abckdeghs…

有一个search list[google, ok, doit]

output:
每当stream里的有字符串是在search list里的,就alarm clock

我想的是先用search list构造一个Tre
然后alarm clock的方法我参考了actor model里的actor send message。所以这个函数是没有返回值的,发现有匹配之后send message
函数的输入是一个叫StringStream的class,用next()函数得到它下一个char。并且string stream是不能回头的,不能通过坐标得到某个char
我给出的做法是每碰到一个合理的开头,就把之后的char都记下来。
比如,对于输入流为abcd…, search list: [abcb, bcd]
那么到d的时候会发现以a开头的不对,于是从存好的a后面的一个char即b开始重新遍历Tre,看是否可以满足。

第三轮
国人哥哥
lc: serialization and deserialization of binary tree
lc: sort colors

第四轮
国人哥哥
第一题:
input:
source string: abcde
target string: ebcda

要求:
对于target string,只能进行交换两个char的操作。如例子中,交换a和e,那么source string和target string之间差异距离就由2减到了0.
要求输出将差异距离减小到最小的一次交换的坐标,如例子,是输出[0,4]
source string和target string长度相等
我先开始是想的是用一个hashmap记录source string里每个char的位置,然后遍历target string时,看是否有对应的。
比如上面的例子,a是0,e是4。那么遍历target string时看e在map的坐标是多少,发现是4,然后看target下标为4的char是否是a,如果是,就说明这个交换可以将差异值减小2,输出。如果不是,那说明这个交换可以将差异值减小1。
但面试官提示说如果输入字符串里有大量重复数字,那么时间复杂度就不是线性的了。
于是想到可以用两个map,第二个map是记录(s, t)这一对tuple的位置的。于是由第二个map可以找到将差异值减小2的解,由第一个map可以找到将差异值减小1的解。

第二题:
给出四个点的坐标,判断这四个点能否构成一个正方形。

关键在于四条边的关系。

一点感想:
Google onsite是我最紧张的一次onsite了。感觉中途代码写的不是bug free,不过面试官一直安慰我说他们看重的是思维。
觉得自己很幸运,遇到两个国人哥哥,真是非常谢谢他们!面试过程中可以感觉出来Google很看重思维的过程。整个过程中我都在和面试官不断的交流,每道题(除了第一轮)都拿出了2到3种方案,感觉他们对于这点还蛮满意的。

补充内容 (2015-12-10 00:50):
求大米啊~~