做题啦 - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>Joke - 肚皮舞运动

做题啦

做题啦# Joke - 肚皮舞运动

f*e2014-11-07 08:11

1 楼

别人面经
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)
有木有比较好的思路，大牛们来指点下。。

h*t2014-11-07 08:11

2 楼

Hi,
I have to sell two tickets for Li Jian World Tour 2016. The original price
is $194.10 for a pair, asking for $155 OBO. The seats are reserved for
Section RIGHT Row 40 Seat 36-38. Thanks!

l*t2014-11-07 08:11

3 楼

一天，有个年轻人来到小米步童鞋店里买了一双鞋子。这双鞋子成本是15元，标价是
21元。结果是这个年轻人掏出50元要买这双鞋子。小米步童鞋店当时没有零钱，用那
50元向街坊换了50元的零钱，找给年轻人29元。但是街坊後来发现那50元是假钞，小
米步童鞋店无奈之下，还了街坊50元。现在问题是：小米步童鞋店在这次交易中到底
损失了多少钱 ?

C*72014-11-07 08:11

4 楼

随便说一个
第一步：遍历M×N，每个点随机产生一种candy，同时检查左边和上面不形成3连。
第二步：重新遍历，每个点跟左边和上边2个位置尝试交换，如果能形成3连，结束。如
果到最后不能形成，全部重新生成一遍。
整体复杂度O(MN)，除非Q很大，重试概率会比较高。或者改善下第二步

p*f2014-11-07 08:11

5 楼

44?

【在 l****t 的大作中提到】

: 一天，有个年轻人来到小米步童鞋店里买了一双鞋子。这双鞋子成本是15元，标价是
: 21元。结果是这个年轻人掏出50元要买这双鞋子。小米步童鞋店当时没有零钱，用那
: 50元向街坊换了50元的零钱，找给年轻人29元。但是街坊後来发现那50元是假钞，小
: 米步童鞋店无奈之下，还了街坊50元。现在问题是：小米步童鞋店在这次交易中到底
: 损失了多少钱 ?

b*52014-11-07 08:11

6 楼

这好像是我的phone interview。。。前30分钟，聊天，和问multithreading。。。
留20分钟给我这题。。。

l*n2014-11-07 08:11

7 楼

－15+21-50

l*s2014-11-07 08:11

8 楼

start from the most naive way: add a valid move at position [0][0],[0][1],[0
][2],[0][3], then fill out rest of cells with rotating types.
then add random function to generate type at each cell's filling, while the
generated type need avoid 3 same type in a row of 3.

O*e2014-11-07 08:11

9 楼

街坊出来纯粹打酱油的

b*52014-11-07 08:11

10 楼

这个是uniformly random么？

[0
the

【在 l******s 的大作中提到】

: start from the most naive way: add a valid move at position [0][0],[0][1],[0
: ][2],[0][3], then fill out rest of cells with rotating types.
: then add random function to generate type at each cell's filling, while the
: generated type need avoid 3 same type in a row of 3.

Z*l2014-11-07 08:11

11 楼

年轻人买童鞋干嘛？

【在 l****t 的大作中提到】

l*s2014-11-07 08:11

12 楼

So far what I thought is it. And so probably it needs dfs + backtracking to
deal with cases of all types on the current cell occurs 3 same type in a row.

【在 b**********5 的大作中提到】

: 这个是uniformly random么？
:
: [0
: the

F*u2014-11-07 08:11

13 楼

如果钱是真的，算赚了6块还是不赔不赚？

【在 l****t 的大作中提到】

C*72014-11-07 08:11

14 楼

用户玩几次会发现第一步总在左上角

to
row.

【在 l******s 的大作中提到】

: So far what I thought is it. And so probably it needs dfs + backtracking to
: deal with cases of all types on the current cell occurs 3 same type in a row.

O*e2014-11-07 08:11

15 楼

应该是赚了
注意“在这场交易中”这个措辞
所以很直接的+6-50=44就ok了

【在 F*********u 的大作中提到】

: 如果钱是真的，算赚了6块还是不赔不赚？

j*82014-11-07 08:11

16 楼

不知道这是啥游戏的话是不是就直接拜拜了

d*f2014-11-07 08:11

17 楼

难度太低，应该改成请用common core math解此题

【在 l****t 的大作中提到】

l*s2014-11-07 08:11

18 楼

yes that was the beggining. You may random it to enhance it.

【在 C*7 的大作中提到】

: 用户玩几次会发现第一步总在左上角
:
: to
: row.

r*g2014-11-07 08:11

19 楼

mark

f*w2014-11-07 08:11

20 楼

如果只要求at least one valid move不是很简单吗
先随机生成3个连在一起的坐标，然后随机从这三个里面选一个移出去
然后完全随机地填剩下的格子，不过填的时候检查上下左右各2格保证没有3个同色
复杂度8*M*N

w*x2014-11-07 08:11

21 楼

我尝试写了一下code，好像Q>3的时候比较简单，Q=3的时候可能在一开始生成的附近会
无法填。Q=2的时候好像各种麻烦。

【在 f*******w 的大作中提到】

: 如果只要求at least one valid move不是很简单吗
: 先随机生成3个连在一起的坐标，然后随机从这三个里面选一个移出去
: 然后完全随机地填剩下的格子，不过填的时候检查上下左右各2格保证没有3个同色
: 复杂度8*M*N

r*g2014-11-07 08:11

22 楼

生成下面这种格式不就行了？
CBCABCABC
BCABCABCA
CABCABCAB
ABCABCABC
.........

g*d2014-11-07 08:11

23 楼

我觉得题目要求是给游戏初始化，如果按照这个模板生成，每次玩家的操作完全一样，
没有玩的意义了

【在 r*******g 的大作中提到】

: 生成下面这种格式不就行了？
: CBCABCABC
: BCABCABCA
: CABCABCAB
: ABCABCABC
: .........

f*w2014-11-07 08:11

24 楼

恩，不过这游戏Q<=3的时候应该就没有多少种valid的布局吧……

【在 w*x 的大作中提到】

: 我尝试写了一下code，好像Q>3的时候比较简单，Q=3的时候可能在一开始生成的附近会
: 无法填。Q=2的时候好像各种麻烦。

b*52014-11-07 08:11

25 楼

我的贴，题目清楚些
http://www.mitbbs.com/article_t1/JobHunting/32909899_0_1.html

【在 f*******w 的大作中提到】

:
: 恩，不过这游戏Q<=3的时候应该就没有多少种valid的布局吧……

w*x2014-11-07 08:11

26 楼

我还是感觉三色好像有问题，比如初始选的0向下移动后在原位置补的2，填的过程中可
能会出现下面这个情况
011
211
2X200
XX0
你那贴子有个对角线向外扩张填充，貌似能解决这个问题，但是我想不出来怎么去loop
这个对角线

【在 b**********5 的大作中提到】

:
: 我的贴，题目清楚些
: http://www.mitbbs.com/article_t1/JobHunting/32909899_0_1.html

w*x2014-11-07 08:11

27 楼

貌似原游戏有三色的？
Q=3感觉布局还是不少的，Q=2应该可以直接算作corner case用特殊的方法生成

【在 f*******w 的大作中提到】

:
: 恩，不过这游戏Q<=3的时候应该就没有多少种valid的布局吧……