问一道FB面试题 - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>JobHunting - 待字闺中

问一道FB面试题

问一道FB面试题# JobHunting - 待字闺中

f*l2015-08-29 07:08

1 楼

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

s*c2015-08-29 07:08

2 楼

Huffman code

b
element
index3
+

【在 f*********l 的大作中提到】

: 我们的手机，几乎每个键都对应字母： 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 +

w*e2015-08-29 07:08

3 楼

贴一段代码，求大牛鉴定，先sort frequency，然后greedy
public int minKeyClicks(int[] keySize, int[] frequency){
int totalSize = 0;
for(int size : keySize)
totalSize += size;
if(frequency.length > totalSize){
return -1; //Illegal input
}
int totalClick = 0;
int i = frequency.length -1;
Arrays.sort(frequency);
int level = 1; //consume first click with max frequency
while( i >= 0){
int k = 0;
while(k < keySize.length){
if(keySize[k] > 0 && i >= 0){
totalClick += frequency[i] * level;
keySize[k]--;
i--;
}
k++;
}
level++;
}
return totalClick;
}

e*32015-08-29 07:08

4 楼

2个堆.keysize用最小堆heap_min,freq用最大堆heap_max.每次从heap_min取出一个数x
,然后在heap_max取出x个数

d*e2015-08-29 07:08

5 楼

你这个不对。首先frequncy应该可以远小于key size.
其次，level成了global的。
这题的关键是建立模型。
假设fre sort好了。
那么每个key,第一个位置 click是1. 第二位置click 是2. 第三个位置click是3......
那么假设key 变成一个list, 那么你现在有n个list,要最优化，需要按照fre，弹出最
小click对应的key/order.
这样你需要一个min queue of n key streams的iterator.
这样实际上回答了第二个扩展问题。
对于第一个，可以简化，从左到右loop keysize就可以。没用一个就keysize +1。用完
的就swap to end, n--.

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

: 贴一段代码，求大牛鉴定，先sort frequency，然后greedy
: public int minKeyClicks(int[] keySize, int[] frequency){
: int totalSize = 0;
: for(int size : keySize)
: totalSize += size;
: if(frequency.length > totalSize){
: return -1; //Illegal input
: }
: int totalClick = 0;
: int i = frequency.length -1;

r*g2015-08-29 07:08

6 楼

看不懂题，留个名

g*u2015-08-29 07:08

7 楼

请问第二问是什么意思？谁能解释一下？

b
element
index3
+

【在 f*********l 的大作中提到】

m*t2015-08-29 07:08

8 楼

看不懂这个follow up。难道character不可以改变顺序？这样不就是把freq加起来？

m*t2015-08-29 07:08

9 楼

第一问也不明白。假设有n个key, 我们只要把freq排序，然后前n个freq就放在n个key
的第一位，等等。。。
似乎太简单了吧？
还是我理解错了？

c*t2015-08-29 07:08

10 楼

楼主题没有说清楚。突然出现一个“index2”, "index1", 总得在前文中出现过吧。
我靠猜测，替楼主把follow up题目补全：
在此问中，frequency 数组中，出现频率小的字母，在键盘上，必须排在出现频率高的
字母之后（或者同一按键）。
比如， [3 3 3 2 1 1 ], 前三个字母频率相同，次序可以任意排列，但第四个字母出
现频率为2，必须出现在键盘上靠后的位置。如果频率为[3 2 2 2 1 1],因为键盘为[3
1 2], 这种情况下，频率为3的字母可以和频率为2的字母处于同一按键。

b
element
index3
+

【在 f*********l 的大作中提到】