一亩三分地论坛

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

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

[找工就业] 问一个FB的店面题-2维矩形最大重合问题

[复制链接] |试试Instant~ |关注本帖
huoshankou 发表于 2016-10-2 07:01:38 | 显示全部楼层 |阅读模式

2017(7-9月)-[12]EE博士+<3个月短暂实习/全职 - 校园招聘会| 码农类全职@Facebookfresh grad应届毕业生

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

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

x
是我之前面FB时遇到过的一个题,但是觉得好像没有得到满意的解答。 原题是给出一堆二维矩形,返回矩形重合最多的地方的坐标 (只需要返回一个就可以)。楼主的思路是拿扫描线段树扫描横边和竖边,但是不确定这样解对不对。大家有什么好的思路吗?


原贴在这. 1point 3acres 璁哄潧
http://www.1point3acres.com/bbs/thread-166129-1-1.html
iPhD 发表于 2016-10-2 07:09:13 | 显示全部楼层
一维的话应该就是类似find most overlapping point in an array of intervals, 二维不太会。。。

另外因为楼主是博士所以才会问这么难的题,bar也相对硕士较高吗?我感觉硕士面实习不太可能面这么难的呀。。。
回复 支持 反对

使用道具 举报

 楼主| huoshankou 发表于 2016-10-2 07:14:19 | 显示全部楼层
iPhD 发表于 2016-10-2 07:09
一维的话应该就是类似find most overlapping point in an array of intervals, 二维不太会。。。

另外因 ...

他先让我写了个一维的,就用扫描线做。二维我就说往两个方向进行扫描。一维的是bug free的,二维的我当时都不知道是不是答对了,他只是很勉强的说了OK。 可能因为面试官是个搞ACM竞赛的台湾帅哥。
回复 支持 反对

使用道具 举报

johnjavabean 发表于 2016-10-6 02:31:09 | 显示全部楼层
有点像meeting room 2二维的,求问楼主的扫描线怎么做
回复 支持 反对

使用道具 举报

pawprinter 发表于 2016-10-7 06:07:39 | 显示全部楼层
huoshankou 发表于 2016-10-2 07:14. more info on 1point3acres.com
他先让我写了个一维的,就用扫描线做。二维我就说往两个方向进行扫描。一维的是bug free的,二维的我当时 ...

请问这个题目是要返回一个二维坐标,使包含这个坐标的矩形的数目最多么?
回复 支持 反对

使用道具 举报

pawprinter 发表于 2016-10-8 01:41:19 | 显示全部楼层
想了一个解法
1. 根据矩形的left x坐标排序,维护一个优先队列,元素按照right x坐标排序。同事也需要一个map,用来mapping矩形和它对应的(top, bottom),也就是一个interval
2. 从左往右扫描,当遇到新矩形时,pop出已经结束的矩形,并且remove到map中对应的interval
3. 将新矩形插入pq,同时加入map
4. 对map中的interval做一个类似meeting room的算法,算出重合最大值的坐标
5. 如果已经扫描完,结束,否则重复2 ~ 4
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-7 20:59

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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