谷歌google跪经

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

我刚要说类似于这个题。你已经说了 😆

chengbaokun 发表于 2016-11-22 23:57
是不是说初始化的时候 一定要存在三个一样的？可不可以初始化完之后在随便找三个连在一起的把它们candy改 ...

这个follow up问题的难点在于要随机化，也就是说要机会均等的返回一个满足条件的棋盘。这里条件是：1、不能有3个相同糖果连成一线；2、要存在两个相邻糖果，使得换位后会出现3个相同糖果连成一线（我才wiki 过candy crush的规则）。
若只有条件1的话就和LZ的题一样，很容易。但条件2很难在概率均等的意义下刻画。随便构造一个棋盘容易，但要机会均等我目前还没有想出怎么解决条件2。

我觉得第一题是可以用heap做的，不过要用一个wrapper class来帮助实现一个平均距离的comparator。最后结果是O((n+k)logn)
//Wrapper class to hold each distance and number of gas stations within
public class Wrapper{
    public int distance;
    public int stationCount;
    public Wrapper(int distance){this.distance = distance; this.stationCount = 1;}
}

int[] dist; //integer array to store the distance between each two adjancent gas stations
// wrapper with higher average distance has higher priority
PriorityQueue<Wrapper> queue = new PriorityQueue<Wrapper>(dist.length, new Comparator<Wrapper>{
    public int compare(Wrapper a, Wrapper b){
        return b.distance/b.stationCount - a.distance/a.stationCount;
    }
});

for (int d : dist)
{
    queue.offer(new Wrapper(d));
}
// k is the number of stations to be inserted
while (k > 0)
{
    Wrapper w = queue.poll();
    w.stationCount++;
    queue.offer(w);
    k--;
}

Wrapper res = queue.peek();
return res.distance/res.stationCount;

bruce2310 发表于 2016-11-23 23:22
我觉得第一题是可以用heap做的，不过要用一个wrapper class来帮助实现一个平均距离的comparator。最后结果 ...

嗯，这个就是正解了。前面catinclay 也提出了。这个"stationCount"感觉命名为“subintervalCount"是否更合理一些？还有初始化heap 的时间是nlogn 还是n呢？我也一直以为是nlogn, 但google 了好像可以n.

gougou9903 发表于 2016-11-21 09:52
第一题直接这样做是不对的，我一开始也是这么想的，小哥说不对，但是没给提示。你可以举个例子看看。
第 ...

Candy 问题：关键在于你的visited[][]设值的顺序是什么？若按先行再列或先列再行都是可以的。这样每次只要检查两个方向（因为剩下两个方向还没有放candy). 这样的过程是等概率的，因为每次对当前格子都等概率遍历所有合法的选择，相当于tree的level order traversal 最终到达每个leaf node恰好各一次。

补充内容 (2016-11-24 07:10):
我想了一下，我的方法也未必是等概率的。用3X1的棋盘验证即可，若4种candy的话共有60种棋盘，但我的方法给出12种以概率1/48出现，48种以概率1/64出现。不是每个1/60的等概率。

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

其中一种方法是先放一个
XOX                                                          XOO
OXO 这种的，然后放随机其他位置，注意不能放OXX 这一类的，因为棋子只有三种，放这一种pattern的话可能就要更多样子的棋子了。

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

请问面试官tricky 的方法是如何解决无死棋的情况的？

zzgzzm 发表于 2016-11-24 23:28
请问面试官tricky 的方法是如何解决无死棋的情况的？

就是我说的那种，只能用
XOX
OXO  
不能用
XOO
OXX 这种的， 因为我的限制条件是只有三种棋子，用这个的话可能需要更多地棋子，因为要判断三个方向

zzgzzm 发表于 2016-11-24 02:49
Candy 问题：关键在于你的visited[][]设值的顺序是什么？若按先行再列或先列再行都是可以的。这样每次只 ...

我认为这样是等概率的。比如按照一行一行来遍历，然后检查往左边两格以及往上两格。我算了一下，每个格子放置每种candy的概率都是1/3。不知道这样子算是等概率的随机吗？

spwahaha 发表于 2016-11-24 23:59
就是我说的那种，只能用
XOX
OXO  

请问，整个棋盘上，只需要有一个这种XOX OXO模式就可以了吧？比如，在开始的时候，就做一次这种设置，不需要每次都满足整个模式吧？那么之后的判断就跟原来的方法一样了呀（即每次判断两个方向，上面的和左边的）。不明白为什么XOO OXX这种需要做三个方向的判断呢？