一亩三分地论坛

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

扫码关注一亩三分地公众号
查看: 2543|回复: 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。最后拍照。. from: 1point3acres.com/bbs

第三轮: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的外围组成一个正方形)

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

补充内容 (2016-11-21 05:58):
谢谢 此用户无名 的提醒!   順求 offer !!!

评分

3

查看全部评分

wtcupup 发表于 2016-11-18 12:53:39 | 显示全部楼层
求问island 是 plus形状应该怎么做?
回复 支持 反对

使用道具 举报

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

使用道具 举报

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

使用道具 举报

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

评分

1

查看全部评分

回复 支持 反对

使用道具 举报

 楼主| lfxy 发表于 2016-11-19 05:56:23 | 显示全部楼层
wtcupup 发表于 2016-11-18 12:53
求问island 是 plus形状应该怎么做?

就是以每个不为1的cell为中心,向上下左右四个方向扩展,找到四个长度中最小的那个就是以这个Cell为中心的plus. 例如,下面的。 以(2,2)为中心的plus长度为1. (Plus的外围是一个正方形)

0 0 1 0 0 1 0
1 0 1 0 1 0 1. from: 1point3acres.com/bbs
1 1 1 1 1 1 1. from: 1point3acres.com/bbs
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
能不能请教一下楼主第一题的思路,无限大怎么证明哪种情况完全没解呢,除了有障碍完全把起点和终点包围起来 ...

这个我提出来了,是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的变形,题主能不能确定一下

对,类似,就是统计的方式改变一下
回复 支持 反对

使用道具 举报

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, 2016-12-9 09:58

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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