狗家新鲜面经

上周面的Google, 已挂,发个面经攒攒人品。
时间线:

8/3 内推

8/10 电面

9/11 onsite

电面就一轮:阿三: numberof islands II , union find解决。 阿三一直问各种简单问题磨时间,导致没有时间进入第二题。

onsite:4轮coding, 1轮PhD research. 遇到的基本是白人。

电面就一轮:阿三: numberof islands II , union find解决。 阿三一直问各种简单问题磨时间,导致没有时间进入第二题。
onsite:4轮coding, 1轮PhD research. 遇到的基本是白人。
第一题: 给一堆interval,每一个对应一个字符: (start, end) char

比如

(0,4 ) X

(3,6) Y

(5, 7) Z

将interval细分为不重叠的interval,并输出每段细分interval中存在哪些字符, 不存在字符的区间不用输出。

(0,3) X

(3,4) X,Y

(4,5) Y,Z

(5,6) Y,Z

(6,7) Z

楼主解法:将原始interval变为(start, 1, char), ( end,-1,char), 然后根据首元素sort处理, 遇到start补上元素,遇到end去掉元素。类似lifeand death.

讲完思路之后在电脑上写完了code

第二题:

给出一堆点(xi,yi) 如果任意两个点水平坐标或者竖直坐标相同,就能去掉其中一个点,直到无法去掉点为止(即任意两点不水平/竖直共线), 要求最多能去掉多少点。

楼主开始讲了brutal force的dfs, 白人小哥觉得复杂度太高,在他的提示下用图来解决。 根据point建立graph,如果两个点符合x或y相同的条件,就连一条边。然后union-find查看有多少联通块。 然后谈了一下union-find压缩路径的几种方法和时间复杂度。写出code后接下来讨论了各种小优化。

第三题:地里的面经题。

有一个山洞,可以看作一维height数组。 另外有一堆箱子boxes, 要求将箱子从外面推到山洞里面,问最多能推多少箱子进山洞。

楼主先解释了为什么要先将箱子高度排序,先推矮箱子,再推高箱子。同时山洞的每一个位置i都最多能容许min(heights[:i])的箱子通过。 根据这点建立一个allowedHeight数组,可以看出是单调不增的序列, 因此对每个箱子高度可以bisect寻找allowedHeight里面对应的position index. 讨论了时间复杂度 O(log(len(height))*len(boxes))。电脑写了code后和面试小哥讨论了几点可以优化的地方,最后小哥表示时间复杂度还可以优化,在提示下使用two pointer方法,让两个pointer分别指向最矮箱子的position和最小allowedHeight position, 依次比较二者的大小来分别递增两pointer。 时间复杂度可以变成O(len(height)+len(boxes))

第四题:

给一个undirected graph, 有两个player A,B 玩游戏,由A先选一个node start, B在剩下的node中选择一个。

接下来A,B依次选node,但是每次选的node必须和该player已选的nodes中的一个是neighbour。假设玩家都很理性,问player B能获得的最大nodes数量。

楼主就是挂在这题上的,这题是coding最后一题,楼主各种犯困,亚裔小哥也寡言少语,说完题目就冷眼旁观了。

楼主谈了一下brutal dfs的思路,亚裔小哥不太满意,提示问B每次如何选才能剪枝,感觉好像是B每次选A neighbour中潜力最大的node(就是联通剩余node最多的那个),但是也一时没想到严格的证明,也没时间在电脑上写出code。

这次也算是感受下狗家面试难度吧,以下是准备过程中参考的面经总结:

http://www.1point3acres.com/bbs/thread-438518-1-1.html

http://www.1point3acres.com/bbs/thread-438216-1-1.html

还有利特抠里面狗家出现的题号总结

872, 857, 854, 853, 852, 850, 849, 846, 844, 843, 835, 833, 818, 817, 815, 809, 807, 806, 805, 804, 803, 802,

791, 787, 785, 778, 777, 776, 774, 773, 772, 769, 767, 766, 765, 753, 750, 745, 742, 739, 737, 735, 734, 732, 731, 729, 727, 724, 722, 721, 720,

685, 684, 683, 681, 674, 659, 652, 621, 568, 560, 552, 540, 529, 527, 505, 503,

499, 496, 494, 490, 486, 465, 460, 457, 456, 438, 419, 444, 418, 399, 394, 392, 379, 365, 362, 361, 359, 353, 346, 340, 337, 334, 315, 312, 308, 305,

298, 297, 295, 289, 286, 274, 271, 270, 269, 264, 253, 249, 248, 238, 236, 235, 230, 229, 222, 220, 218, 205, 200,

169, 165, 162, 153, 152, 150, 146, 141, 135, 134, 128, 124,121, 115,112, 96, 95, 91, 84, 72, 65, 59, 56, 44, 43, 42, 41, 37, 36, 10

谢谢楼主分享。想问下推箱子那题?没太看明白题目意思。。能麻烦楼主再解释下嘛?是有一些箱子,箱子都是不同高度的?然后山洞也是不同的高度的?

3个点,1个联通块,所以能去掉3-1个点

第二题不能直接sort X then sort Y,然后从不同X的点中找不同Y的点个数?

楼主加油

非常感谢lz的分享,祝福lz尽快拿到offer

比如说 (x1,y1), (x1,y2), (x2,y2) 能去两个点,如果按x或者y sort只能去一个点

sort后从尾往前loop,若 i > 0 && (y == y[i-1] || x == x[i-1]) continue, else count++;
这个有什么corner case没考虑到吗?

比如说按x sort的话
(x1,y1), (x1,y2), (x2,y1)

OMG。。。
非常感谢!
看来连线数联通块的方式确比较好

第二题用Union find 是不是不太对啊?
比如以下矩阵:
110
100
000
按照规则的话最多能remove 2个点, 比如先remove(1,0)再remove(0,0)
但是联通块只有1个[(1, 0), (0, 0), (0, 1)]

感觉博士的面试比master难一点?