Facebook onsite面经

朋友帮忙推荐给recruiter的，两轮电面之后拿到onsite。
第一轮： 老印，上来一道题，讲了半天我才弄明白。类似手机按键，比如手机按键上2对应‘abc’, 然后根据‘abc’的顺序，打出a要按一下键，b要按两下键，c要按三下键。给你两个数组: keySize[] 每个element代表能存放的最多character，frequency[]每个element代表每个character出现的频率。要算出最少的按键次数。 Follow up 1: 怎么能提高效率。 Foll

您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

不大好说。

例子就是我们的手机，几乎每个键都对应字母： key2 -> 'abc', key3 -> 'def', key4 -> 'ghi'....老式的手机打字的原理是，如果你要打出a，你需要按1下key2....

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

第一题的followup确实是dp，但是我觉得你这个链接写的不是很清楚，其实只需要N^2的空间和N^3的时间。

需要引入一个辅助数组Status[I][J], 其存储的是，从第I个键开始后面J个连续存放在相同键盘上时对结果的贡献，需要N^2时间获得这个数组。

有了这个数组，再引入一个数组Result[L][K], 存储的就是前L个字符结束于K个键对应的结果。很明显：
Result[L][K] = min_U (Result[L][K], Result[U][K-1] + Status[U+1][L-U])

时间开销是N^3，但是空间开销是2*N^2，你给的链接是三维数组dp，逻辑很容易混淆。

其实这题有点像lintcode copy books.

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

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

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

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

希望大家能看明白。

第二题： sort an array contains only 3 element，类似leetcode的sort colors。 follow up: what if there are N element? 没想出来， hint是可以使用extra memery  <----这个就变成counting sort了吧. 如果n是constant

第一轮是不是可以用Trie？ keysize就是每一个节点有多少字母。

楼主，能够针对第一题举个例子吗？

楼主说说第一题。

```给你两个数组: keySize[] 每个element代表能存放的最多character，frequency[]每个element代表每个character出现的频率。```
能够针对第一题举个例子吗？能说的再详细点吗？

第二轮第一题 cut branch什么意思？

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

莫非是pruning，剪枝？

sort color 那题应该是counting sort如果element 为n的话

第一道是不是这样的。

有N个key，第i个key可以容纳keysize[i]多个character。对于每个key，key size[i]个character必须是依次排列。比如key是1，容纳3个character，a,b,c。你可以排成cab, bac, ....

再给你frequency数组大小M，问你如何把M个character排列到N个key上去，使得总的按character的期望频率最小吧。。。。