求大神讨论Facebook 面经经典难题

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

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

大神，可以用greedy吗？task从高到低排个序，然后用一个min heap, 每次把work load最小的worker弹出来，把当前最大的task分配给他。

补充内容 (2017-4-24 16:02):
我是说第一题

第一题，有两个worker的情况实际上是在求最接近总量／2的subset，在workload有限的情况下是背包。worker>2硬说是dp也可以，复杂度就变成 workload^#workers了。还是dfs吧。
第二题dp，O(n)
第三题扫描线没毛病

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

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

翻滚吧豆子 发表于 2017-4-25 00:05
我后来做了研究，基本确定了第一题属于NP HARD  叫多背包问题，就像你说的那样。
面试官问的时候就是在 ...

楼主大神，能展开说一下，或者给个link？

xiaobai123 发表于 2017-4-25 02:37
楼主大神，能展开说一下，或者给个link？

http://www.or.deis.unibo.it/kp/Chapter6.pdf
这里

翻滚吧豆子 发表于 2017-3-30 07:48
是的，这道题和股票IV很像

有个小bug，当length=n*k的时候，并没有update lastmax。
我稍改了一下，不过是C++

1. int findNWindow(vector<int>& nums, int K, int n){
   
2.         int m = nums.size();
   
3.     vector<int> lastMaxK(m,0);
   
4.     vector<int> maxK(m,0);
   
5. 
   
6.     for(int i=0; i<n; i++){
   
7.             int curSum=0;
   
8.             for(int j=i*K; j<m; j++){
   
9.                     curSum += nums[j];
   
10. 
    
11.                     if (j<(i+1)*K-1) continue;
    
12.                     if (j>=(i+1)*K) curSum -= nums[j-K];
    
13. 
    
14.                     if (j==K-1) maxK[j] = curSum;
    
15.                     else maxK[j] = max(lastMaxK[j-K] + curSum, maxK[j-1]);
    
16.             }
    
17.             swap(maxK, lastMaxK);
    
18.     }
    
19.     return lastMaxK[m-1];
    
20. }

复制代码

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

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

xiaobai123 发表于 2017-4-24 16:01
大神，可以用greedy吗？task从高到低排个序，然后用一个min heap, 每次把work load最小的worker弹出来，把 ...

返例：2， 2， 2， 2， 2， 3， 7， worker：2
不知到这么久了有合适的解了么？

关注一下