d********w
发帖数: 363 | 1 某个公司的面试题，算是我见过最难的了。
给出一个棋盘，比如10*10大小，有2个选手，每个人交替下。每个人手上有7个字母可
以用，给定一个字典
第一问 只考虑一个棋手，
他需要利用手中的字母，放在棋盘上空格中，必须是一个单词（单词可以在字典中查到
），每个字母会有个权重，目标是value最大化。
例如：7个字母为：
a, a, a, b, d, n, n
如果字典里面存在如下单词
and
band
banana
而权重表
a:1
b:2
d:3
n:5
那么他的策略是选个最大的，banana value:15
第二问：考虑到第二个棋手
他也是要利用手上的7个字母，放若干在棋盘上，他必须放在棋手1相邻的位置上，比如
他的上一行，或者右边紧邻的一列，只能横放或者竖放，但必须是跟之前的单词有交接
的，而且他要保证棋盘上有字母的每一行，每一列都是个单词,
如：
他手上的字母是：h,u,n,t,i,n,g
h
u
b a n a n a
t
i
n
g
最后目标是棋盘上的单词价值最大化。 | h*c
发帖数: 1859 | 2 美国人喜欢玩这个游戏。。。
scrabble还是啥
【在 d********w 的大作中提到】
: 某个公司的面试题，算是我见过最难的了。
: 给出一个棋盘，比如10*10大小，有2个选手，每个人交替下。每个人手上有7个字母可
: 以用，给定一个字典
: 第一问 只考虑一个棋手，
: 他需要利用手中的字母，放在棋盘上空格中，必须是一个单词（单词可以在字典中查到
: ），每个字母会有个权重，目标是value最大化。
: 例如：7个字母为：
: a, a, a, b, d, n, n
: 如果字典里面存在如下单词
: and
| b***u
发帖数: 12010 | 3 听着像g的题
【在 d********w 的大作中提到】
: 某个公司的面试题，算是我见过最难的了。
: 给出一个棋盘，比如10*10大小，有2个选手，每个人交替下。每个人手上有7个字母可
: 以用，给定一个字典
: 第一问 只考虑一个棋手，
: 他需要利用手中的字母，放在棋盘上空格中，必须是一个单词（单词可以在字典中查到
: ），每个字母会有个权重，目标是value最大化。
: 例如：7个字母为：
: a, a, a, b, d, n, n
: 如果字典里面存在如下单词
: and
| h*c
发帖数: 1859 | 4 以前房东老太太天天玩这个。
【在 b***u 的大作中提到】
: 听着像g的题
| d********w
发帖数: 363 | 5 呵呵，就是boggle吧
【在 h*c 的大作中提到】
: 以前房东老太太天天玩这个。
| d********w
发帖数: 363 | 6 呵呵，就是boggle吧
【在 h*c 的大作中提到】
: 以前房东老太太天天玩这个。
| h*c
发帖数: 1859 | 7 no. scrabble
【在 d********w 的大作中提到】
: 呵呵，就是boggle吧
| d********w
发帖数: 363 | 8 对的，
真正游戏规则再这
http://www.scrabblepages.com/scrabble/rules/
我敲了半天，唉
【在 h*c 的大作中提到】
: no. scrabble
| z****c
发帖数: 602 | 9 这题面试的时候出只能说说思路，编出来是不可能的。88年Communication of ACM的一
篇paper是讲这个的。
http://www.cs.cmu.edu/afs/cs/academic/class/15451-s06/www/lectu | d********w
发帖数: 363 | 10 赞，是啊，这么难的题让我遇到了。
【在 z****c 的大作中提到】
: 这题面试的时候出只能说说思路，编出来是不可能的。88年Communication of ACM的一
: 篇paper是讲这个的。
: http://www.cs.cmu.edu/afs/cs/academic/class/15451-s06/www/lectu
| w****x
发帖数: 2483 | |
|
