我面的职位是Software Engineer, Tools and Infrastructure, 所以开发和测试的问题都会问到
Phone interview 1: 白人小哥.给一个Interval的class, 就是一个区间,左闭右开,比如 [1, 3) 意思是从1到3除了3的所有interger. 让我在这个class里implement一个method, 判断与另一个Interval是否有overlapping. 第二问是写一个method, 返回在Interval 1而不在Interval 2的区域. 一道如此简单的题…因为我前面实在太紧张了全身是汗面的吭吭哧哧…面完以后我都准备move on了, 看来小哥最后还是放了我一码让我有了二面.
Phone interview 2: 白人小哥.更简单了… Leetcode原题Plus One. 如果现在Google要release全新版本的Chrome, 我要怎么保证这个新的Chrome全方位的work?
意思就是测试些什么,怎么测试这个新版本的Chrome,才能放心的release出去.
最后他还开心的问了我的名字到底怎么念,我就知道大概有个底儿了~
Onsite:
第一轮: 印度哥哥. 大早上的堵了一个多小时开过去腿都麻了,上来就开始coding,直接蒙圈儿. 第一题, 给一个array比如[4,2,1,3,5],根据这个array现在我们能有了一个新的array => 每个数是在原array里,
在它左边的所有比它大的number的个数,就是[0,1,2,1,0]. 题目是现在给了这个[0,1,2,1,0]要求原array,
原来array的range是1~n.
第二题, 知不知道binary search? 但是现在array是unsorted的可是依然看做sorted array来做binary search, 返回在array里面所有可以在这种情况下binary search出来的数.
第二轮: 韩国哥哥. 经典的地里出现过的String压缩编码解码类似题, 后悔当时看到没有好好写过一遍.给一个String比如"abcdfffffffxyz", 写两个methods, encode和decode.
encode就是比如"fffffff"变成"7xf",decode就是要变为原字符串.我说"ff"怎么办,他说变成"2xf"你不觉得更长了吗?
我才明白了,应该是encoded后的String要比原来的短,不然为啥要encode,的亏我问了这个问题…然后又问他,如果原String本来就是"5xt"这种结构,decode不就无法辨认了吗?他说很高兴你提出了这个问题,但是不用管它,一会再讨论,先写吧. 写完以后他就问我如果原String本来就是"5xt"这种结构,我encode应该怎么处理? 我就傻了…
因为一直觉得encode后的字符串长度一定要比原来的短,所以根本想不出来他要的解法. 说了四五种方法他都不满意, 最后给我hint说,要是有个"1xt"这样的你怎么处理? 当时脑洞大开想出来了… 其实是要变成三个"1xt"这种结构, 比如原String就是"5xq", 就encode成为"1x51xx1xq"就好了.
但是这种方法违背了encode后要变短的rule,所以我是真没想出来… 还讨论了好多种情况,
最后一种是"1aaaaa"这种情况怎么变, 我说"1x15xa". 他说这是6个字符,能不能只用5个?
实在想不出来,这时候第三个小哥进来了,韩国哥哥就过来告诉我说,其实看做1a和aaaa两部分encode就好… 面完我就觉得跪了…
第三轮: 中国小哥. 第一个问题是测试的,比较简单. 测试Calculator,input就是比如俩数一个operator, 都有什么case, 怎么测,应该有什么预期结果或错误. 第二题, 一个array,rearrange成为另一个array, 现在给了这两个array, 求是怎么变化成第二个array的. 挺简单的就用了Hashmap秒了…
然后问我,那现在给你原array,也知道了是怎么变化的了,所以我们现在可以用原array求出变化后的array对吗?
但是我要run这个method好多次比如k次, 怎么最快能求出array被rearrange了k次以后的结果? 最后我就推倒出求LCM.
面完他亲切的用中文跟我说,我是他见过面的最好的,时间复杂度最低trade off也说的好. 谢谢小哥给了我信心~么么哒~
第四轮: 印度姐姐. 假装没有准备的样子现场想题目… 谢谢姐姐没有对我下死手T T 海上有一片岛, 每个岛就是一个node, 岛和岛之间有的连着有的没连着. 所有连着的岛是一个Group. 求在这片海上,
包含岛屿个数最小的group的岛的个数,和最大的group的岛的个数. 就是返回两个个数值, 肯定就是int[2]嘛.
先讨论了用什么数据结构存储, 跟她说了trade off. 然后开始写. 全程想给我挑错, 不断质疑我的代码…
还好我这一轮在高压下还是写的极其顺畅, 一个bug没有出现, 对她也是笑脸相迎, 躲过一劫…
第五轮: 中国大哥. 竟然中文给我面试, 也是感动哭… 第一题, 一个二维数组代表了一个岛. 周围都是海, 岛的左侧和上侧通向Pacific, 右侧和下侧通向Atlantic. 每个数字都代表了那个位置的海拔高度. 现在下雨了, 雨只有从海拔高的地儿能流向海拔低或者一样的地儿. 返回岛上的分水岭的点, 就是在某个/某些点上, 雨水既能流进Pacific, 又能流向Atlantic. 大哥可能也知道白板写不下,让我写纸上. 足足写了4页A4纸,当然字也写的大…手都写疼了… 第二题, 给个Google map, 你就测吧… 我的offer效率很高我完全没想到, 5个工作日从onsite到签offer, 真心感谢hr姐姐. 因为我有个WalmartLabs的competing offer正好是那天截止, hr的意思也是我的feedback很好,所以HC没有犹豫,也马上有组想要我, 所以hr加班加点在进HC当天就跟offer team合作把offer弄出来了. 这里再次感谢各位面试官对我高抬贵手, 以及WalmartLabs…