热乎乎的Google Onsite面经

我自知不会做，所以就直接说我早上面试的时候做过这道题了，面试官一听就说，那我们就换一道吧

我好像学习到了不得了的技巧！

请问下第二轮第二道口袋题目，combine的最后是要combine成一个口袋是吗？

补充内容 (2015-4-9 13:05):
另外问下这道题最后要给出combine的顺序吗？还是只给出cost?

bobingmm 发表于 2015-4-9 13:02
请问下第二轮第二道口袋题目，combine的最后是要combine成一个口袋是吗？

补充内容 (2015-4-9 13:05):

最后combine成一个口袋，然后给出最小cost。具体解法可以google石子归并问题。

stochasticer 发表于 2015-4-8 17:10
问个很弱的问题。LZ的第一道题，我的思路和LZ基本一致，对给的每一个点BFS，然后最终扫描。写了一下code发 ...

我最后写在白板上的code基本和你一样（整整正反两面白板啊。。。）。唯一的一点不同就是我是用一个map记录每个点被visited了多少次，然后在最后查一遍整个矩阵里所有能到达的点并且最高的。其实写出来大体都一样。

第二轮的第二题是类似把一圈不同大小的石子堆归并起来吗？这是一道很经典的记忆化搜索的题，记录一下中间结果，O（N*N）

lilianwang 发表于 2015-4-19 08:32
第二轮的第二题是类似把一圈不同大小的石子堆归并起来吗？这是一道很经典的记忆化搜索的题，记录一下中间结 ...

沾沾你的喜气，希望有offer。

想问下石子归并的题能不能用greedy来做？
我的第一想法是每次scan整个数组然后找到加起来和是最小的一组 归并， 然后重新从头开始scan，这个情况下一共是扫这个数组n-1遍，所以时间复杂度是 o(n^2)；
具体例子是这样： 4 1 1 4 -> 4 2 4 -> 6 4 -> 10, sum = 2 + 6 + 10 = 18

我查了网上的办法大家都是用dp做的所以想问下我这个想法是不是在某些情况下不会得出最小的sum？

GirasoleY 发表于 2015-4-23 04:12
想问下石子归并的题能不能用greedy来做？
我的第一想法是每次scan整个数组然后找到加起来和是最小的一组  ...

因为题目要求只能combine相邻的两组，greedy只适用于每次combine任意两组

coolis 发表于 2015-4-7 03:49
恩，还是O(kn)

可以想象新建一个root，那些点是二层节点，就只要做一次bfs，palantir出过类似的题

applepie11 发表于 2015-4-7 11:56
硬币那个没明白

补充内容 (2015-4-7 22:26):

那一题你首先要算一个 a_1/1 + a_2 / 2 + .... a_n/n, where a_i is the number of coins in the i-th bag.
如果根据这个和的奇偶性来搞判断。