[八我司] Expedia一年半遊:这是一個特別適合養老待退的地方

一亩三分地论坛

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

最近看过此主题的会员

H1B/绿卡遥遥无期
又不想回国
来东南亚最大的互联网集团工作?
码农求职神器Triplebyte:
不用海投
内推多家公司面试
坐标湾区
Games Startup
招聘游戏开发工程师
游戏初创公司招聘工程师、UIUX Designer和游戏策划
查看: 10184|回复: 46
收起左侧

facebook onsite

[复制链接] |试试Instant~ |关注本帖
我的人缘0
LumiG 发表于 2016-11-2 04:52:38 | 显示全部楼层 |阅读模式
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】

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的会议安排情况

. visit 1point3acres for more.

评分

参与人数 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 | 显示全部楼层
  此人我要顶:
 
100% (1) 【我投】
  此人我要踩:
 
0% (0) 【我投】
2ndpoet 发表于 2016-11-8 13:19
谢谢LZ的面经分享, 祝好运!. 围观我们@1point 3 acres
个人觉得R2也可以用DFS解决,思路见代码,欢迎大家讨论!

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

使用道具 举报

我的人缘0
Raymomd 发表于 2016-11-2 04:58:36 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
请问lz如果可以穿过三个障碍物怎么答的? 感觉这个好难
回复 支持 反对

使用道具 举报

我的人缘0
eko910817 发表于 2016-11-2 07:47:04 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
请问楼主remove comments的输入是一个string吗
回复 支持 反对

使用道具 举报

我的人缘0
zhaoweigg 发表于 2016-11-2 15:10:53 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
本来 bfs,可穿三个障碍物就是dfs?
回复 支持 反对

使用道具 举报

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

使用道具 举报

我的人缘0
zhaoweigg 发表于 2016-11-3 00:22:20 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
guoyuezhong 发表于 2016-11-2 21:28.本文原创自1point3acres论坛
楼主第二面的followup如何做?我想可不可以dp f[j][k] 表示当前坐标在(i, j) 已经穿过k个障碍物的最短路。

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

使用道具 举报

我的人缘0
william_gong 发表于 2016-11-3 00:31:39 | 显示全部楼层
  此人我要顶:
 
0% (0) 【我投】
  此人我要踩:
 
100% (1) 【我投】
同求第二题follow up思路
Mobile Apps Category (English)728x90
回复 支持 反对

使用道具 举报

我的人缘0
 楼主| LumiG 发表于 2016-11-3 01:02:36 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
eko910817 发表于 2016-11-2 07:47. Waral 博客有更多文章,
请问楼主remove comments的输入是一个string吗

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

使用道具 举报

我的人缘0
 楼主| LumiG 发表于 2016-11-3 01:05:13 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
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% (暂未有人投票) 【我投】
LumiG 发表于 2016-11-2 09:02
是string,紫薯紫薯

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

使用道具 举报

我的人缘0
 楼主| LumiG 发表于 2016-11-3 01:08:12 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
william_gong 发表于 2016-11-3 00:31.1point3acres网
同求第二题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 | 显示全部楼层
  此人我要顶:
 
100% (1) 【我投】
  此人我要踩:
 
0% (0) 【我投】
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% (暂未有人投票) 【我投】
第二题可以3D array做dp?
回复 支持 反对

使用道具 举报

我的人缘0
caikkk123 发表于 2016-11-3 03:00:01 | 显示全部楼层
  此人我要顶:
 
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) 【我投】
  此人我要踩:
 
100% (1) 【我投】
caikkk123 发表于 2016-11-3 03:00
我还是有点疑问,那有的障碍物我也可以选择不穿越啊,比如有很多障碍物,我并不知道穿越哪3个可以得到最 ...
.本文原创自1point3acres论坛
如果你不穿那个障碍物,那你那个方向是不能前进的
回复 支持 反对

使用道具 举报

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

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

使用道具 举报

我的人缘0
zhaoweigg 发表于 2016-11-3 04:40:54 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
OK, 在3d空间的bfs的感觉, 只不过 obstacle 那个维度只能增加或者不变
回复 支持 反对

使用道具 举报

我的人缘0
zzgzzm 发表于 2016-11-3 11:36:03 | 显示全部楼层
  此人我要顶:
 
100% (1) 【我投】
  此人我要踩:
 
0% (0) 【我投】
LumiG 发表于 2016-11-3 01:08. 1point3acres
哎就是用三个值(i, j, o)代表bfs时候的一个状态,然后看四个相邻点相邻点比如(i+1,j),是障碍物就搜(i,j+ ...

这个允许穿障碍物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;. 1point 3acres 论坛
  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;. more info on 1point3acres
  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. From 1point 3acres bbs
  21.       for (auto& dir:dirs) {. 1point 3acres 论坛
  22.         int ii = i + dir[0], jj = j + dir[1];
  23.         if (ii < 0 || ii >= m || jj < 0 || jj >= n) continue;. From 1point 3acres bbs
  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;
  28.         // haven't visited (ii,jj) or enter with fewer cheats used
  29.         if (tmpCht < nCht[ii][jj]) {
  30.           dist[ii][jj] = curDist + 1;  . From 1point 3acres bbs
  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% (暂未有人投票) 【我投】
zzgzzm 发表于 2016-11-3 11:36
这个允许穿障碍物follow-up,我也是用nCheat[][]记录到每个位置已经用多多少次穿越(i.e., cheats)。但我 ...

对啊,所以我用了个三维的bool数组来记录…这样就行了。
回复 支持 反对

使用道具 举报

我的人缘0
treeguard 发表于 2016-11-3 16:26:27 | 显示全部楼层
  此人我要顶:
 
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

关闭

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

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

custom counter

GMT+8, 2018-6-19 13:19

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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