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

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

monte carlo

gaocan1992 发表于 2016-9-17 08:21
你好强，好多面筋我都没看过哎。你拿到了么

谬赞 只是一枚小**

pushazhiniao 发表于 2016-9-16 17:23
谬赞 只是一枚小**

感觉你们面的都是面筋，我的都不是。。。默默哭泣

gaocan1992 发表于 2016-9-17 11:15
感觉你们面的都是面筋，我的都不是。。。默默哭泣

我也不是啊 并且录不录跟是不是完全不成正比

pushazhiniao 发表于 2016-9-16 20:39
我也不是啊 并且录不录跟是不是完全不成正比

这是什么说法啊，求解释

gaocan1992 发表于 2016-9-17 15:08
这是什么说法啊，求解释

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

请教大神们，这样写对不对？

1. public class Solution {
   
2. 
   
3.         // Definition for an interval.
   
4.         class Interval {
   
5.                 int start;
   
6.                 int end;
   
7. 
   
8.                 Interval() {
   
9.                         start = 0;
   
10.                         end = 0;
    
11.                 }
    
12. 
    
13.                 Interval(int s, int e) {
    
14.                         start = s;
    
15.                         end = e;
    
16.                 }
    
17.         }
    
18. 
    
19.         public int rainDrop() {
    
20. 
    
21.                 List<Interval> q = new ArrayList<Interval>();
    
22.                 q.add(new Interval(0, 100));
    
23.                 int count = 0;
    
24.                 while (!q.isEmpty()) {
    
25.                         int size = q.size();
    
26.                         for (int i = 0; i < size; i++) {
    
27.                                 count++;
    
28.                                 Interval current = q.get(i);
    
29.                                 // Create random number 0 - 99
    
30.                                 Random random = new Random();
    
31.                                 // this point is always the left boundary of the rain drop, in
    
32.                                 // this case, we can make sure it only moves in right direction
    
33.                                 int raindrop = random.nextInt(100);
    
34.                                 // the rain drop is 1cm long
    
35.                                 int raindrop_start = raindrop, randrop_end = raindrop + 1;
    
36.                                 int left = current.start, right = current.end;
    
37.                                 if (raindrop_start > right || randrop_end < left) {
    
38.                                         continue;
    
39.                                 } else {
    
40.                                         q.remove(i);
    
41.                                         if (raindrop_start > left)
    
42.                                                 q.add(new Interval(left, raindrop_start - 1));
    
43.                                         if (randrop_end < right)
    
44.                                                 q.add(new Interval(randrop_end, right));
    
45.                                         break;
    
46.                                 }
    
47.                         }
    
48.                 }
    
49.                 return count;
    
50.         }
    
51. 
    
52.         public static void main(String[] args) {
    
53.                 Solution s = new Solution();
    
54.                 System.out.println(s.rainDrop());
    
55.         }
    
56. }

复制代码

ryancooper 发表于 2016-9-16 23:49
为什么要依赖面经，我觉得面经的作用是让你看看会出什么类型的问题而不是让你记住这道题的答案。只要掌握 ...

并没有依赖面筋，也没有背答案啊。但是既然有面筋，碰到了就更好啊

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滴雨。

stellari 发表于 2016-9-18 13:00
你可以这样考虑。用厘米作单位，路面的范围是[0 100]，那么雨点中心左标的可能范围是[-0.5, 100.5]。

...

分析的很棒！