近期论坛无法登录的解决方案


一亩三分地论坛

 找回密码
 获取更多干活,快来注册

一亩三分地官方iOS手机应用下载
查看: 4690|回复: 10
收起左侧

google 滴雨点问题

[复制链接] |试试Instant~ |关注本帖
bobzhang2004 发表于 2016-3-6 05:03:37 | 显示全部楼层 |阅读模式

2016(1-3月) 码农类 硕士 全职@Google - 内推 - HR筛选 |Other其他

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

您需要 登录 才可以下载或查看,没有帐号?获取更多干活,快来注册

x
google常考题,大家有思路吗?
you have 1 meter walkroad, and randomly generate rain, the rain is 1 cm. simulate how many rain drops to cover all the 1 meter [-0.01~1].


本帖被以下淘专辑推荐:

 楼主| bobzhang2004 发表于 2016-3-6 13:03:04 | 显示全部楼层
关注一亩三分地公众号:
Warald_一亩三分地
厉害的超人 发表于 2016-3-6 05:25
定义一个. 1point 3acres 璁哄潧
struct interv {. 鍥磋鎴戜滑@1point 3 acres
    double left=0, right=0.01;

谢谢,应该是对的,java 版本
  1. public class RainDrop {
  2.         static class Interval {.鐣欏璁哄潧-涓浜-涓夊垎鍦
  3.                 double left = 0, right = 0.01;

  4.                 boolean isWet() {. 鍥磋鎴戜滑@1point 3 acres
  5.                         return left >= right;
  6.                 }
  7.         }

  8.         public static void main(String[] args) {
  9.                 simulateRainDrop();
  10.         }
  11.        
  12.         public static void simulateRainDrop() {

  13.                 Interval[] sidewalk = new Interval[100];
  14.                 for (int i = 0; i < 100; i++) {
  15.                         sidewalk[i] = new Interval();
  16.                 }
  17.                 int cnt = 0, wetCnt = 0;
  18.                 while (wetCnt < 100) {.1point3acres缃
  19.                         ++cnt;.1point3acres缃
  20.                         double p = Math.random();
  21.                         double left = p - 0.005;
  22.                         double right = p + 0.005;
  23.                         if (left >= 0) {
  24.                                 int idx = (int) (left / 0.01);.1point3acres缃
  25.                                 if (!sidewalk[idx].isWet()) {
  26.                                         double iright = left - idx * 0.01;. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
  27.                                         if (iright < sidewalk[idx].right) {
  28.                                                 sidewalk[idx].right = iright;.鏈枃鍘熷垱鑷1point3acres璁哄潧
  29.                                                 if (sidewalk[idx].isWet()). 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
  30.                                                         ++wetCnt;
  31.                                         }
  32.                                 }
  33.                         }
  34.                         if (right <= 1) {
  35.                                 int idx = (int) (right / 0.01);
  36.                                 if (!sidewalk[idx].isWet()) {. from: 1point3acres.com/bbs
  37.                                         double ileft = right - idx * 0.01;. From 1point 3acres bbs
  38.                                         if (ileft > sidewalk[idx].left) {
  39.                                                 sidewalk[idx].left = ileft;
  40.                                                 if (sidewalk[idx].isWet())
  41.                                                         ++wetCnt;
  42.                                         }. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
  43.                                 }
  44.                         }
  45.                 }. 1point 3acres 璁哄潧
  46.                 System.out.println(cnt);
  47.         }
  48. }
复制代码
回复 支持 3 反对 0

使用道具 举报

厉害的超人 发表于 2016-3-6 05:25:09 | 显示全部楼层
关注一亩三分地微博:
Warald
定义一个 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
struct interv {
    double left=0, right=0.01;
    bool isWet() {
        return left>=right;
    }
};
就好了,然后生成0,1之间的一个均匀分布,模拟每个雨滴看落到哪个interval里,直
到100个都打湿。. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
vector<interv> sidewalk(100,interv());
int cnt=0, wetCnt=0, idx;
while(wetCnt<100) {
            ++cnt;
            double p= (double)(rand())/RAND_MAX;
            double left=p-0.005;
            double right=p+0.005;. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
            if(left>=0) {
                idx=left/0.01;
                if(!sidewalk[idx].isWet()) {
                    iright=left-idx*0.01;
                    if (iright<sidewalk[idx].right) {
                        sidewalk[idx].right=iright;
                        if(sidewalk[idx].wet()) ++wetCnt;
                    }
                }
            }
            if(right<=1) {
                idx=right/0.01;
                if(!sidewalk[idx].wet()) {
                    ileft=right-idx*0.01;. Waral 鍗氬鏈夋洿澶氭枃绔,
                    if (ileft>sidewalk[idx].left) {
                        sidewalk[idx].left=ileft;. from: 1point3acres.com/bbs
                        if(sidewalk[idx].isWet()) ++wetCnt;
                    }
                }
            }. from: 1point3acres.com/bbs
        }

评分

1

查看全部评分

回复 支持 反对

使用道具 举报

haifengc 发表于 2016-3-6 08:41:57 | 显示全部楼层
用merge intervals. more info on 1point3acres.com
回复 支持 反对

使用道具 举报

 楼主| bobzhang2004 发表于 2016-3-6 12:51:13 | 显示全部楼层
haifengc 发表于 2016-3-6 08:41.鐣欏璁哄潧-涓浜-涓夊垎鍦
用merge intervals

大神可以具体说说嘛?
回复 支持 反对

使用道具 举报

wangmengcathy 发表于 2016-3-7 12:25:41 | 显示全部楼层
当年就跪在了这道题上。。。
回复 支持 反对

使用道具 举报

wtcupup 发表于 2016-9-19 12:26:13 | 显示全部楼层
厉害的超人 发表于 2016-3-6 05:25
定义一个. 鍥磋鎴戜滑@1point 3 acres
struct interv {. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
    double left=0, right=0.01;

能解释下 interv 为啥left=0.0,and right=0.01,这里的left and right的意义是什么? 为啥left>=right就是湿了?
回复 支持 反对

使用道具 举报

Sayings 发表于 2016-9-19 15:14:50 | 显示全部楼层
wtcupup 发表于 2016-9-19 12:26
能解释下 interv 为啥left=0.0,and right=0.01,这里的left and right的意义是什么? 为啥left>=right就 ...

因为把1m的区间分为100个1cm的区间, 然而每个雨滴的宽度1cm是不能忽略的  雨滴可能drop在两个区间之间。  left right 代表每个区间的左右两部分。

假设random出来的值是 0.01 就表示宽度1cm的雨滴的正中心落在0.01 这个第0区间和第1区间的分界线上  于是就是 落在0区间右边0.005,1区间左边0.005。
回复 支持 反对

使用道具 举报

wtcupup 发表于 2016-9-19 15:42:24 | 显示全部楼层
Sayings 发表于 2016-9-19 15:14
因为把1m的区间分为100个1cm的区间, 然而每个雨滴的宽度1cm是不能忽略的  雨滴可能drop在两个区间之间。 ...

bool isWet() {
        return left>=right;
    }

那为啥区间的左边界比右边界大就是湿了呢?
回复 支持 反对

使用道具 举报

Sayings 发表于 2016-9-19 16:17:49 | 显示全部楼层
wtcupup 发表于 2016-9-19 15:42
bool isWet() {
        return left>=right;
    }

左边大于等于右边就是填满那个interval的0-0.01的意思。
.1point3acres缃
还是接着刚刚的例子 现在intervals[1].left 是 0.005 然后另一个random雨滴假设滴在0.021处 0.019-0.005 = 0.016.
所以对于interval 1,  iright = 0.016 - 0.01 = 0.06 然后 intervals[1].right = 0.01 - 0.06(表示1区间右边分被填充了0.06) 这时 left==0.05>right==0.04 代表1区间湿完了。

补充内容 (2016-9-19 16:20):
sorry 0.016 - 0.01 = 0.006   left == 0.005>right == 0.004

补充内容 (2016-9-19 16:39):
脑子不好。。。。是滴在0.019处 0.019-0.005 = 0.014 然后 0.014 - 0.01 = 0.04  interval.right = 0.04  
回复 支持 反对

使用道具 举报

regist1234 发表于 2016-9-27 14:39:51 | 显示全部楼层
我的想法:

class Centimeter{. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
  double left;
  double right;
}
有个数组Centimeter[] arr = new Centimeter[100];.鏈枃鍘熷垱鑷1point3acres璁哄潧
然后有个从0开始的counter,记录有多少个Centimeter被完整地覆盖了
每drop一个雨滴,检查受影响的1或2个Centimeter是否由未完整覆盖变为了完整覆盖。如果是,则counter++
当counter变成100时,simulation ends. From 1point 3acres bbs
回复 支持 反对

使用道具 举报

本版积分规则

关闭

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

手机版|小黑屋|一亩三分地论坛声明

custom counter

GMT+8, 2017-6-27 15:32

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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