问一道FB面试题

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

发信人: frederickyl (frederickyl), 信区: JobHunting
标  题: 问一道FB面试题
发信站: BBS 未名空间站 (Sat Aug 29 19:22:00 2015, 美东)

我们的手机，几乎每个键都对应字母： key2 -> 'abc', key3 -> 'def', key4 -> '
ghi'....老式的手机打字的原理是，如果你要打出a，你需要按1下key2. 如果要打出b
，你需要按2下key2， 打出c就要按3下key2，因为c排在key2的第三位。

所以题目是给出，keySize[] 每个element代表能存放的最多character， 比如上面的
例子就是[3,3,3],因为每个key都能最多放3个字母； 还有frequency[]，每个element
代表每个character出现的频率。要求把character排入key中，通过上面的方法打出所
有frequency数组中的character，最少的按键次数。

下面给个例子，比如我们的keysize是 [3,1,2]，我们的character的frequency是 [3，
3, 3， 2,1,1]。 如果把frequency中头三个字母index0 - index2放入key1， index3
放入key2，index4-index5放入key3，这样的按键次数就是 3*1 + 3*2 + 3*3 + 2*1 +
1*1 + 1*2。character可以打乱随意放，只要不超过keySize的limit。

follow up的要求就是character必须要找 frequency的order来，index2必能放在
index1之前。