Google MTV Onsite

原帖地址:一亩三分地

今天刚面完的,抱着一贯发面经保平安的原则就来发帖了。
第一轮一个中国小哥,其实就是merge interval, 但是就是要自己从头开始设计一个类,实现是否overlap的方法,然后return一堆interval的overall coverage
比如(2, 4) (3, 5) coverage 就是 3 (2, 5)。其实就是merge后返回total len就可以了. 说了两种解法,不过还是得感谢小哥放水

第二是一个中国大哥,问了一个string的plus one,不过和leetcode不同的是,有可能是负数,所以如果负数的话就是minus one了。要haldle各种exception.而且第一次做负数Edge case也不好想。。本来是warmup quesion,结果浪费了好久时间,哎。。。第二题问了一道design,开始没怎么反应过来当成algorithm问题了,所以答得不好。就是 guess 一个 word, 比如 word 是 “heart”, 然后player guess “board”, 会返回1,因为‘r’ 猜对了。
然后设计一个方案,让尽可能快的猜对。答得很不好。。感觉小哥已经给了不少提示了,不过我还是没开窍,最后也不懂。。哎,怪自己。。

中午吃饭也是一个中国大哥,面了大半天了全是中国人,心中窃喜。。跟大哥就唠了唠家常,了解了下湾区定居后的生活是什么样的,大哥很热情。

下午第三轮是个印度小哥,带了个白人shadow, 第一道给一个two D garden , 每一个slot可以是flower或者Wall. 找一个合适的位置,让游客可以看到最多的flower.可以站在flower上,不能站在墙上。。
如果被墙挡了,就看不到墙后面的花。然后游客只能竖直或者水瓶看,不能看对角线。。比如
[ [f, x, x, w, f],
[f, f, x ,x ,x],
[x, x, f, w, f],
[f, f, x, w, x]]
这样,{3, 0} 和 {1,4}都能看到四朵花。
开始说了个brute force的方法,最后优化到o(n^2)分别水平还竖直的便利整个matrix, 记下这行的flower个数,碰到FLOWER就加一,然后每一行碰到墙了就把之前的全部更新, 然后 flower个数reset 到 0.
然后水平和竖直便利后的相加。最后找最大就可以了。。
第二题问了group a list of string, 比如 ’abbc’ 和 ‘bccd’就是一组的。因为平移一位可以得到。楼主傻逼到开始说必须从分别平移量从1试到25才能确定是不是一组的。。最后写完算法忽然发现原来知道string每个字符间的diff就可以了。。感觉三哥哥本来要对我弃疗了。。最后时刻说了想法,小哥终于欣慰的点了点头。。智商真是捉急。。

第四轮一个看着不怎么开心的美国小哥, valid graph tree.跟LEETCODE不同的是,这个图是有向.
Node {
int id;
Set childern;
. 鍥磋鎴戜滑@1point 3 acres}
public boolean isValid(List graph) {}
开始用拓扑排序做完,发现不太对。。因为可能两个Parent有相同的Child,但是Tree中这样不合法。 最后改对了。。 然后问了问test case, 问了问优化。。最后临走前也觉得小哥不怎么开心。。
总体来说Google的面试体验还是不错的,时间安排的很合理。现在最大的concern是第二轮的design,希望大哥能放我一马。。不过楼主感觉运气已经很好了,碰到好多国人,题目也很简单,感觉跟前一阵猛看的面经比起来明显不是一个难度啊。。而且碰到的三哥哥也很NICE。
如果再过不了就完全是自身的问题了,谁都怪不了。。。
攒RP,求Offer..