📣 4th of July限时特惠: VIP通行证立减$68
回复: 30
跳转到指定楼层
上一主题 下一主题
收起左侧

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

全局:

2017(1-3月) 码农类General 博士 全职@meta - 校园招聘会 - 技术电面 Onsite  | | Other | 应届毕业生

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看附件。没有帐号?注册账号

x
希望有大神可以一起讨论一下这几个题:
Question1:
这个稍微难, 说有一堆task,每个有不同时间完成, 然后有一堆worker, 说如何分配 task to worker,完成时间最短, task是独立的。.看起来像背包, DP
task:  2,2,3,7, 1
worker: 2
您好!
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式
游客,您好!
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies
上过一个算法课,大概思路就是做一个二维的meeting room II。 扫描线算法。

谢谢大神们


上一篇:2017.2.18 PocketGems OA 题没变
下一篇:收到了亚麻 intern电面通知

本帖被以下淘专辑推荐:

推荐
zzgzzm 2017-8-5 01:42:32 | 只看该作者
全局:
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. int maxOverlap1D(vector<Rect>& rects, int x) {
  5.   map<int, int> count;
  6.   for (auto& r : rects) {
  7.     if (x < r.x1 || x > r.x2) continue;
  8.     count[r.y1]++, count[r.y2 + 1]--;
  9.   }

  10.   int res = 0, total = 0;
  11.   for (auto& p : count)
  12.     res = max(res, total += p.second);
  13.   return res;
  14. }

  15. int maxOverlap2D(vector<Rect>& rects) {
  16.   int res = 0;
  17.   for (auto& r : rects)
  18.     res = max(res, maxOverlap1D(rects, r.x1));
  19.   return res;
  20. }
复制代码
回复

使用道具 举报

推荐
xiaobai123 2017-4-24 16:01:53 | 只看该作者
全局:
大神,可以用greedy吗?task从高到低排个序,然后用一个min heap, 每次把work load最小的worker弹出来,把当前最大的task分配给他。

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

使用道具 举报

全局:
say543 发表于 2017-3-30 14:31
看不太懂 你怎么用一维限制只找三个.....

一维数组实现二维DP嘛,本来二维表就是一行一行挨个写下来的

这个二维表的行是假设有nn个subarray, nn就是  行index+1

DP(nn, i) = Max(DP(nn-1, i-k)+sum(i-k, i), DP(nn, i-1))
这个是状态转移方程, DP是有subarray的个数下,从0到i的最大值。sum(i-k, i)是元素从i-k到i的累加和
状态转移方程的体现在第13行

这个代码是测试过的,应该没大问题,我发之前应该写注释的

补充内容 (2017-3-30 15:43):
DP是有subarray的个数下
=>DP是有nn个subarray的个数下
回复

使用道具 举报

🔗
say543 2017-2-19 14:30:05 | 只看该作者
全局:
第二题因该就是dp[k][n] k =3, n 是以n为结尾of 最后一个seq 加上前面两个seq 的总和 求越大越好 o(n) 没问题

补充内容 (2017-2-19 14:35):

错了这样好像是o(nk) 楼主怎做到o(n)的?
回复

使用道具 举报

🔗
say543 2017-2-19 14:40:22 | 只看该作者
全局:
第一轮 只会dfs 暴力解 楼主怎转成背包问题?
回复

使用道具 举报

🔗
say543 2017-2-19 14:41:25 | 只看该作者
全局:
第三轮 我有在某家面经看过 但是是圆形 但是一职没想出怎么用线段扫描法 楼主能说说吗?
回复

使用道具 举报

全局:
Question 1 我有点思路。看下有道理没
就是如果我限制三个worder的task上限,那么就变成了一个多背包问题。
多背包问题可以用背包问题再多一维解出来。

这里找了一篇神文,求解多背包的
http://www.or.deis.unibo.it/kp/Chapter6.pdf

然后不断提升这个上限,直到刚刚好装满所有task。
(也可以二分搜索法)
这个上限就是最短时间。
回复

使用道具 举报

🔗
say543 2017-2-27 14:58:32 | 只看该作者
全局:
翻滚吧豆子 发表于 2017-2-27 13:45
Question 1 我有点思路。看下有道理没
就是如果我限制三个worder的task上限,那么就变成了一个多背包问题 ...


BST 上限是可行的 但是问题在于 DP 的worker 是不定的 这要怎么dp呢? 感觉跟多重背包不大依样?
回复

使用道具 举报

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

如果是M个subarray(M = 3在此题), 那么用DP的话能实现O(MN)的,N是Array总长度。
回复

使用道具 举报

全局:
shevchenko777 发表于 2017-3-30 06:46
如果是M个subarray(M = 3在此题), 那么用DP的话能实现O(MN)的,N是Array总长度。

是的,这道题和股票IV很像
  1.   public static int findNWindow(int[] nums, int k, int n){
  2.     int[] lastMaxK = new int[nums.length];
  3.     int[] maxK = new int[nums.length];
  4.    
  5.     for(int nn=0; nn<n; nn++){
  6.       int curSum=0;
  7.       for(int i=nn*k; i<nums.length; i++){
  8.         curSum += nums[i];

  9.         if(i==(nn+1)*k-1) maxK[i] = curSum;
  10.         if(i>=(nn+1)*k){
  11.           curSum -= nums[i-k];
  12.           maxK[i] = Math.max(lastMaxK[i-k] + curSum, maxK[i-1]);
  13.         }
  14.       }
  15.       int[] t = lastMaxK;
  16.       lastMaxK = maxK;
  17.       maxK = t;
  18.     }
  19.    
  20.     return lastMaxK[maxK.length-1];
  21.   }
复制代码
回复

使用道具 举报

🔗
ferrishu 2017-3-30 08:05:52 | 只看该作者
本楼:
全局:
关注一下
回复

使用道具 举报

🔗
say543 2017-3-30 14:31:58 | 只看该作者
全局:
翻滚吧豆子 发表于 2017-3-30 07:48
是的,这道题和股票IV很像

看不太懂 你怎么用一维限制只找三个.....
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 注册账号
隐私提醒:
  • ☑ 禁止发布广告,拉群,贴个人联系方式:找人请去🔗同学同事飞友,拉群请去🔗拉群结伴,广告请去🔗跳蚤市场,和 🔗租房广告|找室友
  • ☑ 论坛内容在发帖 30 分钟内可以编辑,过后则不能删帖。为防止被骚扰甚至人肉,不要公开留微信等联系方式,如有需求请以论坛私信方式发送。
  • ☑ 干货版块可免费使用 🔗超级匿名:面经(美国面经、中国面经、数科面经、PM面经),抖包袱(美国、中国)和录取汇报、定位选校版
  • ☑ 查阅全站 🔗各种匿名方法

本版积分规则

>
快速回复 返回顶部 返回列表