一亩三分地论坛

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

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

[找工就业] Google MTV Onsite 12/11

[复制链接] |试试Instant~ |关注本帖
Labyrinth 发表于 2015-12-30 13:06:02 | 显示全部楼层 |阅读模式

2015(10-12月)-[]CS硕士+1-3年 - 猎头| 码农类全职@Google在职跳槽

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

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

x
第一轮:地里面有类似题目,一个只包含数字的字符串若旋转180度之后还等于其本身,则为valid字符串。如181, 906等。第一问,判断一个给定的字符串是否valid。第二问,生成长度小于n的所有合法字符串。两题都答完之后还有时间,就让我写了一个binary tree level order traverse。
第二轮是关于数据结构的。第一问,如何定义一个heap?(答案要点有三:a. binary tree b. complete tree c. 父节点值小于等于子节点) 。若从中取出k最小值,时间复杂度几何,答曰klgn。问有无更好方法,答可以构建一个新的heap,并把原heap的root放进来。每次从新heap中poll出最小值,然后再把poll出node的子node放入新heap。时间复杂度klnk。

第三轮是给定两个iterater,实现一个自定义的iterater接口,包含hasNext和next两个方法。例如iterater1返回13579,iterater2返回24680,那么你这个新的iterater就要返回1234567890。若两个iterater扩展到n个,又该如何实现?其间还分别分析了时间复杂度。.鏈枃鍘熷垱鑷1point3acres璁哄潧
. Waral 鍗氬鏈夋洿澶氭枃绔,
第四轮是两个人做游戏。给定一个字符串"------+++++------",每人每轮可以将相邻的两个加号变成减号,最后没有next move的人胜。第一问,给定一个字符串,生成所有合法的next move。第二问,给定一个字符串,判断其是否合法(要点是判断空字符串,以及包含加减号之外的符号)。然后再把这个isValid函数补充进第一问的答案中,放在什么地方合适,并且和面试官讨论了如果非法是选择抛出异常,还是返回空等问题。最后一个问题,给定一个字符串,写一个canWin函数,判断先手的player是否能获胜。要点是使用递归,先用第一问的函数生成nextMoves, 对每一个分别调用canWin。若任意一个返回false,则说明后手要输,那么先手者胜。-google 1point3acres

第五轮,warm up计算1!+2!+3!+...+n!。题目给定一些interval (start, end)。返回overlap最多时有几个interval。并返回开始和结束时间。我就把开始和结束时间分别sort一下,然后从头遍历,维护一个全局的max值这样。最后面试间说使用heap也可。但时间复杂度不比我的方法更好。
tltzhsajsdr 发表于 2015-12-30 15:48:47 | 显示全部楼层
楼主能再讲一下第一轮的第二题是为什么用两个heap可以实现Klgk的复杂度的吗,没看明白
回复 支持 反对

使用道具 举报

 楼主| Labyrinth 发表于 2015-12-30 16:03:40 | 显示全部楼层
tltzhsajsdr 发表于 2015-12-30 15:48
楼主能再讲一下第一轮的第二题是为什么用两个heap可以实现Klgk的复杂度的吗,没看明白

因为在新的heap中,每次拿出一个node就会放进去两个。也就是说每次heap的size加一。那么k次操作之后heap的大小就是k了。所以结果是klgk。
回复 支持 反对

使用道具 举报

bunnyNova 发表于 2015-12-30 16:36:24 | 显示全部楼层
比LZ晚一周面试,第二轮的题目一模一样。
回复 支持 反对

使用道具 举报

tltzhsajsdr 发表于 2015-12-31 00:22:14 | 显示全部楼层
Labyrinth 发表于 2015-12-30 16:03
因为在新的heap中,每次拿出一个node就会放进去两个。也就是说每次heap的size加一。那么k次操作之后heap ...

感谢楼主!祝楼主早日offer!
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-7 06:13

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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