问个MS面试题 - 未名空间MITBBS历史存档

P*U2012-03-05 08:03

1 楼

就是那个什么tie toe game，一个N*N的board，里面的数值为0或者1，只要任意一行全
为1或者任意一列全为1或者两个对角线中任意一个全为1，就输出true，否则输出false。
要求：不能用loop
如果N=3，能否不用loop且只用一个statement判断，不能是那种很长的if枚举各种case
的one statement。
面试官给的提示：把board存成一维的bit array，用到类似hashtable的思想
表示仍然不会做，有大牛支招吗？

n*s2012-03-05 08:03

2 楼

把所有可能的列出来

P*U2012-03-05 08:03

3 楼

说了不能是那种很长的if枚举各种case
的one statement。

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

: 把所有可能的列出来

n*s2012-03-05 08:03

4 楼

x[a1] = true
...
...

P*U2012-03-05 08:03

5 楼

什么意思？

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

: x[a1] = true
: ...
: ...

g*e2012-03-05 08:03

6 楼

你是ZJU的？

P*U2012-03-05 08:03

7 楼

额，是的，是不是这种题都不会做给ZJU丢人了哇，555

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

: 你是ZJU的？

f*22012-03-05 08:03

8 楼

没想出来，等解答

g*e2012-03-05 08:03

9 楼

是的你太菜了学长教你用数字电路里的思想 AND OR GATE 然后化简

【在 P*******U 的大作中提到】

: 额，是的，是不是这种题都不会做给ZJU丢人了哇，555

P*U2012-03-05 08:03

10 楼

我勒个去，学长V587，求个detail，怎么和hash扯上关系的！

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

:
: 是的你太菜了学长教你用数字电路里的思想 AND OR GATE 然后化简

g*e2012-03-05 08:03

11 楼

学长表示不会哈希

【在 P*******U 的大作中提到】

: 我勒个去，学长V587，求个detail，怎么和hash扯上关系的！

t*e2012-03-05 08:03

12 楼

I think he wants you to precalculate the result into an array. Then just one
array look up, you can get result. Array index is the state of 3 * 3 board.

s*n2012-03-05 08:03

13 楼

问题不是这么问的吧，如果他问大量查询怎么能加速，那预见表格还差不多。

one
.

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

: I think he wants you to precalculate the result into an array. Then just one
: array look up, you can get result. Array index is the state of 3 * 3 board.

e*l2012-03-05 08:03

14 楼

位运算。8种情况。这个算不算多。
比如x>>6==二进制111

p*22012-03-05 08:03

15 楼

如果用bit表示，用&就可以了吧？

P*U2012-03-05 08:03

16 楼

你是说把每一种case写成与，然后总的在各个与之间或吗？那样还是naive的枚举所有
case啊

【在 p*****2 的大作中提到】

: 如果用bit表示，用&就可以了吧？

h*w2012-03-05 08:03

17 楼

ZJU是 zhe jing da xue me？
准确来说1个if,N*N+2个&和N*N+1个|

r*b2012-03-05 08:03

18 楼

What the interviewer wanted to ask is to how to check the winning condition
while a Tic-Tac-Toe game is going on. We can use two arrays + two intergers
to record the number of 1s that appears in each row, column, diagonal, and
anti-diagonal.
http://basicalgos.blogspot.com/2012/03/13-test-winning-conditio

false。
case

【在 P*******U 的大作中提到】

: 就是那个什么tie toe game，一个N*N的board，里面的数值为0或者1，只要任意一行全
: 为1或者任意一列全为1或者两个对角线中任意一个全为1，就输出true，否则输出false。
: 要求：不能用loop
: 如果N=3，能否不用loop且只用一个statement判断，不能是那种很长的if枚举各种case
: 的one statement。
: 面试官给的提示：把board存成一维的bit array，用到类似hashtable的思想
: 表示仍然不会做，有大牛支招吗？

i*e2012-03-05 08:03

19 楼

赞同。
总共就只有 2^9=512 种状态，直接 table lookup。

one
.

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

: I think he wants you to precalculate the result into an array. Then just one
: array look up, you can get result. Array index is the state of 3 * 3 board.

c*p2012-03-05 08:03

20 楼

关键不是不让用loop么。。
建table的时候也得用loop建啊

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

: 赞同。
: 总共就只有 2^9=512 种状态，直接 table lookup。
:
: one
: .

i*e2012-03-05 08:03

21 楼

我手动初始化，行不 :P
反正运行效率高 :)
我不如地狱谁入地狱

【在 c****p 的大作中提到】

: 关键不是不让用loop么。。
: 建table的时候也得用loop建啊

f*n2012-03-05 08:03

22 楼

这个链接里的解法基本思路倒是不错，可是程序写的有bug啊。我还以为平常问这个问
题太简单了，看来还是可以继续问的。。。

condition
intergers

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

: What the interviewer wanted to ask is to how to check the winning condition
: while a Tic-Tac-Toe game is going on. We can use two arrays + two intergers
: to record the number of 1s that appears in each row, column, diagonal, and
: anti-diagonal.
: http://basicalgos.blogspot.com/2012/03/13-test-winning-conditio
:
: false。
: case

d*u2012-03-05 08:03

23 楼

R*92012-03-05 08:03

24 楼

是这个思路。。我面MS embedding组时有人出这个题目，interviewer解释说是table
lookup.

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

: 赞同。
: 总共就只有 2^9=512 种状态，直接 table lookup。
:
: one
: .

c*22012-03-05 08:03

25 楼

这个题有没有大牛贴个code让我们学习一下啊，感觉限制条件一堆，不知道该咋做

P*U2012-03-05 08:03

26 楼

就是那个什么tie toe game，一个N*N的board，里面的数值为0或者1，只要任意一行全
为1或者任意一列全为1或者两个对角线中任意一个全为1，就输出true，否则输出false。
要求：不能用loop
如果N=3，能否不用loop且只用一个statement判断，不能是那种很长的if枚举各种case
的one statement。
面试官给的提示：把board存成一维的bit array，用到类似hashtable的思想
表示仍然不会做，有大牛支招吗？

n*s2012-03-05 08:03

27 楼

把所有可能的列出来

P*U2012-03-05 08:03

28 楼

说了不能是那种很长的if枚举各种case
的one statement。

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

: 把所有可能的列出来

n*s2012-03-05 08:03

29 楼

x[a1] = true
...
...

P*U2012-03-05 08:03

30 楼

什么意思？

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

: x[a1] = true
: ...
: ...

g*e2012-03-05 08:03

31 楼

你是ZJU的？

P*U2012-03-05 08:03

32 楼

额，是的，是不是这种题都不会做给ZJU丢人了哇，555

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

: 你是ZJU的？

f*22012-03-05 08:03

33 楼

没想出来，等解答

g*e2012-03-05 08:03

34 楼

是的你太菜了学长教你用数字电路里的思想 AND OR GATE 然后化简

【在 P*******U 的大作中提到】

: 额，是的，是不是这种题都不会做给ZJU丢人了哇，555

P*U2012-03-05 08:03

35 楼

我勒个去，学长V587，求个detail，怎么和hash扯上关系的！

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

:
: 是的你太菜了学长教你用数字电路里的思想 AND OR GATE 然后化简

g*e2012-03-05 08:03

36 楼

学长表示不会哈希

【在 P*******U 的大作中提到】

: 我勒个去，学长V587，求个detail，怎么和hash扯上关系的！

t*e2012-03-05 08:03

37 楼

I think he wants you to precalculate the result into an array. Then just one
array look up, you can get result. Array index is the state of 3 * 3 board.

s*n2012-03-05 08:03

38 楼

问题不是这么问的吧，如果他问大量查询怎么能加速，那预见表格还差不多。

one
.

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

: I think he wants you to precalculate the result into an array. Then just one
: array look up, you can get result. Array index is the state of 3 * 3 board.

e*l2012-03-05 08:03

39 楼

位运算。8种情况。这个算不算多。
比如x>>6==二进制111

p*22012-03-05 08:03

40 楼

如果用bit表示，用&就可以了吧？

P*U2012-03-05 08:03

41 楼

你是说把每一种case写成与，然后总的在各个与之间或吗？那样还是naive的枚举所有
case啊

【在 p*****2 的大作中提到】

: 如果用bit表示，用&就可以了吧？

h*w2012-03-05 08:03

42 楼

ZJU是 zhe jing da xue me？
准确来说1个if,N*N+2个&和N*N+1个|

r*b2012-03-05 08:03

43 楼

What the interviewer wanted to ask is to how to check the winning condition
while a Tic-Tac-Toe game is going on. We can use two arrays + two intergers
to record the number of 1s that appears in each row, column, diagonal, and
anti-diagonal.
http://basicalgos.blogspot.com/2012/03/13-test-winning-conditio

false。
case

【在 P*******U 的大作中提到】

: 就是那个什么tie toe game，一个N*N的board，里面的数值为0或者1，只要任意一行全
: 为1或者任意一列全为1或者两个对角线中任意一个全为1，就输出true，否则输出false。
: 要求：不能用loop
: 如果N=3，能否不用loop且只用一个statement判断，不能是那种很长的if枚举各种case
: 的one statement。
: 面试官给的提示：把board存成一维的bit array，用到类似hashtable的思想
: 表示仍然不会做，有大牛支招吗？

i*e2012-03-05 08:03

44 楼

赞同。
总共就只有 2^9=512 种状态，直接 table lookup。

one
.

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

: I think he wants you to precalculate the result into an array. Then just one
: array look up, you can get result. Array index is the state of 3 * 3 board.

c*p2012-03-05 08:03

45 楼

关键不是不让用loop么。。
建table的时候也得用loop建啊

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

: 赞同。
: 总共就只有 2^9=512 种状态，直接 table lookup。
:
: one
: .

i*e2012-03-05 08:03

46 楼

我手动初始化，行不 :P
反正运行效率高 :)
我不如地狱谁入地狱

【在 c****p 的大作中提到】

: 关键不是不让用loop么。。
: 建table的时候也得用loop建啊

f*n2012-03-05 08:03

47 楼

这个链接里的解法基本思路倒是不错，可是程序写的有bug啊。我还以为平常问这个问
题太简单了，看来还是可以继续问的。。。

condition
intergers

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

: What the interviewer wanted to ask is to how to check the winning condition
: while a Tic-Tac-Toe game is going on. We can use two arrays + two intergers
: to record the number of 1s that appears in each row, column, diagonal, and
: anti-diagonal.
: http://basicalgos.blogspot.com/2012/03/13-test-winning-conditio
:
: false。
: case

d*u2012-03-05 08:03

48 楼

R*92012-03-05 08:03

49 楼

是这个思路。。我面MS embedding组时有人出这个题目，interviewer解释说是table
lookup.

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

: 赞同。
: 总共就只有 2^9=512 种状态，直接 table lookup。
:
: one
: .

c*22012-03-05 08:03

50 楼

这个题有没有大牛贴个code让我们学习一下啊，感觉限制条件一堆，不知道该咋做

l*82012-03-05 08:03

51 楼

8*8的board还可以用look-up table吗？

false。
case

【在 P*******U 的大作中提到】

: 就是那个什么tie toe game，一个N*N的board，里面的数值为0或者1，只要任意一行全
: 为1或者任意一列全为1或者两个对角线中任意一个全为1，就输出true，否则输出false。
: 要求：不能用loop
: 如果N=3，能否不用loop且只用一个statement判断，不能是那种很长的if枚举各种case
: 的one statement。
: 面试官给的提示：把board存成一维的bit array，用到类似hashtable的思想
: 表示仍然不会做，有大牛支招吗？

y*n2012-03-05 08:03

52 楼

如果对方强调不可用循环，我则首先考虑用递归。

C*U2012-03-05 08:03

53 楼

不知道这个想法对不对
把所有的行和列用一个table记录下里面1的个数
然后每次某个空格填了1就把对应的行或者列改一下数字

就是那个什么tie toe game，一个N*N的board，里面的数值为0或者1，只要任意一行全
为1或者任意一列全为1或者两个对角线中任意一个全为1，就输出true，否则输出.....
...
★ Sent from iPhone App: iReader Mitbbs 7.52 - iPad Lite

【在 P*******U 的大作中提到】

: 就是那个什么tie toe game，一个N*N的board，里面的数值为0或者1，只要任意一行全
: 为1或者任意一列全为1或者两个对角线中任意一个全为1，就输出true，否则输出false。
: 要求：不能用loop
: 如果N=3，能否不用loop且只用一个statement判断，不能是那种很长的if枚举各种case
: 的one statement。
: 面试官给的提示：把board存成一维的bit array，用到类似hashtable的思想
: 表示仍然不会做，有大牛支招吗？