sidewalk raindrop 问题

Rains on the sidewalk

一个sidewalk可以用[0, 1]的闭区间表示，一个raindrop可以用[a, a+0.01]的闭区间表示，其中a是随机在[0,1]中产生的数。写一段程序simulate雨点打湿sidewalk的过程，并返回整个sidewalk被打湿所需要的时间。自己设计sidewalk的class和raindrop的class并实现两个函数:(a) 随机产生新的雨点并根据雨点的位置更新sidewalk的状态.(2) 判断sidewalk是否被全部cover。两个函数都要求是O(1)

是把[0,1]的区间分成100个宽0.01的小格，每个小格维护两个状态，一个是从左边界算起被打湿的长度，一个是从右边界算起被打湿的长度。每次有新的雨点就更新与该雨点有overlap的两个小格的状态。如果某个小格两个长度加起来大于或等于0.01，则该小格已经被完全打湿。再维护一个counter，每次有新的小格被打完全打湿，counter加1。这样就可以O（1）复杂度实现更新小格状态和判断是否sidewalk完全被cover。

一亩三分地

 class SideWalk
 {

 public:
     void RandomRain()
     {
         float f = (float)rand() / INT_MAX;
         int b = (int)(f * 100) / 100;
         vs[b].first = max(vs[b].first, f - (float)b / 100);
         vs[b].second = max(vs[b].second, -f + (float)(b+1) / 100);
         if (vs[b].first + vs[b].second >= 1)wetcount++;
     }
     SideWalk()
     {
         vs = vector<pair<float, float>>(100);
     }
 private:
     vector < pair<float, float>> vs;
     int wetcount;
 };

OOP design： 设计一个Google Car 的Sensor SynchronizationSystem

从多个有着不同的CPU时钟的sensor读取message，并找到不同sensor的同步关系