http://www.1point3acres.com/bbs/thread-143308-1-1.html
Design a algorithm to initialize the board of Candy Crush Saga. With M x N board, Q types of candies. (Rules: no 3 for run after initialization, must contain at least one valid move at the beginning)
小哥说话很和气，先让我介绍了一个project，于是兴致勃勃地讲了做过的一个游戏。他于是拿出手机给我看了这个，说那就出一道游戏题吧。。游戏可以参考（
http://candycrushsaga.com/how-to-play），这道题很开放，没有固定模式和答案，感觉答的还不错
先把Candy简化成数字，类型数组就成了[0, 1, 2, ..., Q-1]。规则一共三条：随机（至少玩家看上去是）；不能一开始就有3个共线的；开局至少有一步能保证有消除（不然没法玩。。）
1. 我首先关注的是前两条规则，因为觉得第三条只是小修改（尽管如果初始化完成后，再修改成符合第三条，可能导致连锁反应）。因为“随机”一直在我心头挥之不去，所以首先想到的是遍历所有格子，每次随机挑一个Q放进去，但立刻意识到这样很有可能导致死锁，尤其Q很小的时候，然后举了个死锁的例子
2. 因为之前考虑过Q很小，所以最简单就是{0, 1}两种，立刻想到国际象棋棋盘：两色相间一定能填满而且无冲突。然后想到能不能先按照国际象棋棋盘填满，然后在这个基础上进行”随机化“。假如我有个遵循前两条规则的函数random()，对棋盘进行随机化。因为是在01棋盘改，所以第一遍下来可能还是很”假“，但既然这个函数是遵循前两条规则的，那么大可放心的多执行几遍。就像PS的滤镜叠加使用~ 然后开始讨论这个random()函数，大体思路是遍历棋盘，对每个格子有0.5 的概率进行”尝试修改“。(随机化就是一个慢慢tweak的过程，这个参数后面提到要根据实际效果调整）。尝试修改的算法就是：q = random(0, Q); 以q为中心向上下左右四个方向，一共有6条长度为3的线会造成潜在冲突，因此逐个检查一遍，假如无冲突就把当前位置替换为q。最后根据实际效果决定是否再来几次~
3. 然后就剩第三条规则：开局至少有一步能走。我上面阐述的时候就一直有个感觉，每局开始看似随机但一定有定势。然后让小哥打开手机游戏开了两局看了下，果然，每局开头一定会有{V型, _/型} 中的一种或两种排列，保证挪一步就能消除。跟小哥聊了这个想法之后，我的做法就是01棋盘生成后，随机选一个排列，比如V型，然后在棋盘上随机选一个（也可以多个）位置，把这个位置画出的V全部mark成不可修改。然后在这个基础上跑上面提到的random()算法。第三条规则也可以有很多随机性，必须类型选择，类型对应位置、个数的选择。
给一个字符串s由单词组成， 比如“i have a dream”。 要求把这个字符串添到一个m x n的网格里，同一个单词不能被cut off，每一句之间空格相连。问最多添满多少个整句。follow up （m and n are much larger than the length of s, 怎么办）
第二题：就相当于左对齐的排版一样，重复的吧一句话排列到版面上，问最多能排多少次。
Design a algorithm to initialize the board of Candy Crush Saga. With M x N board, Q types of candies. (Rules: no 3 for run after initialization, must contain at least one valid move at the beginning)
小哥说话很和气，先让我介绍了一个project，于是兴致勃勃地讲了做过的一个游戏。他于是拿出手机给我看了这个，说那就出一道游戏题吧。。游戏可以参考（
http://candycrushsaga.com/how-to-play），这道题很开放，没有固定模式和答案，感觉答的还不错
先把Candy简化成数字，类型数组就成了[0, 1, 2, ..., Q-1]。规则一共三条：随机（至少玩家看上去是）；不能一开始就有3个共线的；开局至少有一步能保证有消除（不然没法玩。。）
1. 我首先关注的是前两条规则，因为觉得第三条只是小修改（尽管如果初始化完成后，再修改成符合第三条，可能导致连锁反应）。因为“随机”一直在我心头挥之不去，所以首先想到的是遍历所有格子，每次随机挑一个Q放进去，但立刻意识到这样很有可能导致死锁，尤其Q很小的时候，然后举了个死锁的例子
2. 因为之前考虑过Q很小，所以最简单就是{0, 1}两种，立刻想到国际象棋棋盘：两色相间一定能填满而且无冲突。然后想到能不能先按照国际象棋棋盘填满，然后在这个基础上进行”随机化“。假如我有个遵循前两条规则的函数random()，对棋盘进行随机化。因为是在01棋盘改，所以第一遍下来可能还是很”假“，但既然这个函数是遵循前两条规则的，那么大可放心的多执行几遍。就像PS的滤镜叠加使用~ 然后开始讨论这个random()函数，大体思路是遍历棋盘，对每个格子有0.5 的概率进行”尝试修改“。(随机化就是一个慢慢tweak的过程，这个参数后面提到要根据实际效果调整）。尝试修改的算法就是：q = random(0, Q); 以q为中心向上下左右四个方向，一共有6条长度为3的线会造成潜在冲突，因此逐个检查一遍，假如无冲突就把当前位置替换为q。最后根据实际效果决定是否再来几次~
3. 然后就剩第三条规则：开局至少有一步能走。我上面阐述的时候就一直有个感觉，每局开始看似随机但一定有定势。然后让小哥打开手机游戏开了两局看了下，果然，每局开头一定会有{V型, _/型} 中的一种或两种排列，保证挪一步就能消除。跟小哥聊了这个想法之后，我的做法就是01棋盘生成后，随机选一个排列，比如V型，然后在棋盘上随机选一个（也可以多个）位置，把这个位置画出的V全部mark成不可修改。然后在这个基础上跑上面提到的random()算法。第三条规则也可以有很多随机性，必须类型选择，类型对应位置、个数的选择。
给一个字符串s由单词组成， 比如“i have a dream”。 要求把这个字符串添到一个m x n的网格里，同一个单词不能被cut off，每一句之间空格相连。问最多添满多少个整句。follow up （m and n are much larger than the length of s, 怎么办）
第二题：就相当于左对齐的排版一样，重复的吧一句话排列到版面上，问最多能排多少次。
