问个Facebook的面经题

http://www.mitbbs.com//article_t/JobHunting/33055253.html

发信人: goldsky (MC), 信区: JobHunting
标  题: 问个Facebook的面经题
发信站: BBS 未名空间站 (Thu Sep 17 17:06:35 2015, 美东)

3. 一种字母游戏这样的
给定四个位置 _,_,_,_
然后每个位置可以选5个candidates，然后问这些candidates最多可以组成多少个有效
的词，字典是给定的。

比如，
如果字典是 [cake, bike, fake]
我们可以这样选candidates
第一个位置可以选 b,c,f,e,d
第二个位置 i,a,o,p,e
第三个位置 k,m,w,q,a
第四个位置 e,g,h,k,l
那这些可以组成3个有效的词 cake, bike, fake.

但是如果，这样选每个位置的candidates
第一个位置可以选 z,c,v,b,y
第二个位置 i,a,o,p,e
第三个位置 k,m,w,q,a
第四个位置 e,g,h,k,l

只能组成一个有效的词就是bike.
这样就是第一种选candidates的方法比较好。

然后问你怎么选每个位置的candidates，最终可以让能组成的词最多。

没有什么特别好的思路，问是不是brutal search，还有更好的方法吗？答：你如果要
brutal search的话，你估算一下时间。
我就开始算时间，发现很长，然后面试官说，那你想办法优化。。。但是因为算brual
search的时间算了太长时间了，就没什么时间优化了。。。
--