Berkeley biostat应该是biostat里最非传统,最偏ml的超棒项目了!

一亩三分地论坛

 找回密码
 Sign Up 注册获取更多干货

最近看过此主题的会员

坐标湾区
DreamCraft创始团队
招聘游戏开发工程师
游戏初创公司招聘工程师、UIUX Designer和游戏策划
码农求职神器Triplebyte:
不用海投
内推多家公司面试
前Google华人高管创立
面试offer一键直通
Leap.ai助你进入热门独角兽
查看: 10361|回复: 46
收起左侧

facebook onsite

[复制链接] |试试Instant~
我的人缘0
LumiG 发表于 2016-11-2 04:52:38 | 显示全部楼层 |阅读模式
本楼: 【顶】   100% (1)
 
 
0% (0)   【踩】
全局: 顶  97% (85)
 
 
2% (2)  踩

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

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

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

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大米 +97 收起 理由
coldknight + 1 感谢分享!
whdawn + 40
bych0223 + 3 感谢分享!
cr025 + 3 感谢分享!
candy_shmily + 50

查看全部评分


上一篇:小光棍节GG面(gui?)经NY
下一篇:Airbnb Phone Interview 11/1

本帖被以下淘专辑推荐:

我的人缘0
zzgzzm 发表于 2016-11-8 13:53:33 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
100% (1)   【踩】
全局: 顶  98% (63)
 
 
1% (1)  踩
2ndpoet 发表于 2016-11-8 13:19
谢谢LZ的面经分享, 祝好运!
个人觉得R2也可以用DFS解决,思路见代码,欢迎大家讨论!

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

使用道具 举报

我的人缘0
Raymomd 发表于 2016-11-2 04:58:36 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  86% (19)
 
 
13% (3)  踩
请问lz如果可以穿过三个障碍物怎么答的? 感觉这个好难
回复

使用道具 举报

我的人缘0
eko910817 发表于 2016-11-2 07:47:04 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  92% (72)
 
 
7% (6)  踩
请问楼主remove comments的输入是一个string吗
回复

使用道具 举报

我的人缘0
zhaoweigg 发表于 2016-11-2 15:10:53 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  85% (6)
 
 
14% (1)  踩
本来 bfs,可穿三个障碍物就是dfs?

21.000+ students read the Road to learn React. The course weaves all the opinionated roadmaps into one roadmap to master React. It gives you all the fundamentals in React. You will build a Hacker News App along the way.

回复

使用道具 举报

我的人缘0
guoyuezhong 发表于 2016-11-2 21:28:41 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  100% (1)
 
 
0% (0)  踩
楼主第二面的followup如何做?我想可不可以dp f[i][j][k] 表示当前坐标在(i, j) 已经穿过k个障碍物的最短路。
回复

使用道具 举报

我的人缘0
zhaoweigg 发表于 2016-11-3 00:22:20 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  85% (6)
 
 
14% (1)  踩
guoyuezhong 发表于 2016-11-2 21:28
楼主第二面的followup如何做?我想可不可以dp f[j][k] 表示当前坐标在(i, j) 已经穿过k个障碍物的最短路。

能dp那道是只能向右 或者 向下走的题吧
回复

使用道具 举报

我的人缘0
william_gong 发表于 2016-11-3 00:31:39 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  91% (104)
 
 
8% (10)  踩
同求第二题follow up思路
回复

使用道具 举报

我的人缘0
 楼主| LumiG 发表于 2016-11-3 01:02:36 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  97% (85)
 
 
2% (2)  踩
eko910817 发表于 2016-11-2 07:47
请问楼主remove comments的输入是一个string吗

是string,紫薯紫薯
回复

使用道具 举报

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

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

使用道具 举报

我的人缘0
eko910817 发表于 2016-11-3 01:07:35 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  92% (72)
 
 
7% (6)  踩
LumiG 发表于 2016-11-2 09:02
是string,紫薯紫薯

感谢楼主。祝愿offer多多!

Learn React.js, Redux & Immutable.js while building a weather app

回复

使用道具 举报

我的人缘0
 楼主| LumiG 发表于 2016-11-3 01:08:12 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  97% (85)
 
 
2% (2)  踩
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)
回复

使用道具 举报

我的人缘0
gjxwin 发表于 2016-11-3 01:09:25 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  93% (476)
 
 
6% (35)  踩
LumiG 发表于 2016-11-3 01:08
哎就是用三个值(i, j, o)代表bfs时候的一个状态,然后看四个相邻点相邻点比如(i+1,j),是障碍物就搜(i,j+ ...
. 牛人云集,一亩三分地
lz这么刚啊?每轮都做3题啊
回复

使用道具 举报

我的人缘0
woshigtc 发表于 2016-11-3 01:22:10 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  91% (68)
 
 
8% (6)  踩
第二题可以3D array做dp?
回复

使用道具 举报

我的人缘0
caikkk123 发表于 2016-11-3 03:00:01 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  100% (2)
 
 
0% (0)  踩
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)两种情况么?
回复

使用道具 举报

我的人缘0
william_gong 发表于 2016-11-3 03:58:50 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  91% (104)
 
 
8% (10)  踩
caikkk123 发表于 2016-11-3 03:00
我还是有点疑问,那有的障碍物我也可以选择不穿越啊,比如有很多障碍物,我并不知道穿越哪3个可以得到最 ...
. 一亩-三分-地,独家发布
如果你不穿那个障碍物,那你那个方向是不能前进的
回复

使用道具 举报

我的人缘0
caikkk123 发表于 2016-11-3 04:28:30 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  100% (2)
 
 
0% (0)  踩
william_gong 发表于 2016-11-3 03:58
如果你不穿那个障碍物,那你那个方向是不能前进的

哦对哦!多谢提点!
回复

使用道具 举报

我的人缘0
zhaoweigg 发表于 2016-11-3 04:40:54 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  85% (6)
 
 
14% (1)  踩
OK, 在3d空间的bfs的感觉, 只不过 obstacle 那个维度只能增加或者不变
回复

使用道具 举报

我的人缘0
zzgzzm 发表于 2016-11-3 11:36:03 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  98% (63)
 
 
1% (1)  踩
LumiG 发表于 2016-11-3 01:08
哎就是用三个值(i, j, o)代表bfs时候的一个状态,然后看四个相邻点相邻点比如(i+1,j),是障碍物就搜(i,j+ ...
. from: 1point3acres
这个允许穿障碍物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
OXOXX
OXOXX
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
  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.       
  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];. From 1point 3acres bbs
  23.         if (ii < 0 || ii >= m || jj < 0 || jj >= n) continue;
  24.         // number of cheats to use at (ii,jj)
  25.         int tmpCht = curCht + a[ii][jj]; // use extra cheat for wall
  26.         // cannot enter if out of cheats
  27.         if (tmpCht > maxCheats) continue;
    -google 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. }
复制代码
回复

使用道具 举报

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

使用道具 举报

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

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

使用道具 举报

游客
请先登录

本版积分规则

提醒:发帖可以选择内容隐藏,部分板块支持匿名发帖。请认真读完以下全部说明:

■隐藏内容方法: [hide=200]你想要隐藏的内容比如面经[/hide]
■意思是:用户积分低于200则看不到被隐藏的内容
■可以自行设置积分值,不建议太高(200以上太多人看不到),也不建议太低(那就没必要隐藏了)
■建议只隐藏关键内容,比如具体的面试题目、涉及隐私的信息,大部分内容没必要隐藏。
■微信/QQ/电子邮件等,为防止将来被骚扰甚至人肉,以论坛私信方式发给对方最安全。
■匿名发帖的板块和方法:http://www.1point3acres.com/bbs/thread-405991-1-1.html

手机版|小黑屋|一亩三分地论坛声明

GMT+8, 2018-9-26 22:14

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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