一亩三分地论坛

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

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

11.18 谷歌onsite面经【已拿到offer】

[复制链接] |试试Instant~ |关注本帖
ccccccc 发表于 2015-12-5 03:45:46 | 显示全部楼层 |阅读模式

2015(10-12月) 码农类 本科 全职@Google - 猎头 - Onsite |Pass在职跳槽

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

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

x
因为当年毕业的时候面过谷歌,过了phone interview就直接去MS把谷歌拒了,所以直接安排了onsite。

第一轮:
印度大叔。. visit 1point3acres.com for more.
问了工作经验,问得比较详细,我说的时候他一直在记录。
然后问了一个题,就是给出一堆string,按照一个自定义的字典序排列(a-z),求那个自定义的字典序。举例:bc, bbc, ab,求出来就是c-b-a。
followup是如何detect error: incomplete data and inconsistent data。incomplete指的是有的字母不知道是第几个,比如 az, bz就不知道z是怎么回事。inconsistent指的是有循环,比如算完发现a在b前,b在c前,c在a前。

第二轮:
欧洲大叔,说话挺不清楚的,不过人挺好。
先问了在C++里面vector, map, linkedlist的底层是怎么实现的,插入删除的时间复杂度,heap和BST的区别。
然后问了一个题,跟这个题一样:careercup上id为14424684。(原谅我不能发url。。。)


第三轮:
中国姐姐
第一题是给一个binary clock,hour的部分有4 bits,minute部分有6 bits,每个bit是0或者1,就是二进制.要求一共只有3个bit是1.问有哪些种valid combination。
第二题问了个design question。你有一个update,要发给远程的一堆机器,这些远程的机器在一起。问如何发过去。这里面有很多的假设和条件。比如,远程的机器很down了怎么办,发的update有data corruption怎么办,如果是bad update怎么办,server坏了怎么办,这些都是followup。

第四轮:
美国小叔
问的是design一个sparse matrix,实现两个功能,insert(int x, int y, int val)  在(x,y)插入val,和sum(int x1, int y1, int x2, int y2)左上到右下。要求sum有optimal time complexity。
. visit 1point3acres.com for more.
第五轮:
美国小哥
就一个design question。加入google要在每天进行search的人里随机选一个发一辆特斯拉,该如何选择。听着特容易,给个随机数不就好了,结果这题说了一个小时,因为要考虑到很多scalability和performance的问题,再加上谷歌有很多data center。
鏉ユ簮涓浜.涓夊垎鍦拌鍧.

面试一周以后hr通知hc通过啦~正在negotiate offer~大家好运~~

评分

5

查看全部评分

 楼主| ccccccc 发表于 2015-12-9 11:26:48 | 显示全部楼层
mingmingya 发表于 2015-12-8 15:26.鏈枃鍘熷垱鑷1point3acres璁哄潧
求第三轮和第五轮的设计题答案~还有读啥论文呢? 楼主大牛~
. 1point 3acres 璁哄潧
读Google File System那个论文。
第三题就是在远程加一个server,记录每个远程机器的状态,然后每次发update都发到那个server上,然后让server发给没down的机器。防止data corruption就是要加checksum,bad update就是要take snapshot,不行就滚回到之前的版本,都是论文里的内容。
. 1point 3acres 璁哄潧
第五个说着就略复杂了,总的说就是定一个数,比如1 million,如果找到这个人的时候他已经关了浏览器,就找2m个,以此类推。然后多个data center的情况要加一个prediction server,根据以往每天流量预测接下来一段时间各个data center的流量。快到1m的时候就开始记录,过了就停止,然后在log里面找第1m个。大致就是这样。
回复 支持 1 反对 0

使用道具 举报

ssross 发表于 2015-12-5 06:30:54 | 显示全部楼层
请问楼主工作了多久啦?怎么这么多design?
顺便求问楼主sparse matrix那题是就自己建了一个一个sum matrix吗?每个cell存的是(0,0)到这个坐标的矩阵的sum,然后sum的操作直接就可以变成O(1)了。
回复 支持 反对

使用道具 举报

mooc 发表于 2015-12-5 06:56:41 | 显示全部楼层
祝贺lz,请问你准备了多久,都怎么准备的。如何做到bug free的?
回复 支持 反对

使用道具 举报

 楼主| ccccccc 发表于 2015-12-5 08:04:01 | 显示全部楼层
ssross 发表于 2015-12-5 06:30. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
请问楼主工作了多久啦?怎么这么多design?
顺便求问楼主sparse matrix那题是就自己建了一个一个sum matri ...

我在微软干了两年,我也纳闷儿怎么这么多design。。。

sparse matrix那个题我是用map(hashtable)做的,key是row num,value是pair<int,int>,存的是当前row到x个column的和是多少。这样算sum的时候,比如x1, y1   x2, y2,直接看map里有没有x1这一行,如果有,就找到y1, y2对应的值,然后做减法,就是当前行的和,然后再算下一行。. Waral 鍗氬鏈夋洿澶氭枃绔,

你的做法也不错,我感觉比我做的好哈哈哈~~不过insert的时候要注意update所有相应的值。
回复 支持 反对

使用道具 举报

 楼主| ccccccc 发表于 2015-12-5 08:08:48 | 显示全部楼层
mooc 发表于 2015-12-5 06:56. From 1point 3acres bbs
祝贺lz,请问你准备了多久,都怎么准备的。如何做到bug free的?

我都是间歇的准备的,三天打鱼两天晒网,断断续续从夏天开始准备的。
这些题我都没bug free,都有小bug。我觉得bug free对于谷歌不是特别重要,因为他问的题不是很简单的那种,最重要的是逻辑清楚,能很好的跟面试官communicate。当然不能有特别大的bug,比如会导致重写半个白板的那种。
我就是刷了两遍leetcode的前200题,然后看看面经和design,再用一些别的公司练练手。(练手很重要)
回复 支持 反对

使用道具 举报

orangepie 发表于 2015-12-5 13:31:50 | 显示全部楼层
请问楼主是general hire 还是面试的specific team呢
回复 支持 反对

使用道具 举报

maomaoxiong 发表于 2015-12-5 15:43:54 | 显示全部楼层
恭喜!
第三轮第二题和最后一题怎么扯啊?
回复 支持 反对

使用道具 举报

LifeGoesOn 发表于 2015-12-5 16:17:36 | 显示全部楼层
第一题是给一个binary clock,hour的部分有4 bits,minute部分有6 bits,每个bit是0或者1,就是二进制.要求一共只有3个bit是1.问有哪些种valid combination。
. 鍥磋鎴戜滑@1point 3 acres请问LZ 这题用什么数据类型实现呢 一个int表示hour 一个int表示min吗 还是用两个byte来实现?
回复 支持 反对

使用道具 举报

LifeGoesOn 发表于 2015-12-6 06:47:56 | 显示全部楼层
ccccccc 发表于 2015-12-5 08:04
我在微软干了两年,我也纳闷儿怎么这么多design。。。

sparse matrix那个题我是用map(hashtable)做 ...

LZ 这题用segment tree了吗 , 不然的话 update  会cost O(n) 每次?
回复 支持 反对

使用道具 举报

 楼主| ccccccc 发表于 2015-12-7 03:35:41 | 显示全部楼层
orangepie 发表于 2015-12-5 13:31
请问楼主是general hire 还是面试的specific team呢

是general hire
回复 支持 反对

使用道具 举报

 楼主| ccccccc 发表于 2015-12-7 03:37:12 | 显示全部楼层
maomaoxiong 发表于 2015-12-5 15:43
恭喜!
第三轮第二题和最后一题怎么扯啊?

谢谢!!
那两个题主要的structure就是distributed system,找谷歌关于distributed system的论文看看,就知道该扯什么了。看论文真的对design question特别有用。
回复 支持 反对

使用道具 举报

 楼主| ccccccc 发表于 2015-12-7 03:41:17 | 显示全部楼层
LifeGoesOn 发表于 2015-12-5 16:17
第一题是给一个binary clock,hour的部分有4 bits,minute部分有6 bits,每个bit是0或者1,就是二进制.要求 ...

我用了两个int,返回值是vector<pair<int, int>>。
能用更小的数据类型存储当然更好,可是lz当时脑抽,午饭吃的有点儿多。唉~
记得要跟面试官交流,谈下为什么要用byte,有什么好处。
回复 支持 反对

使用道具 举报

 楼主| ccccccc 发表于 2015-12-7 03:44:29 | 显示全部楼层
LifeGoesOn 发表于 2015-12-6 06:47
LZ 这题用segment tree了吗 , 不然的话 update  会cost O(n) 每次?

没用segment tree,update确实会O(n)。
面试官当时主要说sum一定要最优,而且那个数据结构写出来已经很复杂了,我就没多想。不过如果提了用segment tree应该会更好,不过因为我平时没写过segment tree,也就没敢吹牛(实际是根本没想到哈哈)。
回复 支持 反对

使用道具 举报

queeniejing 发表于 2015-12-7 03:52:04 | 显示全部楼层
恭喜LZ啊, 沾沾LZ喜气, 也希望自己能有好运气
回复 支持 反对

使用道具 举报

dandanliuqian 发表于 2015-12-8 09:58:46 | 显示全部楼层
恭喜楼主啦! 请问楼主已经收到offer的具体数字了吗?  team match进展如何呢?
回复 支持 反对

使用道具 举报

ssross 发表于 2015-12-8 10:51:54 | 显示全部楼层
请问LZ system design的问题要写code的吗?
回复 支持 反对

使用道具 举报

 楼主| ccccccc 发表于 2015-12-8 13:25:58 | 显示全部楼层
dandanliuqian 发表于 2015-12-8 09:58
恭喜楼主啦! 请问楼主已经收到offer的具体数字了吗?  team match进展如何呢?

收到hc通过的通知是周五,接下来的周一就match到了一个组,现在正在negotiate package,已经差不多了。
回复 支持 反对

使用道具 举报

 楼主| ccccccc 发表于 2015-12-8 13:26:21 | 显示全部楼层
ssross 发表于 2015-12-8 10:51
请问LZ system design的问题要写code的吗?
. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
完全不用写code,都是画图和扯淡。
回复 支持 反对

使用道具 举报

mingmingya 发表于 2015-12-8 15:26:32 | 显示全部楼层
求第三轮和第五轮的设计题答案~还有读啥论文呢? 楼主大牛~
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-5 10:28

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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