FB面经悲惨被虐记

还有ONSITE 1的思路是啥呢？

LZ,电面1，part2 reservoir sampling 是怎么用到这道题里的呀？
我只能想到：用hashmap去存value和index的list，当查找一个数时，随机产生一个0~list.size()-1的数j，然后返回list.get(j)
是不是需要考虑在array size比较大的时候用什么方法比较好？

ariesxiao 发表于 2016-9-4 06:05
还有ONSITE 1的思路是啥呢？

参考LC160，找两个链表的intersection

请大神解释为啥reservoir sampling和电面part2有关？

mnmunknown 发表于 2016-9-3 23:55
感谢 lz 分享~

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

oniste1,感觉只用parent指针就可以了。 跟left right 没啥关系啊

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

跟parent没啥关系吧

houqingniao 发表于 2016-9-5 09:02
oniste1,感觉只用parent指针就可以了。 跟left right 没啥关系啊

是啊，所以我说类似两个链表找 intersection，一路往上就行了。对于两个 node 之间路线上的交叉点，位置上说是这两个 node 在树上的 LCA

mnmunknown 发表于 2016-9-5 09:06
是啊，所以我说类似两个链表找 intersection，一路往上就行了。对于两个 node 之间路线上的交叉点，位置 ...

大神，解释下店面part2呢？

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 的概率替换

mnmunknown 发表于 2016-9-4 18:39
过奖了，我还差得很远。。=。=

电面 part2 就是非常典型的蓄水池抽样啊，属于 online algorithm 的一 ...

赞! 能解释一下，“以均匀概率返回 array / stream of integer 中的最大值“的意思吗？，是要一边scan一边找最大值，然后返回最大值的index？ 譬如 2 1 3 4 5 ，这就应该返回 0， 0， 2，3，4这样？