當了一年的 Facebook Rotational Software Engineer 心得分享

一亩三分地论坛

 找回密码
 Sign Up 注册获取更多干货
E轮2.5亿美元融资
K12教育独角兽一起作业
北京-诚聘人工智能/教育/大数据岗
坐标湾区
Games Startup
招聘游戏开发工程师
游戏初创公司招聘工程师、UIUX Designer和游戏策划
码农求职神器Triplebyte:
不用海投
内推多家公司面试
把贵司招聘信息放这里
查看: 5013|回复: 6
收起左侧

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

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

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

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

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

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


原贴在这
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, 二维不太会。。。. from: 1point3acres

另外因 ...

他先让我写了个一维的,就用扫描线做。二维我就说往两个方向进行扫描。一维的是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
他先让我写了个一维的,就用扫描线做。二维我就说往两个方向进行扫描。一维的是bug free的,二维的我当时 ...

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

使用道具 举报

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

使用道具 举报

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

#rectangles is a list of [(x1, y1), (x2, y2)]
def getOverlap(s):
    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]
    return cnt, ans

def maxOverlap(rectangles):
    anscnt, ans = 0, []
. 围观我们@1point 3 acres    recs = []
. from: 1point3acres     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)):. Waral 博客有更多文章,
        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)
        if overlap[0] > anscnt:
            anscnt, ans = overlap[0], (recs[i][0], overlap[1])
        if recs[i][3] == -1:
            removeList.add(recs[i])
    return ans
回复 支持 反对

使用道具 举报

本版积分规则

提醒:发帖可以选择内容隐藏,部分板块支持匿名发帖。请认真读完以下全部说明:

■隐藏内容方法: [hide=200]你想要隐藏的内容比如面经[/hide]
■意思是:用户积分低于200则看不到被隐藏的内容
■可以自行设置积分值,不建议太高(200以上太多人看不到),也不建议太低(那就没必要隐藏了)
■建议只隐藏关键内容,比如具体的面试题目、涉及隐私的信息,大部分内容没必要隐藏。
■微信/QQ/电子邮件等,为防止将来被骚扰甚至人肉,以论坛私信方式发给对方最安全。
■匿名发帖的板块和方法:http://www.1point3acres.com/bbs/thread-405991-1-1.html

关闭

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

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

custom counter

GMT+8, 2018-5-21 02:16

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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