一亩三分地论坛

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

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

google 滴雨点问题

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

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

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

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

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 | 显示全部楼层
厉害的超人 发表于 2016-3-6 05:25
定义一个
struct interv {
    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() {
  5.                         return left >= right;
  6.                 }
  7.         }

  8.         public static void main(String[] args) {
  9.                 simulateRainDrop();
  10.         }
  11.         . 鍥磋鎴戜滑@1point 3 acres
  12.         public static void simulateRainDrop() {
  13. . 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
  14.                 Interval[] sidewalk = new Interval[100];. from: 1point3acres.com/bbs
  15.                 for (int i = 0; i < 100; i++) {
  16.                         sidewalk[i] = new Interval();
  17.                 }. 1point3acres.com/bbs
  18.                 int cnt = 0, wetCnt = 0;
  19.                 while (wetCnt < 100) {
  20.                         ++cnt;
  21.                         double p = Math.random();
  22.                         double left = p - 0.005;
  23.                         double right = p + 0.005;
  24.                         if (left >= 0) {
  25.                                 int idx = (int) (left / 0.01);
  26.                                 if (!sidewalk[idx].isWet()) { 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
  27.                                         double iright = left - idx * 0.01;. visit 1point3acres.com for more.
  28.                                         if (iright < sidewalk[idx].right) {
  29.                                                 sidewalk[idx].right = iright;
  30.                                                 if (sidewalk[idx].isWet())
  31.                                                         ++wetCnt;
  32.                                         }. visit 1point3acres.com for more.
  33.                                 }
  34.                         }
  35.                         if (right <= 1) {
  36.                                 int idx = (int) (right / 0.01);
  37.                                 if (!sidewalk[idx].isWet()) {. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
  38.                                         double ileft = right - idx * 0.01;
  39.                                         if (ileft > sidewalk[idx].left) {. Waral 鍗氬鏈夋洿澶氭枃绔,
  40.                                                 sidewalk[idx].left = ileft;
  41.                                                 if (sidewalk[idx].isWet())
  42.                                                         ++wetCnt;. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
  43.                                         }
  44.                                 }
  45.                         }. more info on 1point3acres.com
  46.                 }
  47.                 System.out.println(cnt);
  48.         }
  49. }
复制代码
回复 支持 3 反对 0

使用道具 举报

厉害的超人 发表于 2016-3-6 05:25:09 | 显示全部楼层
定义一个
struct interv {
    double left=0, right=0.01;
. more info on 1point3acres.com    bool isWet() {. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
        return left>=right;
    }
};-google 1point3acres
就好了,然后生成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;. Waral 鍗氬鏈夋洿澶氭枃绔,
            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;
                    if (ileft>sidewalk[idx].left) {
                        sidewalk[idx].left=ileft;
                        if(sidewalk[idx].isWet()) ++wetCnt;
                    }
                }
            }
        }

评分

1

查看全部评分

回复 支持 反对

使用道具 举报

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

使用道具 举报

 楼主| bobzhang2004 发表于 2016-3-6 12:51:13 | 显示全部楼层

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

使用道具 举报

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

使用道具 举报

wtcupup 发表于 2016-9-19 12:26:13 | 显示全部楼层
厉害的超人 发表于 2016-3-6 05:25
定义一个
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-google 1point3acres
能解释下 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-google 1point3acres
因为把1m的区间分为100个1cm的区间, 然而每个雨滴的宽度1cm是不能忽略的  雨滴可能drop在两个区间之间。 ...
. 鍥磋鎴戜滑@1point 3 acres
bool isWet() {
        return left>=right;
    }. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷

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

使用道具 举报

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

左边大于等于右边就是填满那个interval的0-0.01的意思。
-google 1point3acres
还是接着刚刚的例子 现在intervals[1].left 是 0.005 然后另一个random雨滴假设滴在0.021处 0.019-0.005 = 0.016.. from: 1point3acres.com/bbs
所以对于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区间湿完了。. 1point3acres.com/bbs

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

补充内容 (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];
然后有个从0开始的counter,记录有多少个Centimeter被完整地覆盖了. more info on 1point3acres.com
每drop一个雨滴,检查受影响的1或2个Centimeter是否由未完整覆盖变为了完整覆盖。如果是,则counter++
当counter变成100时,simulation ends.1point3acres缃
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-10 13:42

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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