买新车如何让dealer直接竞价?

一亩三分地论坛

 找回密码
 Sign Up 注册获取更多干货

最近看过此主题的会员

H1B/绿卡遥遥无期
又不想回国
来东南亚最大的互联网集团工作?
码农求职神器Triplebyte:
不用海投
内推多家公司面试
坐标湾区
Games Startup
招聘游戏开发工程师
游戏初创公司招聘工程师、UIUX Designer和游戏策划
查看: 4938|回复: 32
收起左侧

Google MTV onsite面经

[复制链接] |试试Instant~ |关注本帖
我的人缘0
knight0clk 发表于 2016-11-16 10:58:46 | 显示全部楼层 |阅读模式
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】

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

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

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

x
. 1point 3acres 论坛


收到信说过HC了,发面经求RP求大米。。
.本文原创自1point3acres论坛

某个周五去的

可能因为面试的楼里面都是做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。. 一亩-三分-地,独家发布
. from: 1point3acres
代码也是磕磕绊绊,两三个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. visit 1point3acres for more.
0 1 0
. more info on 1point3acres
返回:. 围观我们@1point 3 acres
1 0 1
2 1 0
0 1 0

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

然后中文聊了聊。

#lunch

午饭是同学校11年毕业的印度gg,带我走了一圈campus。。。. 牛人云集,一亩三分地

#3 白人gg

进来直接出题,给一个matrix of char,只有'-', 'o', 'S', 'X', '-'表示path,'o'表示wall, 求'S'到'x'的最短步骤。

比如. From 1point 3acres bbs
o o - o
S - - -. Waral 博客有更多文章,
o - o X
o - o o 来源一亩.三分地论坛.

BFS,不过我做BFS的套路估计小哥没见过,让我解释了一下怎么work的。最后应该是认可我的方法,然后说用queue怎么实现。代码还是有bug,最后改对了。.留学论坛-一亩-三分地
. from: 1point3acres
做BFS的时候,我把visited位置标记为'*',小哥说不改原来的matrix,也不新建matrix,怎么搞,那就用hashtable。小哥就顺势问坐标怎么hash。

又问,如果坐标范围很小,比如x在[x0, x1]内,怎么hash。
. 留学申请论坛-一亩三分地
这是唯一跟我说good luck的。。。.留学论坛-一亩-三分地

#4 华裔gg. 围观我们@1point 3 acres

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

把一个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. Waral 博客有更多文章,
.本文原创自1point3acres论坛
要求左右翻转,得到
. From 1point 3acres bbs1 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)

做法是row by row,每个row,用2个pointer相遇,先flip byte,然后swap。每个byte,写个函数做flip。
. From 1point 3acres bbs
复杂度是O(N),不能更好了。

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




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





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



补充内容 (2016-11-23 12:07):. 留学申请论坛-一亩三分地
发offer了,n^4那道题做成那样也能过我也很惊讶。。

评分

参与人数 2大米 +13 收起 理由
chasedream1 + 3 感谢分享!
kunge12345 + 10 欢迎来介绍你知道的情况

查看全部评分


上一篇:DoorDash电面二面
下一篇:LiveRamp 新鲜跪经(出现新题)

本帖被以下淘专辑推荐:

我的人缘0
 楼主| knight0clk 发表于 2016-11-17 02:27:19 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
oldwhite 发表于 2016-11-17 01:52.留学论坛-一亩-三分地
第二题能不能这么做:

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

. 一亩-三分-地,独家发布好像有道理,这样就是N^2了,因为每个位置只被更新一次。
回复 支持 1 反对 0

使用道具 举报

我的人缘0
 楼主| knight0clk 发表于 2016-11-24 06:09:25 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
海盗包子 发表于 2016-11-24 02:16
楼主是不是有 offer催的?我11.1onsite的上周收到邮件说要12.1做决定,还只是说了送了hc没有讲过没过。。 ...

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

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

使用道具 举报

我的人缘0
houqingniao 发表于 2016-11-16 11:43:33 | 显示全部楼层
  此人我要顶:
 
0% (0) 【我投】
  此人我要踩:
 
100% (1) 【我投】
Bless LZ. 感觉还不错啊, 希望拿下。. Waral 博客有更多文章,
第一题 处理duplicate,哪些算dup?你的例子中13, 13, 13算吗?
回复 支持 反对

使用道具 举报

我的人缘0
 楼主| knight0clk 发表于 2016-11-16 12:06:52 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
houqingniao 发表于 2016-11-16 11:43. from: 1point3acres
Bless LZ. 感觉还不错啊, 希望拿下。
第一题 处理duplicate,哪些算dup?你的例子中13, 13, 13算吗?

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

使用道具 举报

我的人缘0
fflute 发表于 2016-11-16 14:12:48 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
恭喜LZ! 请问是onsite后多久知道消息的?
回复 支持 反对

使用道具 举报

我的人缘0
cezheng2 发表于 2016-11-16 14:16:21 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
第二轮楼主的例子有误吧

1 0 1
1 1 0
0 1 0

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

不是应该返回:.1point3acres网
1 0 1. 围观我们@1point 3 acres
1 1 0
0 1 0

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

使用道具 举报

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

使用道具 举报

我的人缘0
Meetyourmaster 发表于 2016-11-16 17:17:11 | 显示全部楼层
  此人我要顶:
 
100% (7) 【我投】
  此人我要踩:
 
0% (0) 【我投】
请问lz是哪个周五面的..
回复 支持 反对

使用道具 举报

我的人缘0
鼓頔娜夫 发表于 2016-11-16 22:50:05 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
lz是在同时找实习和fulltime吗
回复 支持 反对

使用道具 举报

我的人缘0
 楼主| knight0clk 发表于 2016-11-17 01:36:28 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
fflute 发表于 2016-11-16 14:12
恭喜LZ! 请问是onsite后多久知道消息的?

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

使用道具 举报

我的人缘0
 楼主| knight0clk 发表于 2016-11-17 01:38:50 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
cezheng2 发表于 2016-11-16 14:16
第二轮楼主的例子有误吧

1 0 1
.1point3acres网
你说得对,[1,0]那个位置应该是1
-google 1point3acres
从某个0开始BFS是n^2,访问每个0要n^2,一共是n^4
回复 支持 反对

使用道具 举报

我的人缘0
 楼主| knight0clk 发表于 2016-11-17 01:41:42 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
zyoppy008 发表于 2016-11-16 16:37
我感觉楼主面的不好啊 第一轮很简单就leetcode变形 follow up就用counting sort 加circular array 应该bug  ...

我也觉得一般。。。T T
. visit 1point3acres for more.
第二轮怎么O(N)。。。。矩阵是N*N的,不是一共N个元素啊。。 即便如此,O(N^2)也是不够的吧
回复 支持 反对

使用道具 举报

我的人缘0
 楼主| knight0clk 发表于 2016-11-17 01:42:44 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
鼓頔娜夫 发表于 2016-11-16 22:50
lz是在同时找实习和fulltime吗

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

使用道具 举报

我的人缘0
鼓頔娜夫 发表于 2016-11-17 01:50:38 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
knight0clk 发表于 2016-11-17 01:42
另一个朋友账号米不够,借我号发帖的。。。。

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

使用道具 举报

我的人缘0
oldwhite 发表于 2016-11-17 01:52:56 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
第二题能不能这么做:

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

回复 支持 反对

使用道具 举报

我的人缘0
houqingniao 发表于 2016-11-17 01:59:58 | 显示全部楼层
  此人我要顶:
 
0% (0) 【我投】
  此人我要踩:
 
100% (1) 【我投】
knight0clk 发表于 2016-11-16 12:06
算啊,所以第一个13返回F,后面两个13就返回T。

你dup的意思是同个时间可以多个报错吗?
这个不需要map存吧?
回复 支持 反对

使用道具 举报

我的人缘0
 楼主| knight0clk 发表于 2016-11-17 02:28:24 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
houqingniao 发表于 2016-11-17 01:59. from: 1point3acres
你dup的意思是同个时间可以多个报错吗?
这个不需要map存吧?

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

使用道具 举报

我的人缘0
zyoppy008 发表于 2016-11-17 02:30:49 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
knight0clk 发表于 2016-11-17 01:41. 一亩-三分-地,独家发布
我也觉得一般。。。T T

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

不好意思 我说的意思是N 总个数 如果n 那确实n2
回复 支持 反对

使用道具 举报

我的人缘0
 楼主| knight0clk 发表于 2016-11-17 03:16:51 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
zyoppy008 发表于 2016-11-17 02:30
不好意思 我说的意思是N 总个数 如果n 那确实n2

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

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

使用道具 举报

我的人缘0
xihaokai1 发表于 2016-11-17 10:14:38 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
同过HC,多大概率会被拒呢?
回复 支持 反对

使用道具 举报

游客
请先登录

本版积分规则

提醒:发帖可以选择内容隐藏,部分板块支持匿名发帖。请认真读完以下全部说明:

■隐藏内容方法: [hide=200]你想要隐藏的内容比如面经[/hide]
■意思是:用户积分低于200则看不到被隐藏的内容
■可以自行设置积分值,不建议太高(200以上太多人看不到),也不建议太低(那就没必要隐藏了)
■建议只隐藏关键内容,比如具体的面试题目、涉及隐私的信息,大部分内容没必要隐藏。
■微信/QQ/电子邮件等,为防止将来被骚扰甚至人肉,以论坛私信方式发给对方最安全。
■匿名发帖的板块和方法:http://www.1point3acres.com/bbs/thread-405991-1-1.html

关闭

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

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

custom counter

GMT+8, 2018-6-22 17:21

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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