一亩三分地论坛

 找回密码
 获取更多干货,去instant注册!

扫码关注一亩三分地公众号
查看: 1503|回复: 19
收起左侧

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

[复制链接] |试试Instant~ |关注本帖
WhatsFLAG 发表于 2016-9-17 02:22:18 | 显示全部楼层 |阅读模式

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看,没有帐号?获取更多干货,去instant注册!

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

有没有什么好的解法呢?

评分

1

查看全部评分

stellari 发表于 2016-9-18 13:00:38 | 显示全部楼层
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滴雨。

回复 支持 2 反对 0

使用道具 举报

Henry要工作 发表于 2016-9-17 02:46:19 | 显示全部楼层
可以用map吗。。
1 m = 100 cm  用map记录每一个水滴的位置作为key, value随之递增。一直到map.size()>100?
不是很明确这个题目,是设计题目吗
回复 支持 1 反对 0

使用道具 举报

pushazhiniao 发表于 2016-9-17 03:38:35 | 显示全部楼层
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()
回复 支持 1 反对 0

使用道具 举报

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

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

使用道具 举报

ytsr 发表于 2016-9-17 03:35:17 | 显示全部楼层
得搞清楚模型,水滴下来是圆形的还是放心的,落点是离散的还是连续的,不同的设定差别太大了
回复 支持 反对

使用道具 举报

ytsr 发表于 2016-9-17 03:45:37 | 显示全部楼层
pushazhiniao 发表于 2016-9-17 03:38
import random
class Interval:
        def __init__(self):

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

使用道具 举报

 楼主| WhatsFLAG 发表于 2016-9-17 05:28:08 | 显示全部楼层
pushazhiniao 发表于 2016-9-17 03:38
import random
class Interval:
        def __init__(self):

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

使用道具 举报

Tonsha 发表于 2016-9-17 07:54:50 来自手机 | 显示全部楼层
跟merge interval有点像
回复 支持 反对

使用道具 举报

shuiguo 发表于 2016-9-17 08:12:36 | 显示全部楼层
对呀,请问这题具体是什么呢?
回复 支持 反对

使用道具 举报

gaocan1992 发表于 2016-9-17 08:21:26 | 显示全部楼层
pushazhiniao 发表于 2016-9-16 11:38
import random
class Interval:
        def __init__(self):

你好强,好多面筋我都没看过哎。你拿到了么
回复 支持 反对

使用道具 举报

pushazhiniao 发表于 2016-9-17 09:20:07 | 显示全部楼层
WhatsFLAG 发表于 2016-9-17 05:28
感谢您的细心回答,现在根据您给出的答案,大致判断是一个模拟随机的过程,我做题一般有个“陋习”就是稍 ...

monte carlo
回复 支持 反对

使用道具 举报

pushazhiniao 发表于 2016-9-17 09:23:46 | 显示全部楼层
gaocan1992 发表于 2016-9-17 08:21
你好强,好多面筋我都没看过哎。你拿到了么

谬赞 只是一枚小**
回复 支持 反对

使用道具 举报

gaocan1992 发表于 2016-9-17 11:15:08 | 显示全部楼层

感觉你们面的都是面筋,我的都不是。。。默默哭泣
回复 支持 反对

使用道具 举报

pushazhiniao 发表于 2016-9-17 12:39:53 | 显示全部楼层
gaocan1992 发表于 2016-9-17 11:15
感觉你们面的都是面筋,我的都不是。。。默默哭泣

我也不是啊 并且录不录跟是不是完全不成正比
回复 支持 反对

使用道具 举报

gaocan1992 发表于 2016-9-17 15:08:00 | 显示全部楼层
pushazhiniao 发表于 2016-9-16 20:39
我也不是啊 并且录不录跟是不是完全不成正比

这是什么说法啊,求解释
回复 支持 反对

使用道具 举报

ryancooper 发表于 2016-9-17 15:49:39 | 显示全部楼层
gaocan1992 发表于 2016-9-17 15:08
这是什么说法啊,求解释

为什么要依赖面经,我觉得面经的作用是让你看看会出什么类型的问题而不是让你记住这道题的答案。只要掌握好分析方法,题目你基本都能找到切入点。面试不只是看做不做得出,还看你是怎么分析问题的。
回复 支持 反对

使用道具 举报

wtcupup 发表于 2016-9-17 17:12:32 | 显示全部楼层
请教大神们,这样写对不对?
  1. public class Solution {

  2.         // Definition for an interval.
  3.         class Interval {
  4.                 int start;
  5.                 int end;

  6.                 Interval() {
  7.                         start = 0;
  8.                         end = 0;
  9.                 }

  10.                 Interval(int s, int e) {
  11.                         start = s;
  12.                         end = e;
  13.                 }
  14.         }

  15.         public int rainDrop() {

  16.                 List<Interval> q = new ArrayList<Interval>();
  17.                 q.add(new Interval(0, 100));
  18.                 int count = 0;
  19.                 while (!q.isEmpty()) {
  20.                         int size = q.size();
  21.                         for (int i = 0; i < size; i++) {
  22.                                 count++;
  23.                                 Interval current = q.get(i);
  24.                                 // Create random number 0 - 99
  25.                                 Random random = new Random();
  26.                                 // this point is always the left boundary of the rain drop, in
  27.                                 // this case, we can make sure it only moves in right direction
  28.                                 int raindrop = random.nextInt(100);
  29.                                 // the rain drop is 1cm long
  30.                                 int raindrop_start = raindrop, randrop_end = raindrop + 1;
  31.                                 int left = current.start, right = current.end;
  32.                                 if (raindrop_start > right || randrop_end < left) {
  33.                                         continue;
  34.                                 } else {
  35.                                         q.remove(i);
  36.                                         if (raindrop_start > left)
  37.                                                 q.add(new Interval(left, raindrop_start - 1));
  38.                                         if (randrop_end < right)
  39.                                                 q.add(new Interval(randrop_end, right));
  40.                                         break;
  41.                                 }
  42.                         }
  43.                 }
  44.                 return count;
  45.         }

  46.         public static void main(String[] args) {
  47.                 Solution s = new Solution();
  48.                 System.out.println(s.rainDrop());
  49.         }
  50. }
复制代码
回复 支持 反对

使用道具 举报

gaocan1992 发表于 2016-9-18 01:44:27 | 显示全部楼层
ryancooper 发表于 2016-9-16 23:49
为什么要依赖面经,我觉得面经的作用是让你看看会出什么类型的问题而不是让你记住这道题的答案。只要掌握 ...

并没有依赖面筋,也没有背答案啊。但是既然有面筋,碰到了就更好啊
回复 支持 反对

使用道具 举报

 楼主| WhatsFLAG 发表于 2016-9-20 02:56:24 | 显示全部楼层
stellari 发表于 2016-9-18 13:00
你可以这样考虑。用厘米作单位,路面的范围是[0 100],那么雨点中心左标的可能范围是[-0.5, 100.5]。

...

分析的很棒!
回复 支持 反对

使用道具 举报

本版积分规则

请点这里访问我们的新网站:一亩三分地Instant.

Instant搜索更强大,不扣积分,内容组织的更好更整洁!目前仍在beta版本,努力完善中!反馈请点这里

关闭

一亩三分地推荐上一条 /5 下一条

手机版|小黑屋|一亩三分地论坛声明 ( 沪ICP备11015994号 )

custom counter

GMT+8, 2016-12-4 14:26

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

快速回复 返回顶部 返回列表