一亩三分地论坛

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

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

Facebook 电面面经

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

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

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

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

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

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

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

.鏈枃鍘熷垱鑷1point3acres璁哄潧说实话我第一次见这么高冷的面试官 吓尿了 感觉必挂 觉得超级可惜  半年都无缘FB了
. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
就当攒了个人品吧。。。. 1point 3acres 璁哄潧



评分

1

查看全部评分

teedoo 发表于 2015-1-22 02:22:26 | 显示全部楼层
fb冷冻期是半年吗? 另外bless楼主
回复 支持 反对

使用道具 举报

yezi86 发表于 2015-1-22 02:35:15 | 显示全部楼层
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. Waral 鍗氬鏈夋洿澶氭枃绔,
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楼主

楼主只是猜测。。一般大公司都是半年吧。。
回复 支持 反对

使用道具 举报

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
. 1point 3acres 璁哄潧
嗯 我的第一个解法就是你的 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 | 显示全部楼层
数组那题是这个吧: 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
http://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那个题:我就是这样做的
. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
给一个数组比如: {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
哈哈哈哈 lz 我认识你~

哈哈哈 我也认识你
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-9 10:13

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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