问一道FB面试题

原帖地址:mitbbs

我们的手机,几乎每个键都对应字母: 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之前。