一亩三分地论坛

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

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

FB面经悲惨被虐记

[复制链接] |试试Instant~ |关注本帖
totolin 发表于 2016-9-3 23:32:41 | 显示全部楼层 |阅读模式

2016(4-6月) 码农类 博士 全职@Facebook - 内推 - 技术电面 Onsite |Fail在职跳槽

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

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

x
电面:1. part1: LC 3SUM.              part2: Given an array with possible repeated numbers, randomly output the index of a given number. Example: given [1,2,3,3,3], 3, output 2,3,or 4 with equal probability. Solution: use reservoir sampling.
          2. LC WordBreak.
. 鍥磋鎴戜滑@1point 3 acres
Onsite: 1. a node has left, right and a parent pointer. Given two nodes in a binary tree, find a path from the first node to the second node. Need O(M) solution, M being the depth of tree.
           2. maximum subarray sum, maximum subarray product. (Was expected to finish both of these two problems in less than 10 minutes)
[size=14.6667px]            3. part 1: Merge two sorted linked list. Part2: topological sort/DFS, similar to LC course schedule.
[size=14.6667px]            4. System Design. FB needs to serve billions of ad per day. How to design such a system that can handle such huge amount of request?[size=14.6667px]



. visit 1point3acres.com for more.
Final feedback: coding wasn't strong enough.

. more info on 1point3acres.com
补充内容 (2016-9-3 23:34):.鐣欏璁哄潧-涓浜-涓夊垎鍦
一亩三分编辑功能真让人吐血啊,想改改格式都不行。
. 鍥磋鎴戜滑@1point 3 acres
补充内容 (2016-9-4 01:01):

各位麻烦多赏点大米啊!!!老婆大人需要T_T

评分

13

查看全部评分

本帖被以下淘专辑推荐:

mnmunknown 发表于 2016-9-5 09:39:14 | 显示全部楼层
wtcupup 发表于 2016-9-5 09:16
大神,解释下店面part2呢?

过奖了,我还差得很远。。=。=

电面 part2 就是非常典型的蓄水池抽样啊,属于 online algorithm 的一种,最大的好处是可以在事先完全不知道 input size 多大的情况下依然能以相同的概率返回 k 个目标元素,在这里 K = 1,选择元素的 constraint 是 nums == targetNumber.-google 1point3acres

蓄水池抽样用一句话说就是 “对于第 i 个元素,我们以 k / i 的概率留在抽样结果中,(i - k) / i” 的几率给扔掉。在这题里,根据给定条件可以改成 “对于第 i 个元素,如果不等于 target number,直接扔;否则的话,有 (i - 1) / i 的概率替换掉原来的抽样结果。”

在例子中,[1,2,3,3,3], target = 3, k = 1 的情况下,我们初始 i = 1 ,一开始看到 1 , 2 因为不等于 3,直接跳过不产生任何影响;看到第一个 3 的时候,有 1 / 1 的概率留下其 index (可以把那个留下的 index pool 当成我们的 “蓄水池”),同时 i ++ 变成 2; 再看到第二个 3 的时候,有 1/2 的概率用这个 3 的 index 取代我们 pool 里的那个,1/2 的概率扔掉;
. Waral 鍗氬鏈夋洿澶氭枃绔,
这时候对于第一个 3 来讲,如果这个 stream of integer 中真的只有一个 3,那它被选中的概率是 1.0 ; 当有两个元素的时候,它会有 1/1 的概率在第一次“抽样竞选”中进入 pool,有 1/2 的概率被第二个 3 给踢掉,所以其最终被选中的概率就是 1/2;而对于第二个 3 来讲,其进入 pool 的概率也是 1/2,可以看到在 stream 中有两个 target number 的时候,每个 target number 被选中的概率是均等的。

我们看到第三个 3 的时候,它替换进入 pool 的概率就是 1 / 3,被直接忽略的概率是 2 / 3; 相对于这个元素,它被选中的几率是 1/3 ,对于一个出现了三次的 target number 概率是正确的。. from: 1point3acres.com/bbs

此时相对于第一个 3,它总共可能会经历三次计算,第一次是 1/1 的概率进入 pool,第二次是看到第二个 3 的时候有 1/2 的概率留下来,最后一次是看到第三个 3 个时候,2/3 的几率不被替换掉。所以第一个元素留在最终 pool 里的概率就是 1 * 1/2 * 2/3 = 1/3,以此类推可以计算 stream of integer 中的任意一个 candidate,可以发现它们在概率的连乘中,前一项的分母和后一项的分子相等都可以被消掉,最终选中的概率就是 k / n.. From 1point 3acres bbs
.鏈枃鍘熷垱鑷1point3acres璁哄潧
这题我听朋友说 fb 还有一个变种是 “以均匀概率返回 array / stream of integer 中的最大值”,要求就比一开始给你 target number 高了一点点,但是更有意思~

补充内容 (2016-9-5 12:19):
"有 (i - 1) / i 的概率替换掉原来的抽样结果" 笔误,是 1 / i 的概率替换

评分

1

查看全部评分

回复 支持 1 反对 0

使用道具 举报

leonardcohen 发表于 2016-9-3 23:47:49 | 显示全部楼层
lz leetcode刷到什么程度了?
. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴我看lz帖子纪录 挺厉害的, 怎么挂了? 他们要求这么高!!
回复 支持 反对

使用道具 举报

mnmunknown 发表于 2016-9-3 23:55:47 | 显示全部楼层
感谢 lz 分享~

onsite 第一题看起来是个 LCA 问题,类似两个链表找 intersection,O(M).

请问后面两个 subarray 问题是 behavior 轮最后给的吗,还是 LCA 这题之后又出的? 10 分钟用键盘写完还好,不过面试的时候考虑和面试官交流输入输出+白板的话,时间感觉略紧。。
回复 支持 反对

使用道具 举报

 楼主| totolin 发表于 2016-9-4 00:11:26 | 显示全部楼层
面个subarray是在behavior剩下10分钟给的两题, 写在白板。leetcode有刷了3遍了吧,短板就是在碰到跟leetcode有点差距的题的时候会卡住,毕竟是转行。比如说碰到题用有parent pointer的node的时候就会紧张. (LC里的node只有left 和right)
回复 支持 反对

使用道具 举报

mnmunknown 发表于 2016-9-4 00:21:08 | 显示全部楼层
totolin 发表于 2016-9-4 00:11
面个subarray是在behavior剩下10分钟给的两题, 写在白板。leetcode有刷了3遍了吧,短板就是在碰到跟leetco ...

这类 OJ 上没有的类型题要是头一次遇到确实容易没防备,面经很重要啊 =.=

thanks for sharing ~ keep fighting ~ !
回复 支持 反对

使用道具 举报

slashGu 发表于 2016-9-4 00:55:42 | 显示全部楼层
请问一下楼主是onsite之后多久拿到的feedback?
回复 支持 反对

使用道具 举报

 楼主| totolin 发表于 2016-9-4 00:59:37 | 显示全部楼层
各位请多赏点大米啊!!!老婆大人需要T_T
回复 支持 反对

使用道具 举报

 楼主| totolin 发表于 2016-9-4 01:02:26 | 显示全部楼层
slashGu 发表于 2016-9-4 00:55
请问一下楼主是onsite之后多久拿到的feedback?

2-3周吧吧
回复 支持 反对

使用道具 举报

slashGu 发表于 2016-9-4 01:04:34 | 显示全部楼层
. visit 1point3acres.com for more.
多谢楼主,我这周二刚去onsite完,看来还要一阵子
回复 支持 反对

使用道具 举报

ariesxiao 发表于 2016-9-4 06:05:29 | 显示全部楼层
请问楼主电面PART 2水塘抽样具体怎么做?
回复 支持 反对

使用道具 举报

ariesxiao 发表于 2016-9-4 06:05:39 | 显示全部楼层
还有ONSITE 1的思路是啥呢?
回复 支持 反对

使用道具 举报

smellycat 发表于 2016-9-4 09:55:01 | 显示全部楼层
LZ,电面1,part2 reservoir sampling 是怎么用到这道题里的呀?
我只能想到:用hashmap去存value和index的list,当查找一个数时,随机产生一个0~list.size()-1的数j,然后返回list.get(j)
是不是需要考虑在array size比较大的时候用什么方法比较好?
回复 支持 反对

使用道具 举报

smellycat 发表于 2016-9-4 10:16:38 | 显示全部楼层
ariesxiao 发表于 2016-9-4 06:05
还有ONSITE 1的思路是啥呢?

参考LC160,找两个链表的intersection
回复 支持 反对

使用道具 举报

wtcupup 发表于 2016-9-4 16:34:24 | 显示全部楼层
请大神解释为啥reservoir sampling和电面part2有关?
回复 支持 反对

使用道具 举报

houqingniao 发表于 2016-9-5 09:02:38 | 显示全部楼层
mnmunknown 发表于 2016-9-3 23:55
感谢 lz 分享~

onsite 第一题看起来是个 LCA 问题,类似两个链表找 intersection,O(M).

oniste1,感觉只用parent指针就可以了。 跟left right 没啥关系啊
回复 支持 反对

使用道具 举报

houqingniao 发表于 2016-9-5 09:03:10 | 显示全部楼层
totolin 发表于 2016-9-4 00:11
面个subarray是在behavior剩下10分钟给的两题, 写在白板。leetcode有刷了3遍了吧,短板就是在碰到跟leetco ...

跟parent没啥关系吧
回复 支持 反对

使用道具 举报

mnmunknown 发表于 2016-9-5 09:06:58 | 显示全部楼层
houqingniao 发表于 2016-9-5 09:02
oniste1,感觉只用parent指针就可以了。 跟left right 没啥关系啊
. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
是啊,所以我说类似两个链表找 intersection,一路往上就行了。对于两个 node 之间路线上的交叉点,位置上说是这两个 node 在树上的 LCA
回复 支持 反对

使用道具 举报

wtcupup 发表于 2016-9-5 09:16:25 | 显示全部楼层
mnmunknown 发表于 2016-9-5 09:06
是啊,所以我说类似两个链表找 intersection,一路往上就行了。对于两个 node 之间路线上的交叉点,位置 ...

大神,解释下店面part2呢?
回复 支持 反对

使用道具 举报

xpli521 发表于 2016-9-6 03:14:40 | 显示全部楼层
mnmunknown 发表于 2016-9-4 18:39
过奖了,我还差得很远。。=。=. From 1point 3acres bbs

电面 part2 就是非常典型的蓄水池抽样啊,属于 online algorithm 的一 ...
.1point3acres缃
赞! 能解释一下,“以均匀概率返回 array / stream of integer 中的最大值“的意思吗?,是要一边scan一边找最大值,然后返回最大值的index? 譬如 2 1 3 4 5 ,这就应该返回 0, 0, 2,3,4这样?
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

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

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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