楼主: SuperMe
跳转到指定楼层
上一主题 下一主题
收起左侧

1/31 Google oniste

🔗
cgxy1991 2017-2-7 12:25:14 | 只看该作者
全局:
雨点这道题,如果雨点的宽度是固定值的话,那根本就不需要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++;
                }
回复

使用道具 举报

🔗
 楼主| SuperMe 2017-2-7 13:19:19 | 只看该作者
全局:
csy921125 发表于 2017-2-6 02:50
楼主你好,请问第四轮你是存的timestamp 为key, station发送次数为value, 还是3个station name为key, value ...

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

使用道具 举报

🔗
 楼主| SuperMe 2017-2-7 13:19:58 | 只看该作者
全局:
月下一只喵 发表于 2017-2-6 09:44
求问第一题之前讨论的地方在哪呢?能否发个链接。
第三题每条路径能否能走重复的地方呢?

你的楼下描述的挺好的~
回复

使用道具 举报

🔗
 楼主| SuperMe 2017-2-7 13:23:25 | 只看该作者
全局:
notturno 发表于 2017-2-6 13:40
第一轮好像是很早很早的面经里出现的
好像是这样:
sidewalk是一个大区间,比如[0,100]

不一样的思路,挺好的
回复

使用道具 举报

🔗
 楼主| SuperMe 2017-2-7 13:24:27 | 只看该作者
全局:
notturno 发表于 2017-2-6 13:43
问下设计题能不能具体说清楚一点点,谢谢了

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

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

使用道具 举报

🔗
 楼主| SuperMe 2017-2-7 13:24:53 | 只看该作者
全局:
notturno 发表于 2017-2-6 13:46
DFS一般就是指数,指数的大小一般就是走的length步数。总体上的时间一般按照指数估量。
但实际上,算法里 ...

谢谢,受教
回复

使用道具 举报

🔗
 楼主| SuperMe 2017-2-7 13:26:22 | 只看该作者
全局:
notturno 发表于 2017-2-6 13:46
DFS一般就是指数,指数的大小一般就是走的length步数。总体上的时间一般按照指数估量。
但实际上,算法里 ...

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

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

使用道具 举报

🔗
 楼主| SuperMe 2017-2-7 13:28:27 | 只看该作者
全局:
cgxy1991 发表于 2017-2-7 12:00
第三题复杂度感觉是3^n,因为除了第一圈能走8个位置,后面每个格子只能走3个位置(假设不能倒退,如果能倒退 ...

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

使用道具 举报

🔗
cgxy1991 2017-2-7 13:33:46 | 只看该作者
全局:
SuperMe 发表于 2017-2-7 13:28
不能走走过的地方,那复杂度是不是会降到O(N)?

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

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

使用道具 举报

🔗
 楼主| SuperMe 2017-2-7 13:37:39 | 只看该作者
全局:
cgxy1991 发表于 2017-2-7 12:25
雨点这道题,如果雨点的宽度是固定值的话,那根本就不需要merge interval吧?把一个数组填满不就解决了?

...

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

使用道具 举报

您需要登录后才可以回帖 登录 | 注册账号
隐私提醒:
  • ☑ 禁止发布广告,拉群,贴个人联系方式:找人请去🔗同学同事飞友,拉群请去🔗拉群结伴,广告请去🔗跳蚤市场,和 🔗租房广告|找室友
  • ☑ 论坛内容在发帖 30 分钟内可以编辑,过后则不能删帖。为防止被骚扰甚至人肉,不要公开留微信等联系方式,如有需求请以论坛私信方式发送。
  • ☑ 干货版块可免费使用 🔗超级匿名:面经(美国面经、中国面经、数科面经、PM面经),抖包袱(美国、中国)和录取汇报、定位选校版
  • ☑ 查阅全站 🔗各种匿名方法

本版积分规则

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