谷歌google跪经

flashpacker 发表于 2016-11-22 03:22
感觉第一题有点像lc410?

是啊，LC410相当于将n个加油站合并为k个，求合并的加油站的最大距离的最小值。

doorkeeper 发表于 2016-11-22 04:30
这个heap的复杂度是O(k*logn)吧，虽然应该也没什么差别
证明的话induction可以更清晰一些，可以直接比较 ...

heap方法的复杂度应该是O(加入站个数*log(原始站个数))，因为heap的size永远保持为（原始站个数-1），循环进行了“加入站个数”次数，可能n, k的定义不同吧

第二题和楼主一样，不过是3种糖果，然后follow up是如何初始化使board一定有可以用一步可以消的棋子(初始化完成后不能直接死棋).... 讨论了很久，但是还是没回答出来，最后面试官说的方法挺tricky的。。

spwahaha 发表于 2016-11-22 04:42
第二题和楼主一样，不过是3种糖果，然后follow up是如何初始化使board一定有可以用一步可以消的棋子(初始化 ...

请问follow up是怎么做的呢？

LZ 可以跟你讨论下第一题的做法么？假设现在有一个max和submax，然后我们要加入一个加油站，这个时候只能往max中间加才能保证接下来会得到的max最小。因为接下来能成为max的之后submax这个区间和max被分开的区间中的一个。有两种case：第一种是（max／2）>submax，此时若想minimize 接下来的max，就只能取中点。第二种是(max/2)<submax， 分析一下的话，还是只能取中点。

所以我觉得可以维持一个max heap，里面可以放interval， 然后对于新加进来的t个，每次都把最大的拆成两个再存回去。不知道这样对吗？

chengbaokun 发表于 2016-11-22 23:17
LZ 可以跟你讨论下第一题的做法么？假设现在有一个max和submax，然后我们要加入一个加油站，这个时候只能往 ...

我发现问题了 不对

shenzhenyz 发表于 2016-11-22 07:44
请问follow up是怎么做的呢？

是不是说初始化的时候 一定要存在三个一样的？可不可以初始化完之后在随便找三个连在一起的把它们candy改成一样的？

chengbaokun 发表于 2016-11-22 23:40
我发现问题了 不对

这个方法就是我面试时候想到的。。是不对的，看楼上有大神的解法，我还没仔细看。

gougou9903 发表于 2016-11-23 06:13
这个方法就是我面试时候想到的。。是不对的，看楼上有大神的解法，我还没仔细看。

嗯嗯 看到了～

gougou9903 发表于 2016-11-23 06:13
这个方法就是我面试时候想到的。。是不对的，看楼上有大神的解法，我还没仔细看。

嗯嗯 看到了～