May 2009 - May 2017 论坛八周年-你的足迹,我的骄傲


一亩三分地论坛

 找回密码
 获取更多干活,快来注册

一亩三分地官方iOS手机应用下载
查看: 2888|回复: 31
收起左侧

Google MTV onsite面经

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

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

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

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

x



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


某个周五去的

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

除了最后一位,其他人都没什么表情。。。。
. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
4轮的题目好像都没怎么见过啊,说好google喜欢考DP的,也没有。。。
.鏈枃鍘熷垱鑷1point3acres璁哄潧
#1 国人gg. 鍥磋鎴戜滑@1point 3 acres

一个系统不定期抛出错误,每次有错误时会调用一次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. From 1point 3acres bbs

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

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

然后中文聊了聊。

#lunch
. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
午饭是同学校11年毕业的印度gg,带我走了一圈campus。。。

#3 白人gg
. From 1point 3acres bbs
进来直接出题,给一个matrix of char,只有'-', 'o', 'S', 'X', '-'表示path,'o'表示wall, 求'S'到'x'的最短步骤。

比如.1point3acres缃
o o - o
S - - -. 鍥磋鎴戜滑@1point 3 acres
o - o X
o - o o

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

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

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

#4 华裔gg

进来说终于到最后一轮了,人挺nice,还跟我客套了一会。

把一个bit image存在byte array里,比如:
0 0 0 0 0 0 0 1. Waral 鍗氬鏈夋洿澶氭枃绔,
0 0 0 0 0 0 1 0
0 0 0 0 0 1 0 0
0 0 0 0 1 0 0 0
. 鍥磋鎴戜滑@1point 3 acres就是-google 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
0 0 0 1 0 0 0 0

函数签名:void flip(int8 *image, int width, int height)-google 1point3acres
. 鍥磋鎴戜滑@1point 3 acres
做法是row by row,每个row,用2个pointer相遇,先flip byte,然后swap。每个byte,写个函数做flip。. from: 1point3acres.com/bbs

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

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



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





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


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

评分

1

查看全部评分

本帖被以下淘专辑推荐:

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

没催啊。。2周应该是正常时间吧. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴

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

使用道具 举报

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

使用道具 举报

 楼主| knight0clk 发表于 2016-11-16 12:06:52 | 显示全部楼层
houqingniao 发表于 2016-11-16 11:43
Bless LZ. 感觉还不错啊, 希望拿下。. visit 1point3acres.com for more.
第一题 处理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. 鍥磋鎴戜滑@1point 3 acres

返回:
1 0 1
2 1 0. visit 1point3acres.com for more.
0 1 0

不是应该返回:
1 0 1
1 1 0
0 1 0
. 鍥磋鎴戜滑@1point 3 acres
而且这个为啥是用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璁哄潧
地里有些比较难的面经 基本都差不多答出来也挂了 感觉楼主题不难表现也没有特别出彩 反而过了 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
第二轮楼主的例子有误吧-google 1point3acres

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
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
第二题能不能这么做:
.1point3acres缃
第一遍 先找所有0,把0填进去

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

使用道具 举报

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

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

使用道具 举报

zyoppy008 发表于 2016-11-17 02:30:49 | 显示全部楼层
knight0clk 发表于 2016-11-17 01:41
我也觉得一般。。。T T
. more info on 1point3acres.com
第二轮怎么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

看了上面的回复感觉你说的有道理。。。。
. from: 1point3acres.com/bbs
吓得我又看了一遍邮件
回复 支持 反对

使用道具 举报

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

使用道具 举报

本版积分规则

关闭

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

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

custom counter

GMT+8, 2017-5-29 17:43

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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