一亩三分地论坛

 找回密码
 获取更多干货,去instant注册!

扫码关注一亩三分地公众号
查看: 1927|回复: 6
收起左侧

Google summer intern电面

[复制链接] |试试Instant~ |关注本帖
sjwarthas 发表于 2015-3-22 06:15:30 | 显示全部楼层 |阅读模式

2015(1-3月) 码农类 硕士 实习@Google - 内推 - 技术电面 |Pass

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看,没有帐号?获取更多干货,去instant注册!

x
LZ现在在University of Utah读CS MS,当时觉得这学校图形学很牛逼就来了这然后就后悔了,实习工作不是一般的难找,本地的小公司不愿意招留学生,小公司面试又不问技术问题就净扯淡,然后LZ也没有任何的offer...最后抱着碰碰运气的心态投了Amazon和Google,其他的不敢投,怕面试不过拉黑影响下学期找full time...Amazon是在3.11面的,结果悲剧,这个LZ在另一篇帖子里细说。这里先聊聊Google的面经。面试安排在3.19,三轮电面。用C++。


面试准备:刷了三遍leetcode, 基本做到一题多解,看了一些比较热门的面经题。. From 1point 3acres bbs


第一面:
面试官是个白人小哥,人很nice,上来不是很深入地问了我做过的一个recommender system项目。然后就开始coding interview.

problem 1:
判断是否happy number. Given an input integer num, determine if it's a happy number. . From 1point 3acres bbs
Example: 给出一个数,譬如13,那么计算13的下一个val就是1^2+3^2=10, 再下一个val是1^2+0^2=1, 由于变成了1, 就退出循环,那么这个就是一个happy number。 假如val不会达到1而是重复出现之前出现过的数字,那么就是unhappy number。
Solution: 强撸,如果loop里val为1,返回true; 用一个hash记录出现过的val, 假如碰到之前hash里出现过的,返回false; -google 1point3acres
这里LZ犯了一个很傻逼的错误,本来每个digit应该是dig*dig的,LZ写成了dig<<2, 后来面试官指出来,我改成了dig<<1......脑子秀逗了。后来面试完我才记起来,too young too simple.
. Waral 鍗氬鏈夋洿澶氭枃绔,
problem 2:
longest repetitive substring.
Example: input "banana", ouput "ana". input "ababab", output "abab".
我问了面试官几个问题,如果有多个长度一样的repetitive substring,是否输出第一个,他说是。我又问了这些repetitive substring是否可以overlap,他说是。我心想,一模一样的面经原题。然后我就人生如戏,全靠演技,开始做题。
solution 1: 我给出一个用hashmap的暴力方法,记录每个substring的数量。面试官问我complexity, 我说time O(N^2), space O(N^2)。然后他说,你是不是把hashmap的insert operation当成O(1)。我补充道,是的,但是其实hashmap要map一个string要遍历这个string一次,所以其实insert operation是O(N),那么总共的time O(N^3)。嗯嗯。. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
solution 2: 我又说了一个方法,suffix array, 把input分解成从index 0....n-1到index n-1的substring, 一共n个,然后把这些substring排序,求相邻substring的最长prefix. LZ一开始大脑有点空白,后来结结巴巴用了10分钟才说出了思路。面试官一直鼓励我说it's close, you are on the right way. 真的十分感激这位小哥的耐心。time complexity是O(N^2logN),空间复杂度是O(N^2),不过经过优化可以达到space O(N).
solution 3: 没剩下几分钟了,我就说了一下suffix trie, 面试官说不错,可以把time 和space optimize到O(N)。我就大概说了下思路,面试官也没叫我写。(其实我不会写,所以前面我选择了用suffix array拖延的策略,囧)。. 鍥磋鎴戜滑@1point 3 acres
. visit 1point3acres.com for more.
第二面:
面试官是个三姐,口音还算听得清楚,一上来就给我贴了道python代码,问我是干嘛的。好吧我python代码量不足1000行。。。我看了1分钟,说这是判断是否prime,是就返回false. 她说不对,你仔细看看,原来我尼玛看反了,应该是prime就返回true. . 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
problem 1: . more info on 1point3acres.com
leetcode里面的pow. 我先说了O(N)的方法,然后又说了可以优化到O(logN)。这题比较蛋疼的是一些overflow的问题,我详细地解释了为什么有些地方需要强制转换成unsigned int.
problem 2:
leetcode里面的valid parenthesis. 用stack可以解决。
这次面试比较顺利,结果做完还有10分钟,三姐说没有其他问题了。然后我问了她在哪个group在干啥,她bla了一堆,我听不清(还好前面做题的时候能听清)。然后在还剩下8分钟的时候结束了面试。

第三面:
面试官是个白人小哥,一上来就开始做题。.鐣欏璁哄潧-涓浜-涓夊垎鍦
problem 1:
average of the last K stock price in a stream integer
一个公司,不停的更新股票价格integer, 求最近K只股票的平均价格。
水题,maintain 一个queue, 一个sum, 每次update O(1) time,O(K) space. 啪啪啪写完
follow up 1: 给出不同的公司,given campany name and the current stock price, compute the average of the last K stock price of that company. . From 1point 3acres bbs
就是两个hashmap, 分别存储sum和queue,key为string, 其余跟上面一样。啪啪啪写完
follow up 2: minimum of the last K stock price in a stream of integer, . 1point3acres.com/bbs
我跟面试官说了思路,用heap, 然后我一下子想不起来该用max heap或者min heap(后来想应该是用min heap,而且应该有一个queue记录heap的index,方便delete和insert).....然后面试官说没关系,不是重点。我说time O(logK)和space O(K). 然后就下一个follow up...
follow up 3: median of the last K stock price in a stream of integer. . 鍥磋鎴戜滑@1point 3 acres
我说可以用两个heap来保持平衡,让median在中间。一个max heap, 一个min heap。面试官问我怎么保持size平衡,我说假如一个heap比另一个heap大,那么就把heap top element取出来放到另一个heap里...面试官听了挺满意。

problem 2: .1point3acres缃
Given an integer matrix, and given index x,y, determine the perimeter of the blob which has the same value.
这道题面试官花了不少时间跟我解释什么叫blob,后来我知道就是4-connected的相连的块。至于perimeter, 我不知道perimeter什么意思...面试官给我几个例子,我也想不通。当时我以为是直径,所以想不通...后来面试官直接就说让我把那些blob里每个cell的index都输出就好了。。。我就开始用DFS写。.鐣欏璁哄潧-涓浜-涓夊垎鍦
写完后,面试官叫我写test case,我就装模作样写了几个test case,然后再跟他说,用BFS效果会好一些,不用占用那么多内存...然后到了提问题环节,面试官问我愿不愿意来mountain view...我说好呀好呀blabla

面试完后,我觉得基本没戏了,一来题目不难,二来每轮面试都犯了一些极低级的错误。(还是too young),三来最后一面居然不知道perimeter是什么意思害面试官换问题。。。妥妥的悲剧。
结果3.20早上就收到HR的mail说通过round 1, 进入round 2 host match。太开心了!
.鐣欏璁哄潧-涓浜-涓夊垎鍦
不过,host match似乎比code interview更难。。。而且现在3月都快过去了,我预计能match到得成功率不足30%...虽然是个小**,还是很希望能match上,而且手上没有其他offer了,google不要我的话暑假只能回国。。。(大公司我就面了Amazon和google,其他都是本地小公司)。希望群里在google的大大,如果有渠道有资源有兴趣,希望能推荐一下小弟host match,谢谢!或者,其他什么公司有坑的话,能够帮忙推荐一下也好!谢谢!
. more info on 1point3acres.com

评分

6

查看全部评分

354886 发表于 2015-3-22 06:46:20 | 显示全部楼层
问LZ一个问题。你说的被拉黑是面试不过才会被拉黑?简历直接悲剧就无所谓了?
回复 支持 反对

使用道具 举报

 楼主| sjwarthas 发表于 2015-3-22 06:59:09 | 显示全部楼层
354886 发表于 2015-3-22 06:46
问LZ一个问题。你说的被拉黑是面试不过才会被拉黑?简历直接悲剧就无所谓了?

是的,简历杀不会被拉黑
回复 支持 反对

使用道具 举报

Jackxuxuxu 发表于 2015-3-22 08:10:24 | 显示全部楼层
受教了,面试不过还会被拉黑呀~~
回复 支持 反对

使用道具 举报

aifer 发表于 2015-3-31 05:58:53 | 显示全部楼层
我想问一下楼主,一面的第二个问题的第二个solution的时间复杂度为什么不是O(N^2)?另外,这个空间复杂度应该就是一个size为N的数组,用来放分解出来的N个子串对吧?这个复杂度应该是O(N)还是O(N^2)?
对于总的时间复杂度,我的理解为,第一层循环是整个子串数组的循环为 O(N),子循环是数组中每一个子串的的循环,应该也是O(N),这样的话,应该是O(N^2)才对啊。求楼主解释一下。
回复 支持 反对

使用道具 举报

2015fallcser 发表于 2015-4-5 16:49:46 | 显示全部楼层
求问一下楼主找工作的结果   utah真的很糟么?
回复 支持 反对

使用道具 举报

mm豆 发表于 2015-4-5 23:56:34 | 显示全部楼层
Given an integer matrix, and given index x,y, determine the perimeter of the blob which has the same value. 。也就是和x,y相联通的并且具有相同value的单元格都打印出来,而且这些相连的cell的个数必须大于4(blob)?对么?
回复 支持 反对

使用道具 举报

本版积分规则

请点这里访问我们的新网站:一亩三分地Instant.

Instant搜索更强大,不扣积分,内容组织的更好更整洁!目前仍在beta版本,努力完善中!反馈请点这里

关闭

一亩三分地推荐上一条 /5 下一条

手机版|小黑屋|一亩三分地论坛声明 ( 沪ICP备11015994号 )

custom counter

GMT+8, 2016-12-11 01:55

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

快速回复 返回顶部 返回列表