FB面经悲惨被虐记

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 依次过来的，一开始也不知道整个数据流里到底哪个最大，也不知道数据流到底有多长，所以要实时维护 & 更新。

mnmunknown 发表于 2016-9-6 03:24
不是，[2,1,3,4,5] 里面是 1 的概率返回 index 4，对应数组里的最大值 5. 假如输入是 [1,2,3,6,1,6] 的话 ...

感觉好难啊。
input int[] nums, int k(target)
output int index;
如果 [1, 2, 3, 3, 3] K= 3
index 输出时候random 公式是个啥呢？
例如 3个 index 是 2, 3 , 4， 如果 这个 数组不是order 的， 3 的
[1, 3, 2, 3, 3] index 1, 3, 4 这个怎么random 出 1， 3， 4 根据 平均概率， 还有 target K 是下一个steam 传进的 值 要加上这个值，还是说它只是target

感觉WordBreak好高频啊，朋友这礼拜面G家onsite刚被问了。

想问问lz设计题是怎么答的？