热乎乎的Google Onsite面经

Arthur2012 发表于 2015-4-6 08:54
lz的第二面第三题是石子归并问题，如果给出O(n^3)的解法不知道可不可以。

看了lz描述，半天没看懂题意，到你这里豁然开朗

第四题太坑了，后台预处理，那啥问题都能线型了，还搞毛啊。楼主也真够冒险的，他们面试官其实能看到之前人出的题目的，后面系统里好像也能查，要是写到comment里。。。

Arthur2012 发表于 2015-4-6 08:54
lz的第二面第三题是石子归并问题，如果给出O(n^3)的解法不知道可不可以。

石子归并？  这个题感觉就是算法导论上  Matrix multiplication的变种吧   递归指数级  DP的话n^3

狂暴CNM地 发表于 2015-4-6 23:21
石子归并？  这个题感觉就是算法导论上  Matrix multiplication的变种吧   递归指数级  DP的话n^3

恩恩，矩阵连乘的变种，DP可以优化到n^2
http://blog.csdn.net/acdreamers/article/details/18039073

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

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

fishyuze 发表于 2015-4-7 03:06
反向bfs复杂度似乎没法降吧 应该还是O(kn)的吧 k是给的destination个数 n是矩阵所有点的个数?

恩，还是O(kn)

面试官说sort是个好方法，但有没有更好一点的，我一听，这是要linear时间啊，

弄个counting sort是线性的 否则难优化了吧 似乎可以规约到排序 然后证明基于比较的方法不可能更优了？

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

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