FB面经悲惨被虐记

电面：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.

Onsite: 1. a node has left, right and a parent poi

您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

font>



Final feedback: coding wasn't strong enough.


补充内容 (2016-9-3 23:34):
一亩三分编辑功能真让人吐血啊，想改改格式都不行。

补充内容 (2016-9-4 01:01):

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

wtcupup 发表于 2016-9-5 09:16
大神，解释下店面part2呢？

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

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

蓄水池抽样用一句话说就是 “对于第 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 的概率扔掉；

这时候对于第一个 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 概率是正确的。

此时相对于第一个 3，它总共可能会经历三次计算，第一次是 1/1 的概率进入 pool，第二次是看到第二个 3 的时候有 1/2 的概率留下来，最后一次是看到第三个 3 个时候，2/3 的几率不被替换掉。所以第一个元素留在最终 pool 里的概率就是 1 * 1/2 * 2/3 = 1/3，以此类推可以计算 stream of integer 中的任意一个 candidate，可以发现它们在概率的连乘中，前一项的分母和后一项的分子相等都可以被消掉，最终选中的概率就是 k / n.

这题我听朋友说 fb 还有一个变种是 “以均匀概率返回 array / stream of integer 中的最大值”，要求就比一开始给你 target number 高了一点点，但是更有意思~

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

xpli521 发表于 2016-9-6 03:14
赞! 能解释一下，“以均匀概率返回 array / stream of integer 中的最大值“的意思吗？，是要一边scan一 ...

不是，[2,1,3,4,5] 里面是 1 的概率返回 index 4，对应数组里的最大值 5. 假如输入是 [1,2,3,6,1,6] 的话，就要 1/2 概率分别返回 index = 3 和 index = 5，对应的是 array 里面的最大值 6.

主要需要处理的是数字是从 stream 依次过来的，一开始也不知道整个数据流里到底哪个最大，也不知道数据流到底有多长，所以要实时维护 & 更新。

lz leetcode刷到什么程度了？
我看lz帖子纪录 挺厉害的， 怎么挂了？ 他们要求这么高！！

感谢 lz 分享~

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

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

面个subarray是在behavior剩下10分钟给的两题， 写在白板。leetcode有刷了3遍了吧，短板就是在碰到跟leetcode有点差距的题的时候会卡住，毕竟是转行。比如说碰到题用有parent pointer的node的时候就会紧张. (LC里的node只有left 和right)

totolin 发表于 2016-9-4 00:11
面个subarray是在behavior剩下10分钟给的两题， 写在白板。leetcode有刷了3遍了吧，短板就是在碰到跟leetco ...

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

thanks for sharing ~ keep fighting ~ !

请问一下楼主是onsite之后多久拿到的feedback？

各位请多赏点大米啊！！！老婆大人需要T_T

slashGu 发表于 2016-9-4 00:55
请问一下楼主是onsite之后多久拿到的feedback？

2-3周吧吧

totolin 发表于 2016-9-4 01:02
2-3周吧吧

多谢楼主，我这周二刚去onsite完，看来还要一阵子

请问楼主电面PART 2水塘抽样具体怎么做？