【通知】7月22,工业界资深数据科学家教你破解各大公司面试!


一亩三分地论坛

 找回密码
 获取更多干活,快来注册

一亩三分地官方iOS手机应用下载
查看: 4020|回复: 6
收起左侧

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

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

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

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

您需要 登录 才可以下载或查看,没有帐号?获取更多干活,快来注册

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


原贴在这
http://www.1point3acres.com/bbs/thread-166129-1-1.html
iPhD 发表于 2016-10-2 07:09:13 | 显示全部楼层
关注一亩三分地公众号:
Warald_一亩三分地
一维的话应该就是类似find most overlapping point in an array of intervals, 二维不太会。。。. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
. from: 1point3acres.com/bbs
另外因为楼主是博士所以才会问这么难的题,bar也相对硕士较高吗?我感觉硕士面实习不太可能面这么难的呀。。。
回复 支持 反对

使用道具 举报

 楼主| huoshankou 发表于 2016-10-2 07:14:19 | 显示全部楼层
关注一亩三分地微博:
Warald
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
. from: 1point3acres.com/bbs 他先让我写了个一维的,就用扫描线做。二维我就说往两个方向进行扫描。一维的是bug free的,二维的我当时 ...
. visit 1point3acres.com for more.
请问这个题目是要返回一个二维坐标,使包含这个坐标的矩形的数目最多么?
回复 支持 反对

使用道具 举报

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的算法,算出重合最大值的坐标.鏈枃鍘熷垱鑷1point3acres璁哄潧
5. 如果已经扫描完,结束,否则重复2 ~ 4
回复 支持 反对

使用道具 举报

WhatsFLAG 发表于 2016-12-28 12:36:08 | 显示全部楼层
试着写了一下,发现写的好繁琐,不知道楼主是怎么做的……

#rectangles is a list of [(x1, y1), (x2, y2)].鏈枃鍘熷垱鑷1point3acres璁哄潧
def getOverlap(s):. 1point 3acres 璁哄潧
    cnt, ans = 0, []
    interval = []
    for p in s:
        interval.append([p[1], 1])
        interval.append([p[2], -1])
    interval.sort()
    c = 0
    for inter in interval:
        if inter[1] == -1:
            c -= 1
        else:
            c += 1
        if c >= cnt:
            cnt, ans = c, inter[1]. visit 1point3acres.com for more.
    return cnt, ans

def maxOverlap(rectangles):. Waral 鍗氬鏈夋洿澶氭枃绔,
    anscnt, ans = 0, []
    recs = []
    for rec in rectangles:
        recs.append([rec[0] + [rec[1][1]] + [1]])
        recs.append([rec[1][0] + [rec[0][1] ]+ [rec[1][1]] + [-1]])
    recs.sort(). 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
    curInterval = set()
    removeList = set()
    for i in xrange(len(recs)):
        if i > 0 and recs[i][0] != recs[i - 1][0]:
            for r in removeList:
                curInterval.remove(r)
            removeList = set()
        curInterval.add(recs[i])
        overlap = getOverlap(curInterval)
. 1point3acres.com/bbs        if overlap[0] > anscnt:
            anscnt, ans = overlap[0], (recs[i][0], overlap[1])
        if recs[i][3] == -1:. 鍥磋鎴戜滑@1point 3 acres
            removeList.add(recs[i])
    return ans
回复 支持 反对

使用道具 举报

本版积分规则

关闭

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

手机版|小黑屋|一亩三分地论坛声明

custom counter

GMT+8, 2017-7-23 02:58

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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