一亩三分地论坛

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

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

[编程题] 请教Snapchat 雷达 这道题

[复制链接] |试试Instant~ |关注本帖
神罗天征 发表于 2016-9-15 15:27:59 | 显示全部楼层 |阅读模式

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

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

x
各位大神,看Snapchat的面经,有一道题不太会,不知道各位大神有什么想法
一个tunnel, 范围是[0,1]中间有各种尺寸的雷达,(x, y, r),一个小车只有不被雷达监测的地方可以通过,问给定一个List<Radar>判断小车能不能过去


http://www.1point3acres.com/bbs/ ... adio%26sortid%3D311

看这个帖子的楼主是用union find, 但是不知道怎么用的,我的想法还是最原始的,把在雷达范围内的点全部标记,然后从最左边的一列找路径到最右边的一列,大家有没有其他方法呀
hxtang 发表于 2016-9-15 20:11:17 | 显示全部楼层
如果两个圆有overlap就认为联通。如果y=0, y=1和某个圆相交也认为它们联通。
然后就是看y=0, y=1是否在一个connected component里了。如果是的就认为路被block了。
回复 支持 1 反对 0

使用道具 举报

alucardzhou 发表于 2016-9-15 22:47:09 | 显示全部楼层
每两个圆心之间求距离,如果距离大于两个半径之和再加一(车的路径)。既可以通过。
小于的话立即返回false。
回复 支持 反对

使用道具 举报

 楼主| 神罗天征 发表于 2016-9-16 00:19:42 | 显示全部楼层
alucardzhou 发表于 2016-9-15 22:47
每两个圆心之间求距离,如果距离大于两个半径之和再加一(车的路径)。既可以通过。
小于的话立即返回fals ...

这个好像不对吧,假设有一个圆覆盖了路径,但是这个时候也存在一个圆,使他们的距离大于两个半径之和再加上一吧
回复 支持 反对

使用道具 举报

 楼主| 神罗天征 发表于 2016-9-16 00:46:59 | 显示全部楼层
hxtang 发表于 2016-9-15 20:11
如果两个圆有overlap就认为联通。如果y=0, y=1和某个圆相交也认为它们联通。
然后就是看y=0, y=1是否在一 ...

哦哦,这样,那最后判断是否在一个connected component里面的时候,需要记录每个connected component的x,y的范围吧
回复 支持 反对

使用道具 举报

hxtang 发表于 2016-9-16 00:55:44 | 显示全部楼层
神罗天征 发表于 2016-9-16 00:46
哦哦,这样,那最后判断是否在一个connected component里面的时候,需要记录每个connected component的x ...

这个有多种可能实现,纪录x, y是其中一种
回复 支持 反对

使用道具 举报

alucardzhou 发表于 2016-9-16 02:05:29 | 显示全部楼层
神罗天征 发表于 2016-9-15 11:19
这个好像不对吧,假设有一个圆覆盖了路径,但是这个时候也存在一个圆,使他们的距离大于两个半径之和再加 ...

不好意思之前没理解题意,通路原来是指定了的啊。我还以为可以随便开。
回复 支持 反对

使用道具 举报

MulinZz 发表于 2016-9-16 03:30:23 | 显示全部楼层
Snapchat为什么拒我简历,我心里不平衡
回复 支持 反对

使用道具 举报

 楼主| 神罗天征 发表于 2016-9-16 03:33:10 | 显示全部楼层
MulinZz 发表于 2016-9-16 03:30
Snapchat为什么拒我简历,我心里不平衡

估计是要上市了,人太多了……好像在招有flag实习的人……
回复 支持 反对

使用道具 举报

singku 发表于 2016-10-17 14:28:26 | 显示全部楼层
这道题可以这么做:先把所有的雷达处理一遍,把相交的雷达座位一个connected component, 处理完毕后,就会有很多雷达团体,然后判断每个雷达团体的探测最高和最低是否完全跨越了0到1的高度,这些雷达团体的探测范围实际上就是一堆相交的圆,如果这些圆的范围跨越了0->1,那么肯定可以通过圆的内部画一条线出来,挡住0-1,这样就过不去了。只要有一个雷达团体挡住了0-1 那小车就过不去。至于最高和最低 循环处理雷达团体,记录最高和最低值。
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-6 04:36

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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