May 2009 - May 2017 论坛八周年-你的足迹,我的骄傲


一亩三分地论坛

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

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

FB phone interview

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

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

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

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

x
今天下午刚刚结束的二面
一面时间挺短,大概就三十分钟,leetcode decode way那道题目
二面是今天下午刚刚结束. 1point3acres.com/bbs
连着G家,F家还是有点吃不消的,只能说时间安排略微囧. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
开始等了半个小时,人还没来。有了昨天G家等了一个小时人没来的经验之后,果断给recruiter打电话,然后帮忙安排,一会儿就打电话了
先做题目
1,给定一个01方阵,0表示能走,1表示不能走,从[0,0]点走到[n-1,n-1]点有多少种不同的走法-google 1point3acres
2,还是同样的01方阵,求[0,0]到[n-1,n-1]的最短路
3,最后一个很诡异……因为求最短路的空间是n^2,然后需要降低空间复杂度,然后问一个approximation的做法
最后聊了一会儿天就结束了


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


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

评分

3

查看全部评分

 楼主| hackerpainter 发表于 2015-11-14 10:56:46 | 显示全部楼层
关注一亩三分地公众号:
Warald_一亩三分地
最后approximation的做法把我干爆了……. From 1point 3acres bbs
大家谁有好的想法可以share一下……
表示以前从来没有遇到过这种做法……

补充内容 (2015-11-14 10:57):
说错了,是遇到过,没用过……囧
记得算法导论上关于TSP用到了
回复 支持 反对

使用道具 举报

小A要当码农 发表于 2015-11-14 14:24:39 | 显示全部楼层
关注一亩三分地微博:
Warald
hackerpainter 发表于 2015-11-14 10:56
最后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.1point3acres缃
求问楼主01方阵求最短路径是怎么做的呢?

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

使用道具 举报

 楼主| hackerpainter 发表于 2015-11-14 23:58:58 | 显示全部楼层
小A要当码农 发表于 2015-11-14 23:20
那不用额外O(n^2)的空间,如何表示父节点呢?多谢

不用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. Waral 鍗氬鏈夋洿澶氭枃绔,
DP应该可以,和CC上robot走格子有障碍那题很像
.鏈枃鍘熷垱鑷1point3acres璁哄潧
如果是往右和往下的方向是对的
但是四个方向都可以的话,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会有点问题
不好意思,我题目没有描述清楚
. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
楼主当时被问的是四个方向都可以嘛? 那你是用BFS搜索+visited数组做的? 以及同求科普Approximiation是啥玩意。。。
回复 支持 反对

使用道具 举报

 楼主| hackerpainter 发表于 2015-11-15 04:18:10 | 显示全部楼层
hyliu0000 发表于 2015-11-15 01:41
楼主 求科普  什么是approximation?

我感觉谷歌一下都比我解释得好 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数组,也可以不用. more info on 1point3acres.com
approximation我不会啊( ▼-▼ )

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

使用道具 举报

本版积分规则

关闭

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

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

custom counter

GMT+8, 2017-5-30 10:07

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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