我应该回答这个谷歌面试？

what should answer to this google-interview?

什么是选择在流的随机值的最有效方法是什么？由于他们每个人都有发生同样的机会。

What is the most efficient way to choose a random value in a stream? Given that each of them has a chance of occurring equally.

感谢。

推荐答案

有没有他们正在寻找具体的答案。他们要求你提出正确的问题，看看你是否能推理的问题。问的答案是你可以做明白这样一个问题最糟糕的事情。

There's no specific answer they're looking for. They're asking for you to ask the right questions and to see if you can reason about the problem. Asking for the answer is the worst possible thing you could do to understand a question like this.

有一个很好的答案可能开始是这样的：？？？我们是否知道有多少项目是在流中，我们能指望的项目，而不完全看他们，我们可以倒带流，我们是否可以假设I / O是昂贵得多比什么都重要，并最大限度地降低I / O是我们首要的设计考虑？...

A good answer might start like this: "Do we know how many items are in the stream? Can we count the items without fully reading them in? Can we rewind the stream? Can we assume I/O is much more expensive than anything else and minimizing I/O is our primary design consideration? ..."

他们也可能想看看，如果你知道的1 / N的算法。您可以使用下面的算法风与随机对象，权重相等，从物体流的：

They may also be looking to see if you know the 1/n algorithm. You can wind up with a random object, equally weighted, from a stream of objects by using the following algorithm:

在第一个对象流通过，拿着它。

When the first object streams through, hold it.

在 N '个对象流过，换你持有它的概率为对象 1 / N 。

When the n'th object streams through, swap the object you are holding for it with probability 1/n.

在过去的对象流过，你会举办一个随机选择的对象从所有对象具有同等可能流。

After the last object streams through, you will hold a randomly-selected object from the stream with all objects being equally likely.

如果您没有看到这是为什么，认为它通过。如果只有一个对象，我们认为在最后的对象。好吧，这是正确的。如果有两个对象，我们同样可能持有任一对象，因为我们换用概率1/2。如果有三个对象，我们认为概率1/3的第三个对象（因为这是最后一步），我们只是证明了我们同样可能会持有另外两个对象，所以他们都必须是1/​​3。等等。

If you don't see why this is, think it through. If there's only one object, we hold that object at the end. Okay, that's correct. If there are two objects, we are equally likely to hold either object because we swap with probability 1/2. If there are three objects, we hold the third object with probability 1/3 (because that's the last step), and we just proved we are equally likely to be holding the other two objects, so they must each be 1/3. And so on.

如果您preFER纯数学，你可以通过归纳证明的产品 N / N + 1 为 N 的推移，从 1 到 P 是 1 /（P + 1）。

If you prefer pure math, you can prove by induction that the product of n/n+1 as n goes from 1 to p is 1/(p+1).