Facebook onsite面经

好吧，可能是我表达不好，第一题不画个图真不大好说。

例子就是我们的手机，几乎每个键都对应字母： 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可以daluan随意放，只要不超过keySize的limit。

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

希望大家能看明白。

xnature 发表于 2015-7-28 03:23
第一道是不是这样的。

有N个key，第i个key可以容纳keysize多个character。对于每个key，key size个chara ...

对，基本就是这个意思，比如你其中一个key容纳‘abc’，那你打出a要按1次键，打出b要按2次，c要按3次。
让后给你所有character需要打出的次数，求最少的按键次数

beyond 发表于 2015-7-27 23:22
第二轮第一题 cut branch什么意思？

就是简化code，把不必要的case去掉

Followup 2应该是动态规划。  
http://www.acmerblog.com/POJ-1404-I-Keyboard-blog-387.html

http://poj.org/problem?id=1404

另外，欢迎找我内推Google. 여러분..

第二轮，可以用extra memory的话，那就太简单了啊。。。。。。

mc422 发表于 2015-7-28 05:17
好吧，可能是我表达不好，第一题不画个图真不大好说。

例子就是我们的手机，几乎每个键都对应字母： key ...

follow up的要求就是character必须要找 frequency的order来，index2必能放在index1之前。
楼主，这句话，说白了就是必须按照字母表顺序来呗？是这样的嘛？谢谢

lz onsite 只有三轮呀？

Linzertorte 发表于 2015-7-28 05:52
Followup 2应该是动态规划。  
http://www.acmerblog.com/POJ-1404-I-Keyboard-blog-387.html

我还以为greedy就够了。。。。囧

mc422 发表于 2015-7-28 05:19
对，基本就是这个意思，比如你其中一个key容纳‘abc’，那你打出a要按1次键，打出b要按2次，c要按3次。
...

请问楼主，character可不可跳着放？比如，
Key1： AC
Key2:   B
这样对于每个key上的character来说，order是没有被打乱的，不过不是完全连续的排列。