房子的Insurance - 未名空间MITBBS历史存档

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

Redian新闻

>未名空间

>Living

房子的Insurance

房子的Insurance# Living

b*52013-09-10 07:09

1 楼

Generate a random starting board for Bejeweled:
Constraints:
1) No 3-in-a-rows of a particular color (horizontally or vertically)
2) At least one valid starting move (i.e., can swap two cells to get a 3-in-
a-row).
int[][] generateRandomBoard(int NColors, int N, int M)

r*i2013-09-10 07:09

2 楼

买了房子，下周close. 想问一下房屋保险哪里的比较好， costco么？我们目前车的
是Geico的，如果房子也用Geico，会便宜些么？
谢谢！

b*52013-09-10 07:09

3 楼

我用sudoku那题方法做

p*y2013-09-10 07:09

4 楼

广泛quote一下，找个coverage好又便宜的。

e*y2013-09-10 07:09

5 楼

sigh
没玩过这个游戏，做起题来岂不是很吃亏

in-

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

: Generate a random starting board for Bejeweled:
: Constraints:
: 1) No 3-in-a-rows of a particular color (horizontally or vertically)
: 2) At least one valid starting move (i.e., can swap two cells to get a 3-in-
: a-row).
: int[][] generateRandomBoard(int NColors, int N, int M)

E*A2013-09-10 07:09

6 楼

要朋友推荐一个代理

g*i2013-09-10 07:09

7 楼

曾经gg也问的我这道题记得是个android组的人问的
不过我的要求是在随机产生数这块的
LZ加油

b*52013-09-10 07:09

8 楼

哎，我这是店面，先上来聊背景，然后问了一堆multithread的问题，然后留了大
概20分钟叫我做这题。然后我先按照sudoku的答案，给他解答了不是random的，满
足第一个要求的。然后写完后，我口头上聊了聊，第二个要求，怎么modify我的
code。然后再简单说了说，要random，怎么modify我的code。。。
也不知道这样的店面，能不能有第二轮。。。

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

: 曾经gg也问的我这道题记得是个android组的人问的
: 不过我的要求是在随机产生数这块的
: LZ加油

l*n2013-09-10 07:09

9 楼

没什么思路，想这样做，不知道会不会被人鄙视：
public int[][] generateRandomBoard(int NColors, int N, int M) {
int[][] board = new int[N][M];
boolean isEnd = false;
while(!isEnd){
generateRandomBoard(board, NColors);
isEnd = checkBoard(board);
}
return board;
}
private void generateRandomBoard(int[][] board, int NColors) {
Random rm = new Random();
int N = board.length;
int M = board[0].length;
for(int i=0; ifor(int j=0; jint temp = Math.abs(rm.nextInt()%NColors);
while((i>=2 && temp==board[i-1][j] && temp==board[i-2][j])||(j>=
2 && temp==board[i][j-1] && temp==board[i][j-2])){
temp=Math.abs(rm.nextInt()%NColors);
}
board[i][j] = temp;
}
}
}
private boolean checkBoard(int[][] board){
int N = board.length;
int M = board[0].length;
for(int i=0; ifor(int j=0; j//check 合适的pattern，如果满足返回true；
}
}
return false;
}
合适的pattern比如说：
011
123
或者
01
01
13
就是check board[i][j]附近有没有在特定的两个位子跟他相等的。
只要NColor不是个特别小的数字，比如说2什么的，就能够基本上得到合适的board.如
果是2的话，第二个函数的while循环可能就停不下来了。。。。orz。。。

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

: 哎，我这是店面，先上来聊背景，然后问了一堆multithread的问题，然后留了大
: 概20分钟叫我做这题。然后我先按照sudoku的答案，给他解答了不是random的，满
: 足第一个要求的。然后写完后，我口头上聊了聊，第二个要求，怎么modify我的
: code。然后再简单说了说，要random，怎么modify我的code。。。
: 也不知道这样的店面，能不能有第二轮。。。

l*n2013-09-10 07:09

10 楼

二十分钟内要把code全部写完，考虑到所有的case然后bug free，好难。。。。

b*e2013-09-10 07:09

11 楼

这题要是我店面也做不出来。但是这题挺有意思的。我看分两步走：
第一步先把条件2满足了，也就是在一个随机的三连位置生成一个可调整的染色。
第二步从第一步结果的位置开始，从中间往两边，按对角线的方式扫描填色。按对角线
的原因是对角线上的染色互相无干涉。

in-

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

w*w2013-09-10 07:09

12 楼

先满足1 一个个字符的生成需要算 marginal probability 就是count符合条件的串的
数目条件2就用 check and rejection 就好因为符合条件的可能性不小

b*52013-09-10 07:09

13 楼

我是先按照sudoku那么做，然后要满足第二条件时，就是在一开始随机的三联位置生
成一个可调整的。
哎，谁说G家女马工去面，就容易。。我一个女马工，面过G家几次，店面都是这
么难，记得上次是一个二维DP，去onsite，题目见都没见过，听都没听说过。。。

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

: 这题要是我店面也做不出来。但是这题挺有意思的。我看分两步走：
: 第一步先把条件2满足了，也就是在一个随机的三连位置生成一个可调整的染色。
: 第二步从第一步结果的位置开始，从中间往两边，按对角线的方式扫描填色。按对角线
: 的原因是对角线上的染色互相无干涉。
:
: in-

b*52013-09-10 07:09

14 楼

顺便问问，店面后第二天没回音，是不是就没戏了

B*12013-09-10 07:09

15 楼

什么变态。问这种问题

★ 发自iPhone App: ChineseWeb 1.0.2

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

: 我是先按照sudoku那么做，然后要满足第二条件时，就是在一开始随机的三联位置生
: 成一个可调整的。
: 哎，谁说G家女马工去面，就容易。。我一个女马工，面过G家几次，店面都是这
: 么难，记得上次是一个二维DP，去onsite，题目见都没见过，听都没听说过。。。

h*e2013-09-10 07:09

16 楼

拍张你正在BBS发文的照片，P掉脸露乳沟，我们才知道你是不是女马工。

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

p*u2013-09-10 07:09

17 楼

lol 女马工 my ass...

【在 h****e 的大作中提到】

: 拍张你正在BBS发文的照片，P掉脸露乳沟，我们才知道你是不是女马工。

e*u2013-09-10 07:09

18 楼

我觉得我会先在所有颜色中, random选四种颜色,凑成一个方块. 一个小方块每种颜色
最多出现一次, 然后搭积木一样搭出来,这样能保证不会出现三个同颜色连在一起. 解
决了第一个问题.
第二个问题我觉得有很多种解法,是我要尽快想出的话,我会随机选一个两个连色的, 然
后修改离它们一个位置但是在同一条线上的颜色.

b*i2013-09-10 07:09

19 楼

不知道这个随机是怎么定义？
完全随机？就是所有满足1)和2)的棋盘等概率的出现？
如果不要求这个，其实还是蛮简单的

in-

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

b*52013-09-10 07:09

20 楼

如果不random，你怎么解？我是就sudoku解，然后在一开时的时候，放一个（0，0
）（1，0）（1，1）同样颜色的

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

: 不知道这个随机是怎么定义？
: 完全随机？就是所有满足1)和2)的棋盘等概率的出现？
: 如果不要求这个，其实还是蛮简单的
:
: in-

l*82013-09-10 07:09

21 楼

这道题要做到完全random挺难的
要么对每个生成的board检查一遍，看是否有valid move
要么随机生成valid move的坐标，类型，方向，颜色。。。再放到board中

，0

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

: 如果不random，你怎么解？我是就sudoku解，然后在一开时的时候，放一个（0，0
: ）（1，0）（1，1）同样颜色的

b*52013-09-10 07:09

22 楼

G家是悲剧了好多次了。每次都遇到这种难题。有哪个真能人说说到底怎么做？
我就是用soduku II的方法做， DFS加isValid。然后要满足第二个条件的话，就一
开始在（0，0），（1，0), (1,1) set to the same color，然后再DFS
能人说说这对不对啊？面试官也没说不对。就让我写。。。然后我问feedback，
recruiter说不能share feedback。。。。
random有怎么做呢？

h*k2013-09-10 07:09

23 楼

G onsite碰到这道题。思路是首先满足第二个条件，就是先random一个valid move，然
后开始一边fill board一边查相邻是否valid，是用sudoku那题的backtracking。表示
完整写完code时间不够，只写了个主要的结构，查valid的helper method跟面试官讨论
了下如何实现就没有写出来。

b*52013-09-10 07:09

24 楼

ok. 那我不就是差不多这么做的么？我就是先弄一下valid move，把（0，0），（1
，0），（1，1） set成同样地，然后我soduku，然后我写了整个的soduku II，就
是不知怎么random。。。我写完后，跟它说，你要random，就可以一开始set 那
个color的时候， random pick一下。。。。
我都写了，为什么还要据我? 而且，我写的时候，他也没有提出什么不对的。。。

【在 h***k 的大作中提到】

: G onsite碰到这道题。思路是首先满足第二个条件，就是先random一个valid move，然
: 后开始一边fill board一边查相邻是否valid，是用sudoku那题的backtracking。表示
: 完整写完code时间不够，只写了个主要的结构，查valid的helper method跟面试官讨论
: 了下如何实现就没有写出来。

w*w2013-09-10 07:09

25 楼

答案不是在这里了吗？概率问题无非就是数数你先数所有满足条件1的排列数不会就
从两种颜色 n=1,2,3 ... 数起数到5 6啥的总可以看出点规律来吧
没折暖男总喜欢套公式

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

: 先满足1 一个个字符的生成需要算 marginal probability 就是count符合条件的串的
: 数目条件2就用 check and rejection 就好因为符合条件的可能性不小

b*52013-09-10 07:09

26 楼

大姐，我是做不出来了，你给个code，让我看看呗。虽然我这店面，已经被拒了

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

: 答案不是在这里了吗？概率问题无非就是数数你先数所有满足条件1的排列数不会就
: 从两种颜色 n=1,2,3 ... 数起数到5 6啥的总可以看出点规律来吧
: 没折暖男总喜欢套公式

w*w2013-09-10 07:09

27 楼

看了有啥用呢？还是先数数吧

b*52013-09-10 07:09

28 楼

我数不清啊。你再说说清楚，或者给个pseudo code看看。。。

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

: 看了有啥用呢？还是先数数吧

r*g2013-09-10 07:09

29 楼

我对这题很迷糊，怎么感觉不用backtracing
当你需要新插入一个颜色的时候，只需要比较已经有的两个方向就行了，一个是当前方
格左边，一个是当前方格上边，只要保证新插入的颜色和这两个邻接格子颜色不同，就
可以保证没有3个格子是一样颜色，而且也满足了随机性。
估计所谓的随机性是要求每个格子插入每个颜色的概率是相等吧，但是我一下子推导不
出来概率是相等的。

n*s2013-09-10 07:09

30 楼

碰上这种题，还跟他费什么话啊，直接让他滚。

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

: 我数不清啊。你再说说清楚，或者给个pseudo code看看。。。

E*g2013-09-10 07:09

31 楼

这个方法好！

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

f*k2013-09-10 07:09

32 楼

思路是对的，先生成一行或一列同颜色的；
然后随机填满剩下所有cell，color的int随机取，用类似sudoku的方法validate每一次
取。
最后把同颜色列任取一个cell和旁边置换。

l*s2013-09-10 07:09

33 楼

I'm thinking filling out rest of cells around the random valid move a better
idea.

m*n2013-09-10 07:09

34 楼

如果我没理解错的话，你的代码生成的是一个固定的盘，而不是随机的。你说的换起始
颜色不改变盘的性质。
按六楼的思路写个满足第一条的解法，嘴上再把第二条扯一扯就行了。八楼是一个思路
。一个一个硬试也是个思路，谈谈复杂度啥的应该能混过去。

（1

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

: ok. 那我不就是差不多这么做的么？我就是先弄一下valid move，把（0，0），（1
: ，0），（1，1） set成同样地，然后我soduku，然后我写了整个的soduku II，就
: 是不知怎么random。。。我写完后，跟它说，你要random，就可以一开始set 那
: 个color的时候， random pick一下。。。。
: 我都写了，为什么还要据我? 而且，我写的时候，他也没有提出什么不对的。。。