Facebook onsite面经

键盘那题的followup也太难了吧 .. = =

key1(3), key2(1), key3(2), ABCDEF的frequencey: [3,3,3,2,1,1]， 结果是：ADF->key1, B->key2, CE->key3

follow up确实很难。如果不看followup的话，即character没有顺序，可以随便排的话，那就按照frequency排序，然后把frequency高的character放到key的低位，一位一位往下面放就可以了

第二题用extra memory就是counting sort吧，两次遍历数组

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.

returning 发表于 2016-3-27 01:08
第一题的followup确实是dp，但是我觉得你这个链接写的不是很清楚，其实只需要N^2的空间和N^3的时间。

...

这种解法应该就是面试官想要的解法，不过面试时遇到这题，就算知道是dp，思路明晰，需要考虑的边界条件还是特别多，只能说楼主特别倒霉。。。。