谷歌google跪经

chengbaokun 发表于 2016-11-25 04:06
我认为这样是等概率的。比如按照一行一行来遍历，然后检查往左边两格以及往上两格。我算了一下，每个格子 ...

我也是这么想的，但算法bias在于前2个格子是完全自由度的，但第3个格子的概率分布又依赖于前2个格子的candy相同与否。例如两个合理3X3棋盘（假设共4种candy）：
A:        B:
112     123
112     231
221     312
生成A的概率=((1/4)(1/4)(1/3))^2*(1/3)^3=1/62208;
生成B的概率=(1/4)^9=1/262144。
这个差异的形成从位置(0,2)就开始了，A(0,2)=2的概率为1/3，B(0,2)=2的概率为1/4。或者说candy(0,0)==candy(0,1)的合理棋盘个数其实不等于candy(0,0)！=candy(0,1)的合理棋盘个数，但我的算法中因为顺序的原因用独立1/4等概率分别生成candy(0,0)和candy(0,1)，这个无法保证整体棋盘的等概率。

还可以简化的用一个3X1长方形验证：4种candy，合理棋盘显然有4^3-4=60种，所以若严格等概率应该每个合理棋盘以1/60概率生成。但实际上“candy(0,0)==candy(0,1)”类型的棋盘有12个，每个以概率1/48生成，而“candy(0,0)！=candy(0,1)”类型的棋盘有48个，每个以概率1/64生成.

所以“同类型”的合理棋盘概率的确是均等的，但不同类型的却不是。就看面试官是要求exactly均等还是尽量均等了。

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

你说的“需要更多的棋子，因为要判断三个方向”是什么意思？

新宿车站 发表于 2016-11-25 16:27
你说的“需要更多的棋子，因为要判断三个方向”是什么意思？

是的~~                        

zzgzzm 发表于 2016-11-22 04:11
第二题candy crash: 这个好像就是随机的一行一行从左向右生在board上成均匀随机数{1, 2, 3, 4}。在位置(i,j ...

想了一下，这题想要达到完全的等概率，很难

新宿车站 发表于 2016-11-26 00:48
想了一下，这题想要达到完全的等概率，很难

的确是。我就用最简单的3X1棋盘实验了一下（4种糖果），要真的每个合理棋盘以1/60等概率生成的话必须：
1. 第一个格子以1/4等概率随机生成；
2. 第二个格子以1/5的概率生成和第一个格子一样的糖果，以4/15的概率生成另一种不同糖果的3个中的一个；
3. 第三个格子若前两格子不同，以1/4等概率随机生成；否则以1/3等概率生成一个不同的糖果。
关键若生成的方法中涉及了格子特定的顺序的话就必然牵扯到条件概率，需要计算当前类型的合理棋盘的个数。而在现实N*N的棋盘中是不可能花费得起巨大的时间空间耗费将所有合理棋盘先穷尽再等概率随机返回一个。
以上纯技术讨论，面试中应该不需要。
我也很想知道真的candy crush game是如何初始化棋盘的 :-)

新宿车站 发表于 2016-11-25 16:27
你说的“需要更多的棋子，因为要判断三个方向”是什么意思？

spwahaha 的意思估计是这样：在 spwahaha 的问题中只给定有3种糖果，那么在初始化设计中一旦出现以下情形：
     1
     1
22？33
那么就无解了，因为"?"处放任何糖果都无法满足限制条件，就是因为它受到3个方向的制约。这个和给定了多少种糖果很关键。

zzgzzm 发表于 2016-11-26 03:17
spwahaha 的意思估计是这样：在 spwahaha 的问题中只给定有3种糖果，那么在初始化设计中一旦出现以下情 ...

对的对的，我的面试官限制糖果数目>=3

zzgzzm 发表于 2016-11-26 03:17
spwahaha 的意思估计是这样：在 spwahaha 的问题中只给定有3种糖果，那么在初始化设计中一旦出现以下情 ...

再分享一些东西， 我看了你的code， 在排除了两种糖果后可以用reservoir sampling 随机选剩余的糖果，这样没有额外空间，
我当时提出了一种思路，先放一种pattern后，从那个pettern的位置开始想四周BFS填糖果，这样是哪种pattern应该都可以，不过当时没有再顺着这个思路往下深究，面试官后来说这个思路也是可以的，不过不好coding(说follow up的时候也已经说不需要coding了)

spwahaha 发表于 2016-11-26 03:24
再分享一些东西， 我看了你的code， 在排除了两种糖果后可以用reservoir sampling 随机选剩余的糖果，这 ...

感谢reservoir sampling的提示, 我没想到这样可以避免定义繁琐的options[][]:

1.   for (int i = 0; i < n; ++i)
   
2.   for (int j = 0; j < n; ++j) {
   
3.     int vert = 0, hor = 0; // not allowed candy
   
4.     if (i > 1 && board[i-1][j] == board[i-2][j]) vert = board[i-1][j];
   
5.     if (j > 1 && board[i][j-1] == board[i][j-2]) hor  = board[i][j-1];
   
6.     int x = 1, mod = 1, count = 0;
   
7.     while (++count <= 3) { if (x == vert || x == hor || !rand()%(++mod)) x++; }
   
8.     board[i][j] = x;
   
9.   }

复制代码

补充内容 (2016-11-30 07:24):
Line 7应该改为：
  for (int c = 2; c <= 4; c++) {
    if (x == hor || x == vert) c = ++x;
    else if (c != hor && c != vert && !rand()%(++mod)) x = c;
  }

狗家最近好喜欢考水池抽样