一亩三分地论坛

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

扫码关注一亩三分地公众号
查看: 975|回复: 14
收起左侧

FB phone interview

[复制链接] |试试Instant~ |关注本帖
hackerpainter 发表于 2015-11-14 10:53:25 | 显示全部楼层 |阅读模式

2016(10-12月) 码农类 硕士 实习@Facebook - 内推 - 技术电面 |Otherfresh grad应届毕业生

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

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

x
今天下午刚刚结束的二面
一面时间挺短,大概就三十分钟,leetcode decode way那道题目
二面是今天下午刚刚结束
连着G家,F家还是有点吃不消的,只能说时间安排略微囧

开始等了半个小时,人还没来。有了昨天G家等了一个小时人没来的经验之后,果断给recruiter打电话,然后帮忙安排,一会儿就打电话了
先做题目
1,给定一个01方阵,0表示能走,1表示不能走,从[0,0]点走到[n-1,n-1]点有多少种不同的走法
2,还是同样的01方阵,求[0,0]到[n-1,n-1]的最短路
3,最后一个很诡异……因为求最短路的空间是n^2,然后需要降低空间复杂度,然后问一个approximation的做法.1point3acres缃
最后聊了一会儿天就结束了. From 1point 3acres bbs


继续求大米~求大米~求大米~求offer~求offer~求offer~

. visit 1point3acres.com for more.
补充内容 (2015-11-15 00:00):
不好意思,二面有个描述漏了。第一题是只有往下和往右的方向,第二题是四个方向都可以

评分

3

查看全部评分

 楼主| hackerpainter 发表于 2015-11-14 10:56:46 | 显示全部楼层
最后approximation的做法把我干爆了……
大家谁有好的想法可以share一下……
表示以前从来没有遇到过这种做法……

补充内容 (2015-11-14 10:57):
鏉ユ簮涓浜.涓夊垎鍦拌鍧. 说错了,是遇到过,没用过……囧
记得算法导论上关于TSP用到了
回复 支持 反对

使用道具 举报

小A要当码农 发表于 2015-11-14 14:24:39 | 显示全部楼层
hackerpainter 发表于 2015-11-14 10:56. more info on 1point3acres.com
最后approximation的做法把我干爆了……
大家谁有好的想法可以share一下……
表示以前从来没有遇到过这种 ...

求问楼主01方阵求最短路径是怎么做的呢?
回复 支持 反对

使用道具 举报

 楼主| hackerpainter 发表于 2015-11-14 21:41:21 | 显示全部楼层
小A要当码农 发表于 2015-11-14 14:24
求问楼主01方阵求最短路径是怎么做的呢?

就BFS就行
具体做法我认为是基本功了,你可以先自己试试
回复 支持 反对

使用道具 举报

小A要当码农 发表于 2015-11-14 23:20:01 | 显示全部楼层
hackerpainter 发表于 2015-11-14 21:41
就BFS就行
具体做法我认为是基本功了,你可以先自己试试
鏉ユ簮涓浜.涓夊垎鍦拌鍧.
那不用额外O(n^2)的空间,如何表示父节点呢?多谢
回复 支持 反对

使用道具 举报

Toby 发表于 2015-11-14 23:48:48 | 显示全部楼层
小A要当码农 发表于 2015-11-14 01:24
求问楼主01方阵求最短路径是怎么做的呢?

DP应该可以,和CC上robot走格子有障碍那题很像
回复 支持 反对

使用道具 举报

 楼主| hackerpainter 发表于 2015-11-14 23:58:58 | 显示全部楼层
小A要当码农 发表于 2015-11-14 23:20
那不用额外O(n^2)的空间,如何表示父节点呢?多谢
. visit 1point3acres.com for more.
不用n^2的空间,应该就是approximation的做法了吧,不好意思,这个我没回答上来
如果是n^2的空间,那么就是用队列存储就好
回复 支持 反对

使用道具 举报

 楼主| hackerpainter 发表于 2015-11-14 23:59:40 | 显示全部楼层
不好意思,二面有个描述漏了。第一题是只有往下和往右的方向,第二题是四个方向都可以
回复 支持 反对

使用道具 举报

 楼主| hackerpainter 发表于 2015-11-15 00:00:16 | 显示全部楼层
Toby 发表于 2015-11-14 23:48
DP应该可以,和CC上robot走格子有障碍那题很像

如果是往右和往下的方向是对的
但是四个方向都可以的话,dp会有点问题
不好意思,我题目没有描述清楚
回复 支持 反对

使用道具 举报

plich 发表于 2015-11-15 01:30:03 | 显示全部楼层
最后一个follow挺难啊,果然fb二面就是这样……
回复 支持 反对

使用道具 举报

hyliu0000 发表于 2015-11-15 01:41:14 | 显示全部楼层
楼主 求科普  什么是approximation?
回复 支持 反对

使用道具 举报

小A要当码农 发表于 2015-11-15 02:36:28 | 显示全部楼层
hackerpainter 发表于 2015-11-15 00:00
如果是往右和往下的方向是对的
但是四个方向都可以的话,dp会有点问题
不好意思,我题目没有描述清楚
. visit 1point3acres.com for more.
楼主当时被问的是四个方向都可以嘛? 那你是用BFS搜索+visited数组做的? 以及同求科普Approximiation是啥玩意。。。
回复 支持 反对

使用道具 举报

 楼主| hackerpainter 发表于 2015-11-15 04:18:10 | 显示全部楼层
hyliu0000 发表于 2015-11-15 01:41
楼主 求科普  什么是approximation?
. 1point3acres.com/bbs
我感觉谷歌一下都比我解释得好 2333333333
回复 支持 反对

使用道具 举报

 楼主| hackerpainter 发表于 2015-11-15 04:18:37 | 显示全部楼层
小A要当码农 发表于 2015-11-15 02:36
楼主当时被问的是四个方向都可以嘛? 那你是用BFS搜索+visited数组做的? 以及同求科普Approximiation是 ...

可以用visited数组,也可以不用
approximation我不会啊( ▼-▼ )
回复 支持 反对

使用道具 举报

小A要当码农 发表于 2015-11-15 05:30:17 | 显示全部楼层
hackerpainter 发表于 2015-11-15 04:18
可以用visited数组,也可以不用. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
approximation我不会啊( ▼-▼ )

好吧,感觉好难...祝楼主好运啦。。
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-8 08:35

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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