1/31 Google oniste

雨点这道题，如果雨点的宽度是固定值的话，那根本就不需要merge interval吧？把一个数组填满不就解决了？

补充内容 (2017-2-7 12:55):
int[] road = new int[100];
                Random rand = new Random();
                int wet = 0, drops = 0;
                while(wet < 100){
                        int drop = rand.nextInt(100);
                        if(road[drop] == 0) wet++;
                        road[drop]++;
                        drops++;
                }

csy921125 发表于 2017-2-6 02:50
楼主你好，请问第四轮你是存的timestamp 为key, station发送次数为value, 还是3个station name为key, value ...

我自己想的key为timestamp, value是一个set<String>存timestamp的名字，优化的话就是有些timestamp永远都不会report, 把不会report的删除掉

月下一只喵 发表于 2017-2-6 09:44
求问第一题之前讨论的地方在哪呢？能否发个链接。
第三题每条路径能否能走重复的地方呢？

你的楼下描述的挺好的~

notturno 发表于 2017-2-6 13:40
第一轮好像是很早很早的面经里出现的
好像是这样：
sidewalk是一个大区间，比如[0,100]

不一样的思路，挺好的

notturno 发表于 2017-2-6 13:43
问下设计题能不能具体说清楚一点点，谢谢了

timestamp是一个时间点还是区间？event发送到接受是不是有时 ...

是一个时间点。没有时间间隔，event发送只是一个形式，重点不在这里

notturno 发表于 2017-2-6 13:46
DFS一般就是指数，指数的大小一般就是走的length步数。总体上的时间一般按照指数估量。
但实际上，算法里 ...

谢谢，受教

notturno 发表于 2017-2-6 13:46
DFS一般就是指数，指数的大小一般就是走的length步数。总体上的时间一般按照指数估量。
但实际上，算法里 ...

如果设一个visited矩阵的话，是不是就是O(n)?

补充内容 (2017-2-7 13:27):
如果不可以重复走的话

cgxy1991 发表于 2017-2-7 12:00
第三题复杂度感觉是3^n,因为除了第一圈能走8个位置，后面每个格子只能走3个位置(假设不能倒退，如果能倒退 ...

不能走走过的地方，那复杂度是不是会降到O(N)?

SuperMe 发表于 2017-2-7 13:28
不能走走过的地方，那复杂度是不是会降到O(N)?

不能，因为对每一个点来说，都有m个方向可以走。所以复杂度只能是O(m^n), m是可以走的方向，n是步长

补充内容 (2017-2-7 13:36):
可以想象成一个n-ary tree

cgxy1991 发表于 2017-2-7 12:25
雨点这道题，如果雨点的宽度是固定值的话，那根本就不需要merge interval吧？把一个数组填满不就解决了？

...

没太懂你的意思，如果这个drop 和其他已经打湿的interval有重合呢？