一亩三分地论坛

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

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

新鲜的 Facebook Onsite 面经

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

2016(10-12月) 码农类 博士 全职@Facebook - 网上海投 - Onsite |Otherfresh grad应届毕业生

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

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

x
10.28面经

Pirate: 白人小哥,给一堆二维坐标表示饭店,以及一个当前位置,找最近的k个饭店。如果不只是饭店,还有其标签怎么处理优化。
Jedi:亚裔女PhD,先是PhD research和behavior 问题。之后同是二维坐标找k个最近的点。不过Pirate是偏系统设计和数据结构优化,Jedi就是写个简单代码。
Ninja1:克罗地亚小哥,一个机器人在一个二维的地图上,对地图信息一无所知,包括长和宽。只有一个move命令可以控制机器人,可以东西南北走一步并返回true,如果是墙会返回false。求机器人可以到达位置的总个数。如何优化?
Ninja2:国人小哥:验证二叉查找树,先要求写递归法或迭代法,再写个分治解法。再来一题,找出二叉查找树最大的k个结点。


顺带求offer~~~



. 1point3acres.com/bbs


补充内容 (2016-11-1 04:16):
顺便提个电面题,利特扣得题的基本计算器,不过没有减号和除号;跟进问题是有括号如何处理。。。话说电面题怎么感觉比昂赛还难 -_-||

评分

1

查看全部评分

wtcupup 发表于 2016-11-1 04:22:39 | 显示全部楼层
ninja 2: validBST 分治解法难道不就是递归吗?有啥区别
回复 支持 反对

使用道具 举报

 楼主| alex8937 发表于 2016-11-1 04:25:22 | 显示全部楼层
wtcupup 发表于 2016-11-1 04:22
ninja 2: validBST 分治解法难道不就是递归吗?有啥区别

递归我用中序遍历写的,分治就真的是分治了
回复 支持 反对

使用道具 举报

hrl1991 发表于 2016-11-1 07:54:05 | 显示全部楼层
第一轮忍者的时间复杂度是不是O(n)? 如果是长方形的map可以达到所有的位置
回复 支持 反对

使用道具 举报

 楼主| alex8937 发表于 2016-11-1 09:59:01 | 显示全部楼层
hrl1991 发表于 2016-11-1 07:54. 1point 3acres 璁哄潧
第一轮忍者的时间复杂度是不是O(n)? 如果是长方形的map可以达到所有的位置
.1point3acres缃
嗯 不管是什么形状 都是O(n)
回复 支持 反对

使用道具 举报

mengmeng88717 发表于 2016-11-1 10:35:08 | 显示全部楼层
pirate怎样偏系统设计数据结构优化了,楼主能否具体说下?谢谢!
回复 支持 反对

使用道具 举报

mengmeng88717 发表于 2016-11-1 10:36:47 | 显示全部楼层
hr给楼主具体的面试时间表就是4轮么?为什么我的是三轮,下午有个q&a。。
回复 支持 反对

使用道具 举报

mengmeng88717 发表于 2016-11-1 11:01:26 | 显示全部楼层
1. heap + comparator? 有标签就是考虑权重?

补充内容 (2016-11-1 11:02):
3是怎么优化的哈. visit 1point3acres.com for more.
4. right -> root -> left遍历树?
问了楼主哪些behavior哈?
谢谢!
回复 支持 反对

使用道具 举报

 楼主| alex8937 发表于 2016-11-1 11:03:43 | 显示全部楼层
mengmeng88717 发表于 2016-11-1 10:36
hr给楼主具体的面试时间表就是4轮么?为什么我的是三轮,下午有个q&a。。

因为我是PhD吧。1光heap是不够的,会要求你优化的
回复 支持 反对

使用道具 举报

YY大帝 发表于 2016-11-1 11:29:46 | 显示全部楼层
请教下LZ第一问除了用到heap还能怎么优化,要用到KD tree吗
回复 支持 反对

使用道具 举报

mengmeng88717 发表于 2016-11-1 12:20:47 | 显示全部楼层
alex8937 发表于 2016-11-1 11:03
因为我是PhD吧。1光heap是不够的,会要求你优化的

楼主什么思路哈~~
回复 支持 反对

使用道具 举报

treeguard 发表于 2016-11-1 15:17:10 | 显示全部楼层
YY大帝 发表于 2016-11-1 11:29
请教下LZ第一问除了用到heap还能怎么优化,要用到KD tree吗

可以使用 Find the K-th largest element in unsorted array. see leetcode 215
回复 支持 反对

使用道具 举报

treeguard 发表于 2016-11-1 15:35:53 | 显示全部楼层
机器人: 是不是可以使用DFS 然后标记已经走过的点. 把已经走过的点放在set里面。
回复 支持 反对

使用道具 举报

 楼主| alex8937 发表于 2016-11-1 22:29:16 | 显示全部楼层
YY大帝 发表于 2016-11-1 11:29
请教下LZ第一问除了用到heap还能怎么优化,要用到KD tree吗

嗯 我用的B+tree 不过自我感觉system design面的一般
回复 支持 反对

使用道具 举报

 楼主| alex8937 发表于 2016-11-1 22:30:24 | 显示全部楼层
treeguard 发表于 2016-11-1 15:35
机器人: 是不是可以使用DFS 然后标记已经走过的点. 把已经走过的点放在set里面。

嗯 我就是这么做的
回复 支持 反对

使用道具 举报

treeguard 发表于 2016-11-2 10:15:23 | 显示全部楼层
alex8937 发表于 2016-11-1 22:30
嗯 我就是这么做的

有什么需要优化的吗?
回复 支持 反对

使用道具 举报

fangwei007 发表于 2016-11-4 05:58:15 | 显示全部楼层
lz第一题是维护一个size为K的max-heap吗?
回复 支持 反对

使用道具 举报

cuiyi 发表于 2016-11-22 00:34:48 | 显示全部楼层
alex8937 发表于 2016-11-1 04:25
递归我用中序遍历写的,分治就真的是分治了

嗯,分治还是要递归调用函数吧
回复 支持 反对

使用道具 举报

cuiyi 发表于 2016-11-22 00:39:11 | 显示全部楼层
楼主,请问一下机器人的题是用BFS吗?
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-5 17:05

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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