一亩三分地论坛

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

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

7/21 谷歌MTV onsite 攒人品

[复制链接] |试试Instant~ |关注本帖
jjustc 发表于 2016-7-22 13:06:21 | 显示全部楼层 |阅读模式

2016(7-9月) 码农类 硕士 全职@Google - 猎头 - Onsite |Otherfresh grad应届毕业生

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

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

x
今天刚面完的……来地里怒发一贴 同时求人品啊…….鏈枃鍘熷垱鑷1point3acres璁哄潧

Google onsite安排的很好,前一天在他安排的酒店住下(在阳谷县),我自己租的车,所以直接开了过来。酒店环境还挺不错,有免费早餐。
第二天早起,吃点东西之后开车去mountain view……自己开车的小伙伴一定注意要早点走,101在Google那个出口非常堵,1英里的路开了大概有10分钟。我之前看着Google Maps说16分钟能到,我就9点40才出门(10:15开始面试……)结果到41号楼下已经10点多了,而且还找不到停车位,随便找了一个什么G studio parking only的就停了进去,心里好慌……

然后进到41号楼lobby,在门口小哥处check in 之后,有recruiter来领人。她把我领到一个小会议室里,跟她随便聊,等第一个interviewer来。过了不一会第一个来了,是个印度姐姐,直接扔题……

1. 给你一个数组,里面是一些树的结点,每个结点有id, name, parentId,让DFS输出结点的name。我额外用了一个hash table来存正常的树(根->孩子),然后做了一遍DFS。然后就是想test case,这个姐姐好像是SDET,特别喜欢问test cases,我连想带猜说了好几个corner cases,结果 还基本上都对了,然后改了改code来处理一下,然后问了下问题就完了。她也没说我的做法好不好什么的,比较怕这种没啥feedback的interviewer……

然后就是一个中国大哥,看上去比我还要紧张,然后感觉在放水。先问了下简历上的,然后做题
2.(1) 给你一个数,判断是不是rotation symmetric(比如 111,818,619,69之类的)
        follow up 给你一个n,求n位的所有的rotation symmetric number (leetcode原题)
2.(2) 给一个array A,判断是否存在 i<j<k, s.t. A<=A[j]<=A[k] . more info on 1point3acres.com
一开始我用DP写了O(n^2)的,然后他说可以到O(n),在他提示下写出来了。就是存左边最小的,再存一个右边最大的。(我一开始存了左边小的)

然后他和我一起等陪我吃午饭的人来,一边聊天一边等,等了好一会也没来……然后他就带我吃饭去了……Google饭真难吃…….鏈枃鍘熷垱鑷1point3acres璁哄潧

下午,一开门是一个印度小哥,看起来不是很友善……问了下简历上的东西,问的还挺细致的……跟之前的中国大哥问的不一样的项目。本来我想讲三个项目,讲了两个之后他可能觉的我太啰嗦了,就开始出题了……
3. (1) merge two sorted list 我听到这题都震惊了 也太简单了吧 又确认了一下 (小哥口音略重) 然后就写了顿写出来,讲了下test cases
3. (2) 给一个BST,给一个target 求BST里的值 使这个值离target的距离最近
好像也是leetcode原题,不过记不太清了。我一开始听错了,以为是找BST里比target大的最小结点,blablabla说了一堆 他好像有点烦 然后他又举了一个栗子,我才知道是怎么回事……然后我说应该blablabla这样做 他满意地点了点头,然后就开始写code了
写完之后run了几个test cases 就结束了。他走的时候比较匆忙,他问我有什么问题么,我说没有,然后我脑子一抽,又问了一个问题,然后他解释了下就走了……

最后一位是个白人帅哥,进来之后随便聊了聊 感觉气氛很不错。然后他就开始问题。. 1point3acres.com/bbs
4. 有N个学生,每个学生有一个GPA,有K个scholarship,K<=N,GPA排名前K的学生可以得scholarship。我说用max heap做。然后就来follow up了
follow up 1: 如果 N很大,学生们无法fit in memory,且N>>K。我说读一个chunk一个chunk的进来,求top K,然后再merge到一起求top K。他说好 分析一下复杂度(时间,空间)
然后他又说,你可以one pass做这件事。我想了一下,他又说,你可以每次只读一个学生。这时我知道他是maintain一个K大的数组,我讲了一下。然后他比较满意,分析复杂度(这需要O(NK)次比较,从K大的数组里kick out出最小的,再找到K个里最小的,最坏情况下每次都要比较K次)。
然后他又说,你可不可以improve。我说那可以用multiset,可以搞到O(NlogK)。然后讨论了一下multiset的细节,然后说那改用min heap吧。
然后他又说……如果 K也很大很大怎么办……最后一起figure out出来是用bucket,然后分析了一下复杂度……

最后跟他聊了不少他team的事情,不停的夸他的工作……他也很开心……最后走的时候也很开心……整个面试流程下来,让人感觉还是挺舒服的,希望能有个好结果 !!!

希望大家一起攒人品!



补充内容 (2016-7-22 13:07):.1point3acres缃
补充一点:有些会议室很小,白板也比较小,大家写code的时候,一开始不要写太大……只要能看清,写小一点比较好,便于后面改动和加code……
. visit 1point3acres.com for more.
补充内容 (2016-9-8 05:24):. more info on 1point3acres.com
楼主8.4号拿到Offer,可以看我的抖包袱贴。过了两天就签了,好没骨气……

评分

4

查看全部评分

本帖被以下淘专辑推荐:

 楼主| jjustc 发表于 2016-8-30 09:23:15 | 显示全部楼层
mooc 发表于 2016-8-30 03:06
lz 最后结果怎样?
. visit 1point3acres.com for more.
楼主最后拿到offer啦 可以去看抖包袱贴

也祝大家都有心仪的offer!
回复 支持 1 反对 0

使用道具 举报

 楼主| jjustc 发表于 2016-8-23 01:41:25 | 显示全部楼层
frank11118 发表于 2016-8-22 13:08
鏉ユ簮涓浜.涓夊垎鍦拌鍧. 感謝分享

請問

用两个数组minA和maxA,分别存左边最小和右边最大
minA = min(A[0,,i-1]), maxA=max(A[i+1,n-1])
return true if minA<=A<=maxA

评分

1

查看全部评分

回复 支持 1 反对 0

使用道具 举报

 楼主| jjustc 发表于 2016-7-22 14:11:14 | 显示全部楼层
say543 发表于 2016-7-22 13:30
offer有望 楼主 最后一题的follow up 每次只读一个学生 这个solution 不太懂 能说说吗? 另外follow up2 k  ...

每次只读一个学生就是你在memory里maintain一个K大的数组(叫做KA吧),来存储当前你遇到的K个GPA最大的学生。读进来一个学生(假设是S)之后,比较这个学生的GPA和KA里GPA最小的那个(假设是M),如果S>M,那么就把M从KA里kick out出去,同时加上S,同时再找到现在最小的那个。bucket的话是这样,假设有很多bucket,第一个bucket是GPA 3.99-4.0的,第二个bucket是 3.98-3.99的,以此类推。第一遍,把学生放进对应的bucket,然后从第一个Bucket开始数,数到某个bucket它大于等于K为止。
回复 支持 1 反对 0

使用道具 举报

say543 发表于 2016-7-22 13:30:38 | 显示全部楼层
offer有望 楼主 最后一题的follow up 每次只读一个学生 这个solution 不太懂 能说说吗? 另外follow up2 k 很大 用bucket 是解省memory的意思吗? c++ 不熟 问一下 thanks
回复 支持 反对

使用道具 举报

csushin1992 发表于 2016-7-22 13:52:40 | 显示全部楼层
同样不懂bucket怎么回事。
然后面试新手,问一下楼主说的run test case是手动的么?就是用脑袋自己按程序走一遍,还是说用电脑跑一遍?
回复 支持 反对

使用道具 举报

 楼主| jjustc 发表于 2016-7-22 14:12:15 | 显示全部楼层
csushin1992 发表于 2016-7-22 13:52
同样不懂bucket怎么回事。
然后面试新手,问一下楼主说的run test case是手动的么?就是用脑袋自己按程序 ...

bucket见上一条回复。run test case也不是你在脑子里run,是手动模拟但是我觉的 还需要讲出来给interviewer听。
回复 支持 反对

使用道具 举报

csushin1992 发表于 2016-7-23 04:06:45 | 显示全部楼层
jjustc 发表于 2016-7-22 14:11
每次只读一个学生就是你在memory里maintain一个K大的数组(叫做KA吧),来存储当前你遇到的K个GPA最大的 ...

谢谢,懂了!
回复 支持 反对

使用道具 举报

dorota 发表于 2016-7-23 04:42:01 | 显示全部楼层
赞。感觉G家最近bar不是特别高啊。祝lz好运!
回复 支持 反对

使用道具 举报

 楼主| jjustc 发表于 2016-7-23 05:54:55 | 显示全部楼层
dorota 发表于 2016-7-23 04:42
赞。感觉G家最近bar不是特别高啊。祝lz好运!
鏉ユ簮涓浜.涓夊垎鍦拌鍧.
我也看了几个最近的onsite面经感觉experienced要难很多啊…………可能因为我是new grad吧……
回复 支持 反对

使用道具 举报

frank11118 发表于 2016-8-22 13:08:52 | 显示全部楼层
感謝分享

請問
”2.(2) 给一个array A,判断是否存在 i<j<k, s.t. A<=A[j]<=A[k]
一开始我用DP写了O(n^2)的,然后他说可以到O(n),在他提示下写出来了。就是存左边最小的,再存一个右边最大的。(我一开始存了左边小的)“. visit 1point3acres.com for more.
是指什麼意思呢?
回复 支持 反对

使用道具 举报

zhangyanuuuuu 发表于 2016-8-23 23:26:24 | 显示全部楼层
第二题我也不太懂,对每个数往前往后都扫一遍不也是O(n^2)么,DP也是O(n^2)? O(n)的解法就是两个pointer从头尾-1往中间扫是么?
回复 支持 反对

使用道具 举报

haobotao000 发表于 2016-8-25 14:11:51 | 显示全部楼层
zhangyanuuuuu 发表于 2016-8-23 23:26. visit 1point3acres.com for more.
第二题我也不太懂,对每个数往前往后都扫一遍不也是O(n^2)么,DP也是O(n^2)? O(n)的解法就是两个pointer从 ...

建立两个长度为n的数组,minA, maxA, where minA = min{A[1],...,A[i-1]} and maxA = max{A[i+1],...,A[n-1]}, 再loop数组A,for i in len(A): if minA<=A<=maxA, then return True.
由于建立minA,maxA和loop A的过程都是O(n),所以总时间是O(n).
回复 支持 反对

使用道具 举报

mooc 发表于 2016-8-30 03:06:53 | 显示全部楼层
lz 最后结果怎样?
回复 支持 反对

使用道具 举报

 楼主| jjustc 发表于 2016-8-30 09:22:22 | 显示全部楼层
一亩三分地严打"顶""好贴""收藏了"之类的垃圾回复帖!被警告三次,系统会自动封杀ID!

想支持楼主,请点击帖子下方的"好苗""分享""收藏"键,酌情给楼主加大米(系统不扣你自己的分)。.1point3acres缃
积分不够看不了帖子,请参考论坛导航里的"帮助","新手提纲"里有攒积分指南
回复 支持 反对

使用道具 举报

chen6145 发表于 2016-8-30 15:34:22 | 显示全部楼层
jjustc 发表于 2016-7-22 14:11. From 1point 3acres bbs
每次只读一个学生就是你在memory里maintain一个K大的数组(叫做KA吧),来存储当前你遇到的K个GPA最大的 ...

楼主bucket这个算法思路很棒啊,空间复杂度降到了O(1)。但这样时间复杂度是多少呢?
回复 支持 反对

使用道具 举报

 楼主| jjustc 发表于 2016-8-31 05:22:40 | 显示全部楼层
chen6145 发表于 2016-8-30 15:34
楼主bucket这个算法思路很棒啊,空间复杂度降到了O(1)。但这样时间复杂度是多少呢?

时间复杂度是O(N) 因为第一遍需要把所有人过一遍 放到对应的bucket里
回复 支持 反对

使用道具 举报

 楼主| jjustc 发表于 2016-8-31 05:23:46 | 显示全部楼层
mooc 发表于 2016-8-30 03:06
lz 最后结果怎样?

LZ最后收到了offer并且直接从了…………
回复 支持 反对

使用道具 举报

mooc 发表于 2016-8-31 06:04:25 | 显示全部楼层
jjustc 发表于 2016-8-31 05:23
LZ最后收到了offer并且直接从了…………

恭喜恭喜,lz为谷歌的面试准备了多久?都怎么准备的?
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-6 09:14

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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