一亩三分地论坛

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

一亩三分地官方iOS手机应用下载
查看: 4712|回复: 46
收起左侧

热乎乎的Facebook Onsite面经

[复制链接] |试试Instant~ |关注本帖
lfxy 发表于 2016-11-18 12:48:17 | 显示全部楼层 |阅读模式

2016(10-12月) 码农类 博士 全职@Facebook - 内推 - Onsite |Other在职跳槽

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

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

x
一共四轮,中间有45分钟的Lunch。
第一轮:Coding: infinite matrix, 有一个destination, 有一个source, 和一个blocks存一些不能走到坐标,问从source能不能到达destination, 从source (x,y) 只能走:x+/-1, x +/- 2, y +/-1, y +/- 2, 所以一共有8中组合。注意Matrix是infinite的. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
  Follow up: optimization
. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
第二轮:BQ+Coding: Matrix中有0和1, 求1组成的最大的plus (+)形状的长度.。前面说的多了,后面有个function没写完,解释了思路,然后说OK。最后拍照。

第三轮:Design,设计FB event reminder, 就是允许用户设置在事件发生之前多长时间发出提醒, 主要是讲怎么扩展数据库. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
鏉ユ簮涓浜.涓夊垎鍦拌鍧.
第四轮:Coding, 给一个dictionary和一个字符串,可能有匹配符,如何建立一个data structure, 实现insert 和 search. 用Trie 和DFS


. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴

补充内容 (2016-11-19 06:02):
第一轮: 就是以每个不为1的cell为中心,向上下左右四个方向扩展,找到四个长度中最小的那个就是以这个Cell为中心的plus. 例如,下面的。 以(2,2)为中心的plus长度为1. (Plus的外围组成一个正方形). visit 1point3acres.com for more.

补充内容 (2016-11-20 10:39):. From 1point 3acres bbs
更正前面的补充,以每个为1的cell为中心。谢谢 cuiyi

补充内容 (2016-11-21 05:58):. from: 1point3acres.com/bbs
谢谢 此用户无名 的提醒!   順求 offer !!!

评分

3

查看全部评分

本帖被以下淘专辑推荐:

tiantiana 发表于 2016-12-5 08:47:21 | 显示全部楼层
关注一亩三分地公众号:
Warald_一亩三分地
lz 这第一题纯纯的extra hard的题吧。不是一般matrix上move可以解决的。。。。

我这个解发不知道是不是最优,但应该算是一个solution吧:. visit 1point3acres.com for more.
由于matrix无限,不能没完没了的bfs 或是dfs。其实这次就是问,blocks里面的点可不可以把source或事destination围起来,围起来一个,就return false,othersize return true。我讲到这里,不知道有没有同学恍然大悟。是的,如果从source出发,或事destination出发,有一个无路可走就是false。那么问题来了,怎么判断无路可走,又是从哪个点走呢。答案是,必须从两点一起走,不然不行。:
1. 建立两个queue 分别存 source 和dest 接下来可以走的点。
2. 需要用两个visited_set记录source 和dest走过的点。
3. 用一个while loop 判断 source 和dest下一个可走的点。
4. 如果 下一个走的点在visited里面,或是blocks里面,不操作。否则把新的点加到queue里面。
5. 如果dest走到了source,或事source走到了dest,return true。
6. 如果两个queue又一个空了,说明这个点被blocks围住了,return false。

p。s。觉得我的方法好,或是觉得我讲的清楚的,请给我评分。 :)
回复 支持 1 反对 0

使用道具 举报

wtcupup 发表于 2016-11-18 12:53:39 | 显示全部楼层
关注一亩三分地微博:
Warald
求问island 是 plus形状应该怎么做?
回复 支持 反对

使用道具 举报

31415926 发表于 2016-11-18 14:10:43 | 显示全部楼层
Today's Uday ?
回复 支持 反对

使用道具 举报

Xochitl 发表于 2016-11-18 14:17:53 | 显示全部楼层
能不能请教一下楼主第一题的思路,无限大怎么证明哪种情况完全没解呢,除了有障碍完全把起点和终点包围起来的情况,其他情况什么时候可以是这个dfs或者bfs的终止条件呢
求职神器indeed - 在全球最大的求职网站找找适合你的工作?
回复 支持 反对

使用道具 举报

bzplbn 发表于 2016-11-19 02:39:23 | 显示全部楼层
求问楼主是new grad吗?怎么还考了design?

评分

1

查看全部评分

回复 支持 反对

使用道具 举报

 楼主| lfxy 发表于 2016-11-19 05:56:23 | 显示全部楼层
wtcupup 发表于 2016-11-18 12:53.鏈枃鍘熷垱鑷1point3acres璁哄潧
求问island 是 plus形状应该怎么做?
. from: 1point3acres.com/bbs
就是以每个不为1的cell为中心,向上下左右四个方向扩展,找到四个长度中最小的那个就是以这个Cell为中心的plus. 例如,下面的。 以(2,2)为中心的plus长度为1. (Plus的外围是一个正方形)

0 0 1 0 0 1 0
1 0 1 0 1 0 1
1 1 1 1 1 1 1. Waral 鍗氬鏈夋洿澶氭枃绔,
0 0 1 0 0 0 0
0 0 0 0 0 0 0
回复 支持 反对

使用道具 举报

 楼主| lfxy 发表于 2016-11-19 05:59:28 | 显示全部楼层
Xochitl 发表于 2016-11-18 14:17. 1point3acres.com/bbs
能不能请教一下楼主第一题的思路,无限大怎么证明哪种情况完全没解呢,除了有障碍完全把起点和终点包围起来 ...

这个我提出来了,是infinite的,所以没有终止,除了你说的情况,一定会到达的。所以到达就是终止。你说的情况可以用来优化
回复 支持 反对

使用道具 举报

 楼主| lfxy 发表于 2016-11-19 05:59:44 | 显示全部楼层
bzplbn 发表于 2016-11-19 02:39 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
求问楼主是new grad吗?怎么还考了design?

不是new grad
回复 支持 反对

使用道具 举报

sqz2017er 发表于 2016-11-19 06:17:19 | 显示全部楼层
觉得第二题有点像 leetcode 361的变形,题主能不能确定一下
回复 支持 反对

使用道具 举报

sqz2017er 发表于 2016-11-19 06:22:33 | 显示全部楼层
一个问题,第一轮为什么是8种?(x+1,y +1/-1/+2/-2), (x-1, y +1/-1/+2/-2), (x+2, y +1/-1/+2/-2), (x-2, y +1/-1/+2/-2) 我感觉是16种呢
回复 支持 反对

使用道具 举报

 楼主| lfxy 发表于 2016-11-19 06:29:39 | 显示全部楼层
sqz2017er 发表于 2016-11-19 06:22
一个问题,第一轮为什么是8种?(x+1,y +1/-1/+2/-2), (x-1, y +1/-1/+2/-2), (x+2, y +1/-1/+2/-2), (x- ...

Chess中knight的走法:(x+/-1,y+/-2), (x+/-2, y+/-1) 8种组合,不是全排列组合
回复 支持 反对

使用道具 举报

 楼主| lfxy 发表于 2016-11-19 06:32:20 | 显示全部楼层
sqz2017er 发表于 2016-11-19 06:17
觉得第二题有点像 leetcode 361的变形,题主能不能确定一下
-google 1point3acres
对,类似,就是统计的方式改变一下
回复 支持 反对

使用道具 举报

elvia 发表于 2016-11-19 07:09:14 | 显示全部楼层
楼主求问面试TIMELINE 是多少, 电面后大概多久ONSITE?
回复 支持 反对

使用道具 举报

cuiyi 发表于 2016-11-20 06:01:02 | 显示全部楼层
lfxy 发表于 2016-11-19 05:56
就是以每个不为1的cell为中心,向上下左右四个方向扩展,找到四个长度中最小的那个就是以这个Cell为中心 ...

楼主请问一下,是不是应该以为1的cell为中心啊?这个题跟bomb enemy差不多好像。
回复 支持 反对

使用道具 举报

cuiyi 发表于 2016-11-20 06:44:38 | 显示全部楼层
lfxy 发表于 2016-11-19 05:59
这个我提出来了,是infinite的,所以没有终止,除了你说的情况,一定会到达的。所以到达就是终止。你说的 ...

我想用BFS,从source往外扩散,只是不知道在无法到达destination的情况下如何终止搜索
回复 支持 反对

使用道具 举报

cuiyi 发表于 2016-11-20 06:45:22 | 显示全部楼层
楼主能不能讲一下系统设计题?我也会有一轮系统设计面试
回复 支持 反对

使用道具 举报

鼓頔娜夫 发表于 2016-11-20 07:53:04 | 显示全部楼层
lz可以分享一下第二题的思路吗?我的基本想法是扫四遍matrix, 第一次对matrix[i][j]数每一行从左边开始有多少个1,第二次从右边数,第三次从上往下数每一列,第四次从下往上
回复 支持 反对

使用道具 举报

 楼主| lfxy 发表于 2016-11-20 10:37:17 | 显示全部楼层
elvia 发表于 2016-11-19 07:09
楼主求问面试TIMELINE 是多少, 电面后大概多久ONSITE?

查了一下邮件, 电面后一个星期+4天收到recruiter的电话
回复 支持 反对

使用道具 举报

 楼主| lfxy 发表于 2016-11-20 10:37:58 | 显示全部楼层
cuiyi 发表于 2016-11-20 06:01
楼主请问一下,是不是应该以为1的cell为中心啊?这个题跟bomb enemy差不多好像。

嗯,是以为1的cell为中心
回复 支持 反对

使用道具 举报

 楼主| lfxy 发表于 2016-11-20 10:41:36 | 显示全部楼层
cuiyi 发表于 2016-11-20 06:44
我想用BFS,从source往外扩散,只是不知道在无法到达destination的情况下如何终止搜索

可以分别从source和destination双向BFS,找Collision,同时也能解决destination不能到达的情况
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2017-2-22 19:48

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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