G面经3
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出来的数..
- Find Peak Element
- Find Peak Element 2
第二轮: 韩国哥哥.
经典的地里出现过的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,所以我是真没想出来...... Waral
还讨论了好多种情况, 最后一种是"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.. visit 1point3acres.com for more. 面完他亲切的用中文跟我说,我是他见过面的最好的,时间复杂度最低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.... ß