google电面

最初的梦想2013 发表于 2013-8-17 03:02
我觉得楼主的方法是对的，但好像解释不通，无法证明是等概率的。
有谁能证明下啊？

楼主，sorry,我开始没看清楚你的回答，你是说每次投2次啊，我理解为了1次，
那这个对了，那跟我刚才想到的一样，这样对了。

最初的梦想2013 发表于 2013-8-16 13:02
我觉得楼主的方法是对的，但好像解释不通，无法证明是等概率的。
有谁能证明下啊？

你的方法是我最初的方法，然后那个面试官说是不是可以这样改进一下

xiaoma318 发表于 2013-8-17 05:54
你的方法是我最初的方法，然后那个面试官说是不是可以这样改进一下

按你的做法，0,0,1所对应的电影1概率是1/4+1/4*1/2=3/8；电影2,3分别都是2/8;作废的概率是1/8；你还是认为这个方法是等概率的？

楼主觉得我说的对么？

struct result
{
   int  r1, int r2;
}
void throwit(result & r)

int choice()
{
    result r;
    do {
         throwit(r);
         if(r.r1 == 0 && r.r2 == 0) { continue; }
         if(r.r1 ==0 && r.r2 == 1) { return 1; }
         if(r.r1 == 1 && r.r2 == 0) { return 2; }
         return 3;
    } while (true);
   return 0; /* something wrong */
}

谢谢分享！

PS:第二题楼主最开始的方法是对的

xiaoma318 发表于 2013-8-17 00:11
actually my way is to throw another twice, the way is hint by the interviewer, tell me why it's wr ...

I think you were right. throw twice is correct.
first round, we throw twice, get (0,1.2,3), all with probability 1/4.
If we hit 0, throw twice again, also get (0,1.2,3), each with probability 1/4 * 1/4

Assume we hit 0 infinite times, then probability of it is 1/4 * 1/4 * ... * 1/4 = 0
probability of hitting 1,2,3 are equally (1/4 + (1/4)^2 (1/4)^2 ... + (1/4)^n)= 1/3

So they have equal probability, and you were right.

我觉得你一开始的方法是对的。扔两次得到0的话，重新扔两次，以此反复。这个肯定是等概率的。
改进的方法说的是先扔两次，看看情况。如果是1-3，就得到结果。如果是0，就再扔一次。这时候重新定义映射。只有0或者7需要重新扔。显然这时候不会再得到7。实际上就是得到0的话重新再扔，得到1的话就对于某一种结果。
如果改进的方法我没理解错lz意思，lz没理解错interviewer意。那这个方法是不对的。要么一开始就用扔三次的结果。不可以扔完两次后又改变映射，第三次扔硬币显然已经不是等概率了。上面大家也都分析过了。