San Jose各个房价 <1.5m 区域买房总结

一亩三分地论坛

 找回密码
 Sign Up 注册获取更多干货
E轮2.5亿美元融资
K12教育独角兽一起作业
北京-诚聘人工智能/教育/大数据岗
坐标湾区
Games Startup
招聘游戏开发工程师
游戏初创公司招聘工程师、UIUX Designer和游戏策划
码农求职神器Triplebyte:
不用海投
内推多家公司面试
把贵司招聘信息放这里
查看: 2450|回复: 4
收起左侧

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

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

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

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

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

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。. 1point3acres

第三轮是给定两个iterater,实现一个自定义的iterater接口,包含hasNext和next两个方法。例如iterater1返回13579,iterater2返回24680,那么你这个新的iterater就要返回1234567890。若两个iterater扩展到n个,又该如何实现?其间还分别分析了时间复杂度。

第四轮是两个人做游戏。给定一个字符串"------+++++------",每人每轮可以将相邻的两个加号变成减号,最后没有next move的人胜。第一问,给定一个字符串,生成所有合法的next move。第二问,给定一个字符串,判断其是否合法(要点是判断空字符串,以及包含加减号之外的符号)。然后再把这个isValid函数补充进第一问的答案中,放在什么地方合适,并且和面试官讨论了如果非法是选择抛出异常,还是返回空等问题。最后一个问题,给定一个字符串,写一个canWin函数,判断先手的player是否能获胜。要点是使用递归,先用第一问的函数生成nextMoves, 对每一个分别调用canWin。若任意一个返回false,则说明后手要输,那么先手者胜。

第五轮,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的复杂度的吗,没看明白
. 1point 3acres 论坛
因为在新的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!
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2018-5-26 08:52

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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