一亩三分地论坛

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

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

Google MTV onsite面经

[复制链接] |试试Instant~ |关注本帖
knight0clk 发表于 2016-11-16 10:58:46 | 显示全部楼层 |阅读模式

2016(10-12月) 码农类 硕士 全职@Google - 内推 - Onsite |Passfresh grad应届毕业生

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

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

x



收到信说过HC了,发面经求RP求大米。。

.鐣欏璁哄潧-涓浜-涓夊垎鍦
某个周五去的

可能因为面试的楼里面都是做ads的,所以4轮+午饭,5个人里有4个做ads的。。。。。

除了最后一位,其他人都没什么表情。。。。

4轮的题目好像都没怎么见过啊,说好google喜欢考DP的,也没有。。。

#1 国人gg

一个系统不定期抛出错误,每次有错误时会调用一次alter(int timestamp)函数来检查在过去的period时间内出错数是否超过max_e,alert返回bool。可以认为当且仅当有一个新错误,alert才会被调用。

比如,出错时间为:1,3,3,8,10,13,13,13,20。给定max_e = 4, period = 5,那么每次出错后调用alert的结果依次为:F,F,F,F,F,F,T,T,F。第一个13返回F,因为8-13这段时间内一共3个报错,后面两个13返回T因为分别有4/5个报错。

可以用queue,每次alert就push,然后把过期的错误pop,然后检查size。

由于可能有duplicate,用hashmap存次数,遇到重复的就不push。

代码也是磕磕绊绊,两三个bug在提示下改对了。分析时间空间复杂度,然后分析平摊情况下的复杂度,这里也是给了提示才说出来。

follow up:上面的解法对小period大max_e比较友好,如果period大,而max_e小怎么做?我在面试官说out of time之后才想到,赶紧说只在queue里存max_e大小的元素,然后检查最早的元素是不是超出period。

#2 国人gg
鏉ユ簮涓浜.涓夊垎鍦拌鍧.
小哥好像对我项目领域有所涉猎,随便聊了聊。

出题,给matrix,里面只有1/0,至少一个是0。返回一个matrix,每个位置,如果原来是0,返回0,如果原来是1,返回走多少步可以到最近的0。

比如: 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
1 0 1
1 1 0
. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴0 1 0

返回:
1 0 1
2 1 0
0 1 0

没什么好办法,DFS,复杂度O(n^4)。后来想了想好像有个bug,但面试官当时也没指出来。

然后中文聊了聊。

#lunch

午饭是同学校11年毕业的印度gg,带我走了一圈campus。。。
. visit 1point3acres.com for more.
#3 白人gg

进来直接出题,给一个matrix of char,只有'-', 'o', 'S', 'X', '-'表示path,'o'表示wall, 求'S'到'x'的最短步骤。
. Waral 鍗氬鏈夋洿澶氭枃绔,
比如
o o - o
S - - -
o - o X
o - o o. 鍥磋鎴戜滑@1point 3 acres

BFS,不过我做BFS的套路估计小哥没见过,让我解释了一下怎么work的。最后应该是认可我的方法,然后说用queue怎么实现。代码还是有bug,最后改对了。

做BFS的时候,我把visited位置标记为'*',小哥说不改原来的matrix,也不新建matrix,怎么搞,那就用hashtable。小哥就顺势问坐标怎么hash。

又问,如果坐标范围很小,比如x在[x0, x1]内,怎么hash。

这是唯一跟我说good luck的。。。

#4 华裔gg

进来说终于到最后一轮了,人挺nice,还跟我客套了一会。
. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴.鏈枃鍘熷垱鑷1point3acres璁哄潧
把一个bit image存在byte array里,比如:
0 0 0 0 0 0 0 1
0 0 0 0 0 0 1 0
0 0 0 0 0 1 0 0
0 0 0 0 1 0 0 0
就是
.鏈枃鍘熷垱鑷1point3acres璁哄潧0x01 0x02 0x04 0x08

要求左右翻转,得到
1 0 0 0 0 0 0 0
0 1 0 0 0 0 0 0
0 0 1 0 0 0 0 0
. Waral 鍗氬鏈夋洿澶氭枃绔,0 0 0 1 0 0 0 0

函数签名:void flip(int8 *image, int width, int height)
-google 1point3acres
做法是row by row,每个row,用2个pointer相遇,先flip byte,然后swap。每个byte,写个函数做flip。

复杂度是O(N),不能更好了。

follow up: 怎么parallel优化,这里每个row可以独立处理,每个pair of byte可是独立,这两个比较naive。但是byte flip就不懂了,最后讨论了一下写了些公式,但我还是没看出怎么能比原来做的好。




是因为最近招聘季,大家比较累吗,面试官都没什么笑脸。。。。




. From 1point 3acres bbs
之前电面的帖子: http://www.1point3acres.com/bbs/thread-204586-1-1.html



补充内容 (2016-11-23 12:07):
发offer了,n^4那道题做成那样也能过我也很惊讶。。

评分

1

查看全部评分

本帖被以下淘专辑推荐:

 楼主| knight0clk 发表于 2016-11-24 06:09:25 | 显示全部楼层
海盗包子 发表于 2016-11-24 02:16
楼主是不是有 offer催的?我11.1onsite的上周收到邮件说要12.1做决定,还只是说了送了hc没有讲过没过。。 ...

没催啊。。2周应该是正常时间吧

你急的话发邮件给recruiter问一下进展吧,不过最近感恩节大家都休假不能保证工作效率。。
回复 支持 0 反对 1

使用道具 举报

houqingniao 发表于 2016-11-16 11:43:33 | 显示全部楼层
Bless LZ. 感觉还不错啊, 希望拿下。
第一题 处理duplicate,哪些算dup?你的例子中13, 13, 13算吗?
回复 支持 反对

使用道具 举报

 楼主| knight0clk 发表于 2016-11-16 12:06:52 | 显示全部楼层
houqingniao 发表于 2016-11-16 11:43
Bless LZ. 感觉还不错啊, 希望拿下。
第一题 处理duplicate,哪些算dup?你的例子中13, 13, 13算吗?

算啊,所以第一个13返回F,后面两个13就返回T。
回复 支持 反对

使用道具 举报

fflute 发表于 2016-11-16 14:12:48 | 显示全部楼层
恭喜LZ! 请问是onsite后多久知道消息的?
回复 支持 反对

使用道具 举报

cezheng2 发表于 2016-11-16 14:16:21 | 显示全部楼层
第二轮楼主的例子有误吧. visit 1point3acres.com for more.

1 0 1
1 1 0
0 1 0

返回:
1 0 1
2 1 0
0 1 0. visit 1point3acres.com for more.
.1point3acres缃
不是应该返回:
1 0 1
1 1 0
0 1 0. more info on 1point3acres.com

而且这个为啥是用DFS O(n^4)做,不是先扫一遍矩阵找出所有的0,然后从这些0开始BFS,O(n^2)?是我理解错楼主说的题意了么
回复 支持 反对

使用道具 举报

zyoppy008 发表于 2016-11-16 16:37:04 | 显示全部楼层
我感觉楼主面的不好啊 第一轮很简单就leetcode变形 follow up就用counting sort 加circular array 应该bug free的 第二轮 明显也是原题变形啊 bfs o(n) 可解 第三轮类似第二轮还更简单 第四轮 没看明白
地里有些比较难的面经 基本都差不多答出来也挂了 感觉楼主题不难表现也没有特别出彩 反而过了 g家标准有点迷啊
回复 支持 反对

使用道具 举报

Meetyourmaster 发表于 2016-11-16 17:17:11 | 显示全部楼层
请问lz是哪个周五面的..
回复 支持 反对

使用道具 举报

鼓頔娜夫 发表于 2016-11-16 22:50:05 | 显示全部楼层
lz是在同时找实习和fulltime吗
回复 支持 反对

使用道具 举报

 楼主| knight0clk 发表于 2016-11-17 01:36:28 | 显示全部楼层
fflute 发表于 2016-11-16 14:12
恭喜LZ! 请问是onsite后多久知道消息的?

一周以上,字数字数
回复 支持 反对

使用道具 举报

 楼主| knight0clk 发表于 2016-11-17 01:38:50 | 显示全部楼层
cezheng2 发表于 2016-11-16 14:16 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
第二轮楼主的例子有误吧

1 0 1

你说得对,[1,0]那个位置应该是1
. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
从某个0开始BFS是n^2,访问每个0要n^2,一共是n^4
回复 支持 反对

使用道具 举报

 楼主| knight0clk 发表于 2016-11-17 01:41:42 | 显示全部楼层
zyoppy008 发表于 2016-11-16 16:37
我感觉楼主面的不好啊 第一轮很简单就leetcode变形 follow up就用counting sort 加circular array 应该bug  ...

我也觉得一般。。。T T. 1point 3acres 璁哄潧

第二轮怎么O(N)。。。。矩阵是N*N的,不是一共N个元素啊。。 即便如此,O(N^2)也是不够的吧
回复 支持 反对

使用道具 举报

 楼主| knight0clk 发表于 2016-11-17 01:42:44 | 显示全部楼层
鼓頔娜夫 发表于 2016-11-16 22:50
lz是在同时找实习和fulltime吗

另一个朋友账号米不够,借我号发帖的。。。。
回复 支持 反对

使用道具 举报

鼓頔娜夫 发表于 2016-11-17 01:50:38 | 显示全部楼层
knight0clk 发表于 2016-11-17 01:42
另一个朋友账号米不够,借我号发帖的。。。。

哈哈。。我都看凌乱了。。
回复 支持 反对

使用道具 举报

oldwhite 发表于 2016-11-17 01:52:56 | 显示全部楼层
第二题能不能这么做:

第一遍 先找所有0,把0填进去
第二遍 根据之前的0,所有跟0接近的没填上的格子标为1
第三遍 根据之前的1,所有跟1接近的没填上的格子标为2
以此类推 直到所有格子被填满

回复 支持 反对

使用道具 举报

houqingniao 发表于 2016-11-17 01:59:58 | 显示全部楼层
knight0clk 发表于 2016-11-16 12:06
算啊,所以第一个13返回F,后面两个13就返回T。

你dup的意思是同个时间可以多个报错吗?. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
这个不需要map存吧?
回复 支持 反对

使用道具 举报

 楼主| knight0clk 发表于 2016-11-17 02:27:19 | 显示全部楼层
oldwhite 发表于 2016-11-17 01:52
第二题能不能这么做:

第一遍 先找所有0,把0填进去

好像有道理,这样就是N^2了,因为每个位置只被更新一次。
回复 支持 反对

使用道具 举报

 楼主| knight0clk 发表于 2016-11-17 02:28:24 | 显示全部楼层
houqingniao 发表于 2016-11-17 01:59
你dup的意思是同个时间可以多个报错吗?
这个不需要map存吧?

对,同个时间多个报错。所以要存下来每个时间报了多少错,用一个hashmap存。
回复 支持 反对

使用道具 举报

zyoppy008 发表于 2016-11-17 02:30:49 | 显示全部楼层
knight0clk 发表于 2016-11-17 01:41. From 1point 3acres bbs
我也觉得一般。。。T T

第二轮怎么O(N)。。。。矩阵是N*N的,不是一共N个元素啊。。 即便如此,O(N ...
. 1point3acres.com/bbs
不好意思 我说的意思是N 总个数 如果n 那确实n2
回复 支持 反对

使用道具 举报

 楼主| knight0clk 发表于 2016-11-17 03:16:51 | 显示全部楼层
zyoppy008 发表于 2016-11-17 02:30
不好意思 我说的意思是N 总个数 如果n 那确实n2

看了上面的回复感觉你说的有道理。。。。

吓得我又看了一遍邮件
回复 支持 反对

使用道具 举报

xihaokai1 发表于 2016-11-17 10:14:38 | 显示全部楼层
同过HC,多大概率会被拒呢?
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-10 01:58

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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