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

daguanyuan 发表于 2017-6-30 06:16
返例：2， 2， 2， 2， 2， 3， 7， worker：2
不知到这么久了有合适的解了么？

看leetcode 410. 应该是一样的

关注一下，也在准备昂赛

扫描线算法 怎么算这个矩形重合？
那位大牛能简单说下？
我还看见有题是算多个圆重合，答案是先看包含圆的矩形是否重合（用扫描线），然后确认里面圆形是否重合

scredwood 发表于 2017-7-1 03:47
看leetcode 410. 应该是一样的

好像不一样。LC上要求是连续的，这里要求是不连续的。

daguanyuan 发表于 2017-7-1 06:30
好像不一样。LC上要求是连续的，这里要求是不连续的。

我觉得还是可以。 比如你的例子
2，2，2，2，2，3，7
二分出来了以后，是10
正好分两组。我再想想有没有反例

补充内容 (2017-7-1 09:38):
我的意思是排序下，再算。但是隐隐感觉还是不太对。

say543 发表于 2017-2-19 14:30
第二题因该就是dp[k][n] k =3, n 是以n为结尾of 最后一个seq 加上前面两个seq 的总和 求越大越好 o(n) 没问 ...

Note that the k-sum always refers to k consecutive values, so do not dp on k. Once you compute the k-sum for first k value, just +a[k]-a[i-k] to compute the next sliding window's sum.

Q2, Prob 2: I don't think it is typical DP. It seems to just update max sum while sliding the window. Using more space in exchange of time.

1. int max3KSum(vector<int>& a, int k) {
   
2.         int n = a.size();
   
3.         vector<int> L2RMaxKSum(n - k + 1), R2LMaxKSum(n - k + 1), sum(n- k + 1);
   
4. 
   
5.         L2RMaxKSum[0] = sum[0] = accumulate(a.begin(), a.begin() + k, 0);
   
6.         for (int i = 1; i <= n - k; ++i)
   
7.                 L2RMaxKSum[i] = max(L2RMaxKSum[i - 1], sum[i] += (a[i + k - 1] - a[i - 1]));
   
8. 
   
9.         R2LMaxKSum[n - k] = sum[n - k];
   
10.         for (int i = n-k-1; i >= 0; --i)
    
11.                 R2LMaxKSum[i] = max(R2LMaxKSum[i + 1], sum[i]);
    
12. 
    
13.         int res = 0;
    
14.         for (int i = k; i + 2 * k < n; ++i)
    
15.                 res = max(res, sum[i] + L2RMaxKSum[i - k] + R2LMaxKSum[i + k]);
    
16.         return res;
    
17. }

复制代码

Question 3: If this is treated as 2D meeting room II problem, I am thinking for any fix x, solve a 1-D Meeting Room II. For each 1-D problem, because I need to filter out those rectangles which don't intersect x, I can only do O(N*logN) for each 1-D problem. Total O(N^2*logN). Anyone has O(N^2) solution?

1. struct Rect {
   
2.   int x1, x2, y1, y2;
   
3. };
   
4. 
   
5. int maxOverlap1D(vector<Rect>& rects, int x) {
   
6.   map<int, int> count;
   
7.   for (auto& r : rects) {
   
8.     if (x < r.x1 || x > r.x2) continue;
   
9.     count[r.y1]++, count[r.y2 + 1]--;
   
10.   }
    
11. 
    
12.   int res = 0, total = 0;
    
13.   for (auto& p : count)
    
14.     res = max(res, total += p.second);
    
15.   return res;
    
16. }
    
17. 
    
18. int maxOverlap2D(vector<Rect>& rects) {
    
19.   int res = 0;
    
20.   for (auto& r : rects)
    
21.     res = max(res, maxOverlap1D(rects, r.x1));
    
22.   return res;
    
23. }
    

复制代码

第一题就是基于背包的贪心吧，相当于有worker个背包，每次尽可能装满，去掉那些用过的元素，然后在装下一个包，所以复杂度基本是O((worker-1)*(sum(tasks)/worker*len(tasks)))