一亩三分地论坛

 找回密码
 获取更多干货,去instant注册!

扫码关注一亩三分地公众号
查看: 3644|回复: 42
收起左侧

facebook onsite

[复制链接] |试试Instant~ |关注本帖
LumiG 发表于 2016-11-2 04:52:38 | 显示全部楼层 |阅读模式

2016(10-12月) 码农类 硕士 全职@Facebook - 内推 - Onsite |Otherfresh grad应届毕业生

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

您需要 登录 才可以下载或查看,没有帐号?获取更多干货,去instant注册!

x
差不多最后一个onsite了吧。

r1 Behaviourial, 然后两个小题目,remove comments in code, 一个dp(每次走2 3 7步,到每个位置有几种走法)
r2 lc 50;69; 一个二维矩阵,求从起点到宝藏的最短路,矩阵里边有障碍物。followup如果可以穿过3个障碍物,求最短路。
r3 2sum + 3sum; meet rooms II; follow up同时输出每个room的会议安排情况


评分

5

查看全部评分

zzgzzm 发表于 2016-11-8 13:53:33 | 显示全部楼层
2ndpoet 发表于 2016-11-8 13:19
鏉ユ簮涓浜.涓夊垎鍦拌鍧. 谢谢LZ的面经分享, 祝好运!
个人觉得R2也可以用DFS解决,思路见代码,欢迎大家讨论!

我觉得code没问题。但因为问的是最短路径,是不是DFS在最差情况下的搜索时间会很长(比如一开始搜索方向就不对)?而且即使第一次到达目的地的时候也不能能最终返回,因为可能不是最短。感觉BFS对于距离有关的会少走一些弯路。
回复 支持 0 反对 1

使用道具 举报

Raymomd 发表于 2016-11-2 04:58:36 | 显示全部楼层
请问lz如果可以穿过三个障碍物怎么答的? 感觉这个好难
回复 支持 反对

使用道具 举报

eko910817 发表于 2016-11-2 07:47:04 | 显示全部楼层
请问楼主remove comments的输入是一个string吗
回复 支持 反对

使用道具 举报

zhaoweigg 发表于 2016-11-2 15:10:53 | 显示全部楼层
本来 bfs,可穿三个障碍物就是dfs?
回复 支持 反对

使用道具 举报

guoyuezhong 发表于 2016-11-2 21:28:41 | 显示全部楼层
楼主第二面的followup如何做?我想可不可以dp f[i][j][k] 表示当前坐标在(i, j) 已经穿过k个障碍物的最短路。
回复 支持 反对

使用道具 举报

zhaoweigg 发表于 2016-11-3 00:22:20 | 显示全部楼层
guoyuezhong 发表于 2016-11-2 21:28. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
楼主第二面的followup如何做?我想可不可以dp f[j][k] 表示当前坐标在(i, j) 已经穿过k个障碍物的最短路。
. 鍥磋鎴戜滑@1point 3 acres
能dp那道是只能向右 或者 向下走的题吧
回复 支持 反对

使用道具 举报

william_gong 发表于 2016-11-3 00:31:39 | 显示全部楼层
同求第二题follow up思路
回复 支持 反对

使用道具 举报

 楼主| LumiG 发表于 2016-11-3 01:02:36 | 显示全部楼层
eko910817 发表于 2016-11-2 07:47
请问楼主remove comments的输入是一个string吗

是string,紫薯紫薯
回复 支持 反对

使用道具 举报

 楼主| LumiG 发表于 2016-11-3 01:05:13 | 显示全部楼层
guoyuezhong 发表于 2016-11-2 21:28
楼主第二面的followup如何做?我想可不可以dp f[j][k] 表示当前坐标在(i, j) 已经穿过k个障碍物的最短路。

差不多就这样,不过这题dp不好更新,所以我还是bfs写的。压队列的时候,加一个“已经穿过几个障碍物”,然后visited数组像你一样改成三维的,其他的和前一问一样。
回复 支持 反对

使用道具 举报

eko910817 发表于 2016-11-3 01:07:35 | 显示全部楼层
LumiG 发表于 2016-11-2 09:02
是string,紫薯紫薯

感谢楼主。祝愿offer多多!
回复 支持 反对

使用道具 举报

 楼主| LumiG 发表于 2016-11-3 01:08:12 | 显示全部楼层
william_gong 发表于 2016-11-3 00:31
同求第二题follow up思路

哎就是用三个值(i, j, o)代表bfs时候的一个状态,然后看四个相邻点相邻点比如(i+1,j),是障碍物就搜(i,j+1,o+1),否则就搜(i,j+1,o)
回复 支持 反对

使用道具 举报

gjxwin 发表于 2016-11-3 01:09:25 | 显示全部楼层
LumiG 发表于 2016-11-3 01:08
哎就是用三个值(i, j, o)代表bfs时候的一个状态,然后看四个相邻点相邻点比如(i+1,j),是障碍物就搜(i,j+ ...

lz这么刚啊?每轮都做3题啊
回复 支持 反对

使用道具 举报

woshigtc 发表于 2016-11-3 01:22:10 | 显示全部楼层
第二题可以3D array做dp?
回复 支持 反对

使用道具 举报

caikkk123 发表于 2016-11-3 03:00:01 | 显示全部楼层
LumiG 发表于 2016-11-3 01:08
哎就是用三个值(i, j, o)代表bfs时候的一个状态,然后看四个相邻点相邻点比如(i+1,j),是障碍物就搜(i,j+ ...

我还是有点疑问,那有的障碍物我也可以选择不穿越啊,比如有很多障碍物,我并不知道穿越哪3个可以得到最短的路径,所以对于每遇到一个障碍物都要走一遍(i,j+1,o+1)和(i,j+1,o)两种情况么?
回复 支持 反对

使用道具 举报

william_gong 发表于 2016-11-3 03:58:50 | 显示全部楼层
caikkk123 发表于 2016-11-3 03:00
我还是有点疑问,那有的障碍物我也可以选择不穿越啊,比如有很多障碍物,我并不知道穿越哪3个可以得到最 ...

如果你不穿那个障碍物,那你那个方向是不能前进的
回复 支持 反对

使用道具 举报

caikkk123 发表于 2016-11-3 04:28:30 | 显示全部楼层
william_gong 发表于 2016-11-3 03:58
如果你不穿那个障碍物,那你那个方向是不能前进的

哦对哦!多谢提点!
回复 支持 反对

使用道具 举报

zhaoweigg 发表于 2016-11-3 04:40:54 | 显示全部楼层
OK, 在3d空间的bfs的感觉, 只不过 obstacle 那个维度只能增加或者不变
回复 支持 反对

使用道具 举报

zzgzzm 发表于 2016-11-3 11:36:03 | 显示全部楼层
LumiG 发表于 2016-11-3 01:08
哎就是用三个值(i, j, o)代表bfs时候的一个状态,然后看四个相邻点相邻点比如(i+1,j),是障碍物就搜(i,j+ ...
. 1point 3acres 璁哄潧
这个允许穿障碍物follow-up,我也是用nCheat[][]记录到每个位置已经用多多少次穿越(i.e., cheats)。但我觉得这个题没有那么简单。就是BFS已经visited过的位置可能还要再visit,因为第二次visit时虽然路径长,但有可能用的穿越次数少,所以之前第一次访问的路径可能跟本到不了终点。也就是说,光用类似于bool visisted[][]是无法判断是否该位置还需要visit。应该是若到达一个已经visit过的位置,因为现在最短路径还没有找到,所以只要当前穿越次数比之前到达该位置时次数用的少就要再visit并update当前距离及穿越次数。
例如:从S走到E,最多允许穿越一次,那么BSF先到达(0,2)时已经用了一次穿越,所以不可能完成路径。但实际上先不穿越绕道到(0,2)再穿过(0,3)就可到达E.
SXOXE
OXOXX.鏈枃鍘熷垱鑷1point3acres璁哄潧
OXOXX
OXOXX. From 1point 3acres bbs
OOOXX
  1. // wall = 1, empty = 0, start = (0,0), end = (m-1,n-1)
  2. int shortestPath(const vector<vector<int>>& a, const int maxCheats = 3) {. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
  3.     int m = a.size(); if (!m) return INT_MAX;
  4.     int n = a[0].size(); if (!n) return INT_MAX;
  5.     // dist[i][j] = distance of (i,j) from start.1point3acres缃
  6.     auto dist = vector<vector<int>>(m, vector<int>(n, INT_MAX)); dist[0][0] = 0;
  7.     // nCht[i][j] = number of cheats used at (i,j)
  8.     auto nCht = vector<vector<int>>(m, vector<int>(n, INT_MAX)); nCht[0][0] = 0;
  9.    
  10.     queue<vector<int>> q; q.push({0, 0}); // start = (0,0)
  11.     vector<vector<int>> dirs = {{1,0},{-1,0},{0,1},{0,-1}};
  12.     // BFS from start = (0,0)
  13.     while (!q.empty()) {
  14.       auto cur = q.front(); q.pop();
  15.       int i = cur[0], j = cur[1], curDist = dist[i][j], curCht = nCht[i][j];
  16.       .鏈枃鍘熷垱鑷1point3acres璁哄潧
  17.       // shortest path found
  18.       if (i == m-1 && j == n-1) return curDist;
  19.       
  20.       // search valid neighbors
  21.       for (auto& dir:dirs) {
  22.         int ii = i + dir[0], jj = j + dir[1];
  23.         if (ii < 0 || ii >= m || jj < 0 || jj >= n) continue;. visit 1point3acres.com for more.
  24.         // number of cheats to use at (ii,jj). visit 1point3acres.com for more.
  25.         int tmpCht = curCht + a[ii][jj]; // use extra cheat for wall. from: 1point3acres.com/bbs
  26.         // cannot enter if out of cheats
  27.         if (tmpCht > maxCheats) continue;.鏈枃鍘熷垱鑷1point3acres璁哄潧
  28.         // haven't visited (ii,jj) or enter with fewer cheats used
  29.         if (tmpCht < nCht[ii][jj]) {
  30.           dist[ii][jj] = curDist + 1;  
  31.           nCht[ii][jj] = tmpCht;
  32.           q.push({ii, jj});   
  33.         }
  34.       }
  35.     }
  36.     return INT_MAX; // cannot reach end=(m-1,n-1)
  37. }
复制代码
回复 支持 反对

使用道具 举报

 楼主| LumiG 发表于 2016-11-3 13:52:06 | 显示全部楼层
zzgzzm 发表于 2016-11-3 11:36
这个允许穿障碍物follow-up,我也是用nCheat[][]记录到每个位置已经用多多少次穿越(i.e., cheats)。但我 ...
.1point3acres缃
对啊,所以我用了个三维的bool数组来记录…这样就行了。
回复 支持 反对

使用道具 举报

treeguard 发表于 2016-11-3 16:26:27 | 显示全部楼层
zzgzzm 发表于 2016-11-3 11:36
这个允许穿障碍物follow-up,我也是用nCheat[][]记录到每个位置已经用多多少次穿越(i.e., cheats)。但我 ...

dist 二维数组是不是可以去掉呢。 因为你在做BFS,  可以每次进入while之前记录下queue的长度, 然后全部遍历完。
回复 支持 反对

使用道具 举报

本版积分规则

请点这里访问我们的新网站:一亩三分地Instant.

Instant搜索更强大,不扣积分,内容组织的更好更整洁!目前仍在beta版本,努力完善中!反馈请点这里

关闭

一亩三分地推荐上一条 /5 下一条

手机版|小黑屋|一亩三分地论坛声明 ( 沪ICP备11015994号 )

custom counter

GMT+8, 2016-12-8 14:06

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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