推荐:数据科学课程和书籍清单以及培训讲座


一亩三分地论坛

 找回密码
 获取更多干活,快来注册

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

热乎乎的Facebook Onsite面经

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

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

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

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

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 1point 3acres 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的外围组成一个正方形). Waral 鍗氬鏈夋洿澶氭枃绔,

补充内容 (2016-11-20 10:39):.鏈枃鍘熷垱鑷1point3acres璁哄潧
更正前面的补充,以每个为1的cell为中心。谢谢 cuiyi

补充内容 (2016-11-21 05:58): 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
谢谢 此用户无名 的提醒!   順求 offer !!!

评分

3

查看全部评分

本帖被以下淘专辑推荐:

tiantiana 发表于 2016-12-5 08:47:21 | 显示全部楼层
关注一亩三分地公众号:
Warald_一亩三分地
lz 这第一题纯纯的extra hard的题吧。不是一般matrix上move可以解决的。。。。
-google 1point3acres
我这个解发不知道是不是最优,但应该算是一个solution吧:
由于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。觉得我的方法好,或是觉得我讲的清楚的,请给我评分。 :)
回复 支持 3 反对 0

使用道具 举报

2008 发表于 2016-12-6 00:51:42 | 显示全部楼层
关注一亩三分地微博:
Warald
第一题很简单啊, 矩阵无穷大,可以做一个框子,吧所以的点框住,然后留一个宽度为2的边,就在这个框里做dfs,或者dp,就可以了。.鏈枃鍘熷垱鑷1point3acres璁哄潧
第二题也很简单,从四个方向,分别算累加,如果是1就累加,是0就清零,然后求max(min(L,R,U,D))
回复 支持 1 反对 0

使用道具 举报

鼓頔娜夫 发表于 2016-11-26 01:04:37 | 显示全部楼层
zhihaosun 发表于 2016-11-23 09:54.鏈枃鍘熷垱鑷1point3acres璁哄潧
做四遍遍历,记录四个方向上每个格最长的连续长度,最后遍历一遍,取四个方向上的连续长度的最小值就是十 ...

对 我也是这个思路 最后的复杂度是O(MN)的
回复 支持 1 反对 0

使用道具 举报

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
1 1 1 1 1 1 1
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?
.1point3acres缃
不是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的情况下如何终止搜索

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

使用道具 举报

本版积分规则

关闭

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

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

custom counter

GMT+8, 2017-7-24 13:04

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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