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


一亩三分地论坛

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

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

Facebook 电面面经

[复制链接] |试试Instant~ |关注本帖
hesha0987 发表于 2015-1-22 00:54:37 | 显示全部楼层 |阅读模式

2015(1-3月) 码农类 硕士 全职@Facebook - 内推 - 技术电面 |Other

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

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

x
昨天电面 打电话来的是个美国人 一上来他就心情不好 collabedit他也用不了 换了好几个才终于成功. 1point 3acres 璁哄潧

期间他特别高冷 几乎我每句话都是以被他打断而结束 including 最后一句“Thank you for answering my question”都被打断

题目很简单 都是面经中题
1. why facebook 然后不依不挠 追根问底 对general的回答不屑一顾。。。. From 1point 3acres bbs
2. 随机返回数组中最大值的下标 要求O(1)空间复杂度
3. 返回BST中第5个最小值 followup是各种降低时间/空间复杂度
. 鍥磋鎴戜滑@1point 3 acres
--他的眼里揉不得半个bug--

说实话我第一次见这么高冷的面试官 吓尿了 感觉必挂 觉得超级可惜  半年都无缘FB了
. from: 1point3acres.com/bbs
就当攒了个人品吧。。。
. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷


评分

1

查看全部评分

teedoo 发表于 2015-1-22 02:22:26 | 显示全部楼层
关注一亩三分地公众号:
Warald_一亩三分地
fb冷冻期是半年吗? 另外bless楼主
回复 支持 反对

使用道具 举报

yezi86 发表于 2015-1-22 02:35:15 | 显示全部楼层
关注一亩三分地微博:
Warald
BST的那道题时间就是O(N) / O(k) 吧。空间怎么优化,必须要栈啊,那就O(h)了。求指点!
回复 支持 反对

使用道具 举报

kwang75 发表于 2015-1-22 03:03:50 | 显示全部楼层
第一题的随机是什么意思呢?不能有额外空间那只能扫数组了吧
回复 支持 反对

使用道具 举报

 楼主| hesha0987 发表于 2015-1-22 03:04:31 | 显示全部楼层
yezi86 发表于 2015-1-22 02:35
BST的那道题时间就是O(N) / O(k) 吧。空间怎么优化,必须要栈啊,那就O(h)了。求指点!

面试官相当高冷 他没有任何提示 也没说最优是怎样
楼主用的是inorder traversal 递归实现 所以如果已知了K是5的话 时间空间应该是O(1)吧
回复 支持 反对

使用道具 举报

 楼主| hesha0987 发表于 2015-1-22 03:05:21 | 显示全部楼层
teedoo 发表于 2015-1-22 02:22
fb冷冻期是半年吗? 另外bless楼主
-google 1point3acres
楼主只是猜测。。一般大公司都是半年吧。。
回复 支持 反对

使用道具 举报

landuostorm 发表于 2015-1-22 03:08:14 | 显示全部楼层
第三题,可以BST每个Node存左子树有多少个节点,然后二分
回复 支持 反对

使用道具 举报

zengm321 发表于 2015-1-22 03:25:50 | 显示全部楼层
hesha0987 发表于 2015-1-22 03:05.鐣欏璁哄潧-涓浜-涓夊垎鍦
楼主只是猜测。。一般大公司都是半年吧。。

不是一年吗?
回复 支持 反对

使用道具 举报

zengm321 发表于 2015-1-22 03:27:44 | 显示全部楼层
BST那道,我能想到 1)deleteMin 5 次 2) inorder traverse成数组,然后select kth smallest
回复 支持 反对

使用道具 举报

 楼主| hesha0987 发表于 2015-1-22 03:40:35 | 显示全部楼层

那可能就是一年吧 反正楼主没啥念想了
回复 支持 反对

使用道具 举报

 楼主| hesha0987 发表于 2015-1-22 03:41:29 | 显示全部楼层
zengm321 发表于 2015-1-22 03:27
BST那道,我能想到 1)deleteMin 5 次 2) inorder traverse成数组,然后select kth smallest

嗯 我的第一个解法就是你的 2) 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
然后followup要求降低复杂度
回复 支持 反对

使用道具 举报

cjlm007 发表于 2015-1-22 04:33:12 | 显示全部楼层
BST用Morris遍历可以空间O(1)
回复 支持 反对

使用道具 举报

kwang75 发表于 2015-1-22 04:41:56 | 显示全部楼层
能麻烦楼主说一下第一题随机返回数组中最大的数是什么意思么?谢谢!
回复 支持 反对

使用道具 举报

鱼吃鱼翅 发表于 2015-1-22 04:52:14 | 显示全部楼层
BST那个题,能不能用inorder traversal,用i记录扫到的值的个数,当i等于5的时候直接返回这个值就可以了,这样空间和时间最坏是O(n)最好是O(1)

然后楼主能不能解释一下数组那题,我没看懂什么意思
回复 支持 反对

使用道具 举报

cjlm007 发表于 2015-1-22 05:01:43 | 显示全部楼层
数组那题是这个吧:
. more info on 1point3acres.comhttp://www.fgdsb.com/2015/01/15/random-maximum/
回复 支持 反对

使用道具 举报

 楼主| hesha0987 发表于 2015-1-22 05:02:48 | 显示全部楼层
鱼吃鱼翅 发表于 2015-1-22 04:52
BST那个题,能不能用inorder traversal,用i记录扫到的值的个数,当i等于5的时候直接返回这个值就可以了, ...

BST那个题:我就是这样做的. from: 1point3acres.com/bbs

给一个数组比如: {1,2,3,5,5,3,2,5}
请返回最大数的下标。
如果最大数出现了好几次,就随机返回一个,随机是指,每个最大数的下标被选中的概率是一样的
回复 支持 反对

使用道具 举报

 楼主| hesha0987 发表于 2015-1-22 05:03:04 | 显示全部楼层
kwang75 发表于 2015-1-22 04:41
能麻烦楼主说一下第一题随机返回数组中最大的数是什么意思么?谢谢!

给一个数组比如: {1,2,3,5,5,3,2,5}
请返回最大数的下标。
如果最大数出现了好几次,就随机返回一个,随机是指,每个最大数的下标被选中的概率是一样的
回复 支持 反对

使用道具 举报

 楼主| hesha0987 发表于 2015-1-22 05:05:46 | 显示全部楼层
cjlm007 发表于 2015-1-22 05:01
数组那题是这个吧:
http://www.fgdsb.com/2015/01/15/random-maximum/

是的 这个博客好赞!我要收藏!多谢分享
回复 支持 反对

使用道具 举报

yapingchen1990 发表于 2015-1-22 08:20:58 | 显示全部楼层
哈哈哈哈 lz 我认识你~
回复 支持 反对

使用道具 举报

 楼主| hesha0987 发表于 2015-1-22 09:50:38 | 显示全部楼层
yapingchen1990 发表于 2015-1-22 08:20-google 1point3acres
哈哈哈哈 lz 我认识你~
. from: 1point3acres.com/bbs
哈哈哈 我也认识你
回复 支持 反对

使用道具 举报

本版积分规则

关闭

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

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

custom counter

GMT+8, 2017-7-28 23:19

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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