FB滚烫电面面经， 求大米

上来一个印度小哥，简单2分钟的寒暄就上题了
说有一串数组代表文件大小（A）， 还有一串数组代表这些文件被压缩后的大小（B）， 其中A和B的元素数目相同。 还有一个数组S，代表想最终处理后所有文件的大小，包括有些文件

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

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

ong>补充内容 (2019-6-28 23:33):
昨天刚刚被告知要加面电面，看来挂得还不够彻底。。。

f(i)(s) = min | f(i-1)(s-b[i-1])+1, f(i-1)(s-a[i-1]) |

一进来头像吓我一跳

个人感觉按照压缩的差排序再贪心得到等于S和不大于S的结果个数是一样的，只不过最后一个要压缩的文件不压缩那么多而已，贪心算法应该还是可行的

LZ实在没想出来DP的解法，就用递归做的。。。如果哪位大神指导解法请不吝赐教。

所以最后目标是，压缩完以后的大小‘等于’S？ 还是可以‘不大于’S?

xcz52416 发表于 2019-6-25 02:37
所以最后目标是，压缩完以后的大小‘等于’S？ 还是可以‘不大于’S?

最后的目标是不大于S

wangbd 发表于 2019-6-25 02:54
最后的目标是不大于S

不大于的话岂不是之间算完两个数组之间的差，然后从大到小排序求和就完事了？

ljhgod 发表于 2019-6-25 03:04
不大于的话岂不是之间算完两个数组之间的差，然后从大到小排序求和就完事了？

这个是我最后给出的答案，贪心算法。但是我没有时间求证这个算法是否正确了。不知道是不是在所有的情况下面都能行。

我会用max heap来做，其中的元素是A与B的差。步骤如下：1）算出A中所有元素的加和cur_sum；2）while 循环判断cur_sum是否大于S，若是，则从最大堆中取出最大值m，cur_sum-=m

myhong 发表于 2019-6-25 03:14
我会用max heap来做，其中的元素是A与B的差。步骤如下：1）算出A中所有元素的加和cur_sum；2）while 循环判 ...

这个跟我最终给的答案差不多，都是O（n log n）的时间复杂度。DP的话是N^2

ljhgod 发表于 2019-6-25 03:04
不大于的话岂不是之间算完两个数组之间的差，然后从大到小排序求和就完事了？

嗯，我也是这么想的。总觉得不大于的情况有点过于简单。。。等于的话我还没想明白