Google 5/27 MTV onsite

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]
假如当前处理到nums[2], 则leftsum = 1 * 2 + 3 * 1 = 5, rightsum = 7 * 1 + 8 * 2 = 23
这道题其实也不难，我找到思路后跟面试官说了，他表示赞同还举了举大拇指（人真是太好了），但时间不够我写代码了，只写了几行。


Round3
白人小叔+Shadow

您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

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

总的来说题目比想象中水，但第一第四轮都面的不是很满意，还可以面的更好。下周二HR会打电话给feedback,希望有好一点的结果。




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

您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

关于第一题怎么compress的，大家有什么想法欢迎提出。

round 4 1 是类似于leetcode course schedule 2吗？

跟楼主同一天面的 为啥感觉画风完全不同...

LZ第一题是我店面题...

请问楼主2.2怎么优化成 O(1)的?

edcent 发表于 2016-5-29 09:56
请问楼主2.2怎么优化成 O(1)的?

先求个和 再从前扫当sum - presum = presum时就找到了吧

wangmengcathy 发表于 2016-5-29 09:37
跟楼主同一天面的 为啥感觉画风完全不同...

你知道compress回去怎么做吗？

wangmengcathy 发表于 2016-5-29 09:37
跟楼主同一天面的 为啥感觉画风完全不同...

哈哈，是不是我的题太水了...

感谢分享！请问楼主2.3的思路是什么？