谷歌经典面试题 1cm水滴 1M范围 随机覆盖 直到全覆盖

求教这个题的具体细节是什么，要求模拟这个过程 或者 是用概率求期望值？

有没有什么好的解法呢？

WhatsFLAG 发表于 2016-9-17 05:28
感谢您的细心回答，现在根据您给出的答案，大致判断是一个模拟随机的过程，我做题一般有个“陋习”就是稍 ...

你可以这样考虑。用厘米作单位，路面的范围是[0 100]，那么雨点中心左标的可能范围是[-0.5, 100.5]。

那么第一滴雨的中心如果落在[0.5, 99.5]这个范围内，那么就会恰好覆盖长为1厘米的路面，这件事发生的概率是(99.5-0.5)/(100.5-(-0.5)) = 99/101。而如果落在其余范围内，覆盖的面积从0~1等概率均匀分布。这些事件加起来的总概率是1 - 99/101 = 2/101，。因此，第一滴雨落下后，覆盖面积的期望是99/101 X 1cm + 2/101 x 0.5 = 99/101 + 1/101 = 100/101。

反过来想，也就是说平均要下101/100滴雨，才能正好覆盖1cm的路面。

当恰好1cm的路面被覆盖以后，这时路面上有99cm未被覆盖。上面我们说了，100cm未被覆盖的情况下，有99/101的概率会覆盖1cm。那么99cm未覆盖的情况下，则有98/101的概率会覆盖1cm，剩下有2/101的情况依然是从覆盖0~1cm之间等概率分布，那么此时覆盖面积的期望是98/101 x 1cm + 2/101* 0.5 = 99/101.

换言之，从1cm覆盖到2cm覆盖这个过程，又平均需要101/99滴雨。

……

那么，从99cm覆盖到100cm覆盖，平均需要101滴雨。

因此，整个过程平均需要101/99+101/98+...101/2+101 = 524滴雨。

import random
class Interval:
        def __init__(self):
                self.left, self.right = 0, 0.01
        def isWet(self):
                return self.left >= self.right

def rainDropCover():
        sidewalk = [Interval() for i in range(100)]
        result, cover = 0, 0
        while cover < 100:
                center = random.random()
                left, right = center - 0.005, center + 0.005
                if left >= 0:
                        index = int(left / 0.01)
                        if not sidewalk[index].isWet():
                                sidewalk[index].right = min(sidewalk[index].right, left - index * 0.01)
                                if sidewalk[index].isWet():
                                        cover += 1
                if right < 1:
                        index = int(right / 0.01)
                        if not sidewalk[index].isWet():
                                sidewalk[index].left = max(sidewalk[index].left, right - index * 0.01)
                                if sidewalk[index].isWet():
                                        cover += 1
                result += 1
        return result

print rainDropCover()

可以用map吗。。
1 m = 100 cm  用map记录每一个水滴的位置作为key, value随之递增。一直到map.size()>100?
不是很明确这个题目，是设计题目吗

Henry要工作 发表于 2016-9-17 02:46
可以用map吗。。
1 m = 100 cm  用map记录每一个水滴的位置作为key, value随之递增。一直到map.size()>100 ...

我感觉是不行的，因为是随机上水，第一滴水可能滴在10厘米，第二滴可能滴在10.5厘米，这两滴会有所重叠，如果用map.size()可能会导致有失偏颇？
具体是什么题我也不清楚，都是在面经里看到的，连题意都还没太高明白……

得搞清楚模型，水滴下来是圆形的还是放心的，落点是离散的还是连续的，不同的设定差别太大了

pushazhiniao 发表于 2016-9-17 03:38
import random
class Interval:
        def __init__(self):

一维的就简单多了。不就是merge intervals么
看来我想复杂了。

pushazhiniao 发表于 2016-9-17 03:38
import random
class Interval:
        def __init__(self):

感谢您的细心回答，现在根据您给出的答案，大致判断是一个模拟随机的过程，我做题一般有个“陋习”就是稍微发散一下，假如这个题问概率上的期望，您认为有什么好的办法来做吗？

跟merge interval有点像

对呀，请问这题具体是什么呢？

pushazhiniao 发表于 2016-9-16 11:38
import random
class Interval:
        def __init__(self):

你好强，好多面筋我都没看过哎。你拿到了么