一亩三分地论坛

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

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

Google 5/27 MTV onsite

[复制链接] |试试Instant~ |关注本帖
Wingszero 发表于 2016-5-29 08:08:58 | 显示全部楼层 |阅读模式

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

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

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

x
Round 1
韩国人, 给定这类型的字符串:
“3a2[mtv]ac”,  decompress to: aaamtvmtvac,括号可以嵌套。
这个我觉得不是很难,大概花了15分钟理清了思路并写好了代码,大概就是找匹配括号递归解,面试官也找不到bug表示认同。

但吊诡的地方来了,面试官说把这种字符串compress回去...这显然有多种情况,于是我问是不是要求压缩后最短,面试官说肯定越短越好。
比如对于aaaa, 肯定4a比2[aa]好。
鏉ユ簮涓浜.涓夊垎鍦拌鍧.
我思考了一会,只想到了枚举所有substring及其连续出现次数,然后选择match出现次数最多的substring作为压缩。
面试官觉得复杂度高了,问还能不能优化,感觉他自己语气也不是很肯定,提示了一下我有没有类似two pointer的解法。
我个人觉得这道题真心不简单,没什么想法,一直卡到了这轮结束...

Round2
国人小哥,非常友善
1 在BST中给定[min, max] 求在此值域里的所有node之和. 简单递归.
2 一个数组里找某个index, 使sum[:i] == sum[i+1:], 也是经典题。我一开始用了O(n) space, follow up就是优化成了O(1).
这里代码写的有点慢,但都在没给提示的前提下bug free了。
3 上道题的变种,此时要求数组和带有权重,每个nums需要乘以一个weight, 这个weight等于和某个index的距离。
eg:
nums = [1, 3, 5, 7, 8]. visit 1point3acres.com for more.
假如当前处理到nums[2], 则leftsum = 1 * 2 + 3 * 1 = 5, rightsum = 7 * 1 + 8 * 2 = 23
这道题其实也不难,我找到思路后跟面试官说了,他表示赞同还举了举大拇指(人真是太好了),但时间不够我写代码了,只写了几行。
. 1point 3acres 璁哄潧
. from: 1point3acres.com/bbs
Round3
白人小叔+Shadow
1 walls and gates的变种,要求离各个gate距离之和最近的grid。经典题了.
2 randomize and return an array with value from 0 to n. 经典题了.
两道很快写完了之后,白人小哥看了一会都没发现什么问题,就说good, 然后就聊项目。
项目问题问得不深,所以足足聊了3个,他一直态度都不错但也没表现出对我的项目非常感兴趣的样子,就说good, cool之类的。

Round4. from: 1point3acres.com/bbs
中年烙印.鐣欏璁哄潧-涓浜-涓夊垎鍦
天啊, 又是各种听不懂...
1 buildfile with tag and dependency, return one of the invalid tags. Toposort搞之,但回家之后才发现自己搞错了复杂度...这里感觉会特别悲剧。
2 给一堆有序的单词和一个prefix, 叫你从单词里找出range是以这个prefix开头的, 我第一感觉是binary search。回头想了一下这题要是多次查询的话应该是用Trie, 但我写完代码之后已经时间不多,他也没问到。
两道题他都叫我写了好几个testcase验证,都没发现问题,但感觉他有拖时间的嫌疑.

总的来说题目比想象中水,但第一第四轮都面的不是很满意,还可以面的更好。下周二HR会打电话给feedback,希望有好一点的结果。
. visit 1point3acres.com for more.
. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴


补充内容 (2016-6-10 05:25):. From 1point 3acres bbs
Result: 昨天收到HR电话还是过不了HC,可加面转SETI, 因为手上有别的offer等着签于是放弃, 问feedback不肯说,自觉还是最后一轮面的不好。

本帖被以下淘专辑推荐:

 楼主| Wingszero 发表于 2016-5-29 08:26:54 | 显示全部楼层
关于第一题怎么compress的,大家有什么想法欢迎提出。
回复 支持 反对

使用道具 举报

wtcupup 发表于 2016-5-29 08:58:10 | 显示全部楼层
round 4 1 是类似于leetcode course schedule 2吗?
回复 支持 反对

使用道具 举报

wangmengcathy 发表于 2016-5-29 09:37:27 | 显示全部楼层
跟楼主同一天面的 为啥感觉画风完全不同...
回复 支持 反对

使用道具 举报

wangmengcathy 发表于 2016-5-29 09:38:47 | 显示全部楼层
LZ第一题是我店面题...
回复 支持 反对

使用道具 举报

edcent 发表于 2016-5-29 09:56:44 | 显示全部楼层
请问楼主2.2怎么优化成 O(1)的?
回复 支持 反对

使用道具 举报

wangmengcathy 发表于 2016-5-29 10:08:55 | 显示全部楼层
edcent 发表于 2016-5-29 09:56
请问楼主2.2怎么优化成 O(1)的?

先求个和 再从前扫当sum - presum = presum时就找到了吧
回复 支持 反对

使用道具 举报

 楼主| Wingszero 发表于 2016-5-29 10:12:36 | 显示全部楼层
wangmengcathy 发表于 2016-5-29 09:37
跟楼主同一天面的 为啥感觉画风完全不同...

你知道compress回去怎么做吗?
回复 支持 反对

使用道具 举报

 楼主| Wingszero 发表于 2016-5-29 10:15:16 | 显示全部楼层
wangmengcathy 发表于 2016-5-29 09:37. 1point3acres.com/bbs
跟楼主同一天面的 为啥感觉画风完全不同...

哈哈,是不是我的题太水了...
回复 支持 反对

使用道具 举报

oceanator 发表于 2016-5-29 13:12:37 | 显示全部楼层
感谢分享!请问楼主2.3的思路是什么?
回复 支持 反对

使用道具 举报

yzl232 发表于 2016-5-29 17:51:41 | 显示全部楼层
楼主面的不错啊。 感觉可以拿offer
回复 支持 反对

使用道具 举报

 楼主| Wingszero 发表于 2016-5-30 01:35:39 来自手机 | 显示全部楼层
oceanator 发表于 2016-5-29 13:12 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
感谢分享!请问楼主2.3的思路是什么?

你可以找个testcase算下相邻左子和之差。
回复 支持 反对

使用道具 举报

 楼主| Wingszero 发表于 2016-5-30 01:37:00 来自手机 | 显示全部楼层
yzl232 发表于 2016-5-29 17:51
楼主面的不错啊。 感觉可以拿offer
. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
承君贵言,但我自觉一四轮挺硬伤的,平常心吧。
回复 支持 反对

使用道具 举报

oceanator 发表于 2016-5-30 05:59:57 | 显示全部楼层
Wingszero 发表于 2016-5-30 01:35
你可以找个testcase算下相邻左子和之差。

谢谢!貌似每次往左移动都累加一次prefix sum和当前元素。。可以解了
回复 支持 反对

使用道具 举报

say543 发表于 2016-6-1 13:15:41 | 显示全部楼层
wangmengcathy 发表于 2016-5-29 09:38
LZ第一题是我店面题...


能分享怎么compress back as short as possible 吗 谢谢了
回复 支持 反对

使用道具 举报

poormm 发表于 2016-6-3 05:27:41 | 显示全部楼层
楼主有消息了么. from: 1point3acres.com/bbs
同等待ing
回复 支持 反对

使用道具 举报

 楼主| Wingszero 发表于 2016-6-3 05:49:23 | 显示全部楼层
poormm 发表于 2016-6-3 05:27
楼主有消息了么
同等待ing
.鏈枃鍘熷垱鑷1point3acres璁哄潧
还没呢,HR说最早这周末最迟下周。
回复 支持 反对

使用道具 举报

Judywan8888 发表于 2016-6-4 05:03:05 | 显示全部楼层
我的LG也还没消息,等得好心焦啊
回复 支持 反对

使用道具 举报

Judywan8888 发表于 2016-6-4 06:44:09 | 显示全部楼层
刚刚收到猎头电话, feed back positive, 周一电话详谈,希望有offer
回复 支持 反对

使用道具 举报

sal12 发表于 2016-7-1 13:37:42 | 显示全部楼层
Wingszero 发表于 2016-5-30 01:35
你可以找个testcase算下相邻左子和之差。

什么是相邻左子和之差?
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-3 17:37

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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