一亩三分地论坛

 找回密码
 Sign Up 注册获取更多干货
码农求职神器Triplebyte:
不用海投,内推你去多家公司面试
Airbnb 数据科学职位
in analytics and inference
天天打游戏、照样领工资,
你要不要来?
把贵司招聘信息放这里
查看: 4376|回复: 32
收起左侧

Google MTV onsite面经

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

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

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

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

x



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

. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
某个周五去的

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

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

4轮的题目好像都没怎么见过啊,说好google喜欢考DP的,也没有。。。
. 鍥磋鎴戜滑@1point 3 acres
#1 国人gg

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

比如,出错时间为: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个报错。
. Waral 鍗氬鏈夋洿澶氭枃绔,
可以用queue,每次alert就push,然后把过期的错误pop,然后检查size。-google 1point3acres

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

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

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

#2 国人gg. more info on 1point3acres.com

小哥好像对我项目领域有所涉猎,随便聊了聊。. 鍥磋鎴戜滑@1point 3 acres

出题,给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
. 1point 3acres 璁哄潧
没什么好办法,DFS,复杂度O(n^4)。后来想了想好像有个bug,但面试官当时也没指出来。

然后中文聊了聊。

#lunch 鏉ユ簮涓浜.涓夊垎鍦拌鍧.

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

进来直接出题,给一个matrix of char,只有'-', 'o', 'S', 'X', '-'表示path,'o'表示wall, 求'S'到'x'的最短步骤。
.鐣欏璁哄潧-涓浜-涓夊垎鍦
比如
o o - o
S - - -
.鐣欏璁哄潧-涓浜-涓夊垎鍦o - o X
o - o o

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

做BFS的时候,我把visited位置标记为'*',小哥说不改原来的matrix,也不新建matrix,怎么搞,那就用hashtable。小哥就顺势问坐标怎么hash。
. visit 1point3acres.com for more.
又问,如果坐标范围很小,比如x在[x0, x1]内,怎么hash。

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

#4 华裔gg. 1point3acres.com/bbs

进来说终于到最后一轮了,人挺nice,还跟我客套了一会。
.1point3acres缃
把一个bit image存在byte array里,比如:. more info on 1point3acres.com
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.鐣欏璁哄潧-涓浜-涓夊垎鍦
就是
0x01 0x02 0x04 0x08. more info on 1point3acres.com

要求左右翻转,得到
1 0 0 0 0 0 0 0. from: 1point3acres.com/bbs
0 1 0 0 0 0 0 0
0 0 1 0 0 0 0 0
0 0 0 1 0 0 0 0

函数签名:void flip(int8 *image, int width, int height)

做法是row by row,每个row,用2个pointer相遇,先flip byte,然后swap。每个byte,写个函数做flip。 鏉ユ簮涓浜.涓夊垎鍦拌鍧.

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

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



. from: 1point3acres.com/bbs
是因为最近招聘季,大家比较累吗,面试官都没什么笑脸。。。。





之前电面的帖子: http://www.1point3acres.com/bbs/thread-204586-1-1.html. 鍥磋鎴戜滑@1point 3 acres
. From 1point 3acres bbs


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

评分

2

查看全部评分

本帖被以下淘专辑推荐:

 楼主| knight0clk 发表于 2016-11-17 02:27:19 | 显示全部楼层
oldwhite 发表于 2016-11-17 01:52
第二题能不能这么做:. 1point3acres.com/bbs
. visit 1point3acres.com for more.
第一遍 先找所有0,把0填进去

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

使用道具 举报

 楼主| 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. 感觉还不错啊, 希望拿下。
. from: 1point3acres.com/bbs 第一题 处理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 | 显示全部楼层
第二轮楼主的例子有误吧

1 0 1
1 1 0
0 1 0
. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
返回:
1 0 1. more info on 1point3acres.com
2 1 0.鐣欏璁哄潧-涓浜-涓夊垎鍦
0 1 0

不是应该返回:
1 0 1. 1point3acres.com/bbs
1 1 0
0 1 0

而且这个为啥是用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) 可解 第三轮类似第二轮还更简单 第四轮 没看明白 . 1point3acres.com/bbs
地里有些比较难的面经 基本都差不多答出来也挂了 感觉楼主题不难表现也没有特别出彩 反而过了 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. Waral 鍗氬鏈夋洿澶氭枃绔,
第二轮楼主的例子有误吧

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

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

使用道具 举报

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

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

使用道具 举报

鼓頔娜夫 发表于 2016-11-17 01:50:38 | 显示全部楼层
knight0clk 发表于 2016-11-17 01:42
另一个朋友账号米不够,借我号发帖的。。。。
. 1point3acres.com/bbs
哈哈。。我都看凌乱了。。
回复 支持 反对

使用道具 举报

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

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

使用道具 举报

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

第二轮怎么O(N)。。。。矩阵是N*N的,不是一共N个元素啊。。 即便如此,O(N ...

不好意思 我说的意思是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,多大概率会被拒呢?
回复 支持 反对

使用道具 举报

本版积分规则

关闭

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

手机版|小黑屋|一亩三分地论坛声明

custom counter

GMT+8, 2017-12-14 21:23

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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