热乎乎的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

对给定的点反过来向上uphill做BFS，然后一个map记录矩阵上每个点被访问了几次。然后再来个for loop检查矩阵上被所有给定的点访问过的最高点。time complexity O(n).

反向bfs复杂度似乎没法降吧 应该还是O(kn)的吧 k是给的destination个数 n是矩阵所有点的个数?

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

恩，还是O(kn)

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

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

fishyuze 发表于 2015-4-7 05:29
弄个counting sort是线性的 否则难优化了吧 似乎可以规约到排序 然后证明基于比较的方法不可能更优了？

counting sort的N不能太大，但是这里是任意array。我没有想出什么更好的算法，所以只能从后台预处理的角度去做了，不知道有没有大神有更牛的算法。