12月1日Google本科Intern电面

原帖地址:一亩三分地

9月底网上海投的的,之后就忘了这事了,11月初突然通知有面试,面试定的时间是北美11月30日上午,两轮back-to-back,在我们东八区就是12月1日凌晨了。。没日没夜刷了三周题,当天凌晨1点的时候喝了罐红牛,开始等电面。。这次面试出奇的简单,可能是因为楼主是本科的原因吧,之后发现全是LC原题。。

第一面 纽约白人小哥,比较不爱说话
1. Leetcode 102 level order traversal, 把每层print出来就行
e.g.
. 1point3acres.com/bbsinput:
1
/ \
2 3
output:
1
2 3

上来一看就知道用queue就行,跟他说了想法之后直接开始code, 3分钟写完。。

2. Leetcode 107, print in bottom-up level order
e.g. Input 如上一题
output:
2 3
1

刚看到这题还在想要不要用stack或者recursion,然后马上发现用一个LinkedList倒着保存每层的结果就行,就是每层traverse完把结果插到list的前面就行了,最后循环一下输出。。
直接复制第一题code加几行就过了。。

-google 1point3acres
之后小哥说有个bug,发现其实是每行print出来会多一个空格。。判断一下是不是每层的最后一个就行了。。最后说了一下复杂度,他说没啥问题了,一看时间才15分钟,然后我问他这题还有更好的方法么,他说iterative就很好了,有些人用了一些很weird的方法也没做出来之类的,最后聊了会天就挂了

接着第二面 白人小哥,人超好的感觉
1. Encode/Decode string
经典题了,演了一下就过了

然后小哥说有点工作上的技术问题要挂5分钟,一会打过来。。

2. Leetcode 249. 题干说的是这是一种被称为“rotate-n”的加密方法,比如”ace”就可以通过rotate-1得到”bdf”, rotate-2得到”ceg”, …, rotate-25得到”zbd”
然后给一个list of string, 要求把所有可以互相rotate得到的string group到一起。其实就是和原题一模一样的,只不过换了个背景交代
e.g.
input: [“a”,”c”, “abc”, “def”, “ceg”, “ace”]
output: [[“a”,”c”], [“abc”, “def”], [“ceg”, “ace”]]
不要求写code,直接说思路
楼主刷题的时候没刷过这一题。。
先brute force给了n^2的解,然后小哥提示说能不能每个stirng都transform成可以一个identify它的group的string?
想了一下,发现对于同一个group的string有以下特征:
1. single char肯定都是同一组
2. 考虑abc => bcd => cde,发现”abc”中的”a”和”b”的difference为1 (‘b’ – ‘a’ = 1), 他们rotate之后的”bcd”中的”b”,”c”的difference仍然为1 (‘c’ – ‘b’ = 1),也就是说rotate之后,这个string每个char之间的difference不变
所以可以先把每个string都转化成这种char difference的形式:比如”abc”就变成了”11″, “bcd”也是”11″, “acb”就变成了”2-1″,就可以把同一个组的string都pre-process成一样的了,最后扫一遍list就可以得到group的结果了
感觉小哥对这个解还挺满意的,然后这题就算过了。最后聊了十几分钟的样子,感觉他心情蛮好的,跟我讲了蛮多google的团队,project,每天的工作啥的,然后就结束了。

后来看地里的面经,一个更清楚的解法是把所有string都rotate成’a’开头的,就肯定能把不同的group分出来了。。。当时咋没想到呢

接下来就是等啊等,等啊等,每天都会半夜醒来看一眼邮件。。然后经过三周的等待。。今天早上终于通知进pool了,太不容易了。。

求match求大米!祝其他的同学好运啊!

补充内容 (2015-12-23 20:57):
忘说了,报的是北美2016暑假实习