📣 黑五价提前开抢|VIP一年通行证5折,蓝莓、Offer多多同步特惠
回复: 9
跳转到指定楼层
上一主题 下一主题
收起左侧

求大神讲解fb一道面经题

全局:

2017(4-6月) 码农类General 博士 其他@meta - Other - 其他  | | Other | 其他

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

您需要 登录 才可以下载或查看附件。没有帐号?注册账号

x
几何算法问题。如果给你一堆的矩形, 求重合矩形重合最多的坐标位置。我上过一个算法课,大概思路就是做一个二维的meeting room
您好!
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式
游客,您好!
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Popular Interview Questions from Top Companies
eer.blogspot.com/2011/12/no-27-area-of-rectangles.html


上一篇:发一个电面攒人品
下一篇:微软中国小冰暑期实习

本帖被以下淘专辑推荐:

推荐
 楼主| xiaobai123 2017-4-26 16:51:52 | 只看该作者
全局:
您好!
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式
游客,您好!
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Popular Interview Questions from Top Companies

评分

参与人数 1大米 +3 收起 理由
FightOn + 3 感谢分享!

查看全部评分

回复

使用道具 举报

🔗
xiaoquexing 2017-4-25 23:11:19 | 只看该作者
全局:
比如所有的矩形按左上和右下坐标给出,(x1, y1), (x2, y2)
先按所有的x1,x2把矩形分为2*n-1个区间,然后在每一个区间做meeting room
回复

使用道具 举报

🔗
LeetCodeOJ 2017-4-26 17:34:04 | 只看该作者
全局:
这道题真的出来了
回复

使用道具 举报

🔗
xiaoquexing 2017-4-26 23:10:42 | 只看该作者
全局:
xiaobai123 发表于 2017-4-26 16:51
想多问一点细节,关于这道题希望求的是什么矩形集合
比如我们现在有如下的一系列矩形

给n个矩形,求被最多个数的矩形覆盖的点 (如果有很多点,结果返回任意一点都可以)
回复

使用道具 举报

🔗
stealop 2017-4-27 04:26:20 | 只看该作者
全局:
您好!
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式
游客,您好!
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Popular Interview Questions from Top Companies
回复

使用道具 举报

🔗
zyq121 2017-4-28 01:26:06 | 只看该作者
全局:
所有矩阵顶点x轴坐标排序,如果是左上坐标加一,是右下坐标减一,找最大值即可找到最多x边重合区域。同理y轴。即可找到重合区域。

补充内容 (2017-4-28 03:18):
找最大值不对。应该是keep 所有两点间间距。
回复

使用道具 举报

🔗
edyyy 2017-4-29 01:44:34 | 只看该作者
全局:
这题到底怎么做?
回复

使用道具 举报

🔗
FightOn 2017-5-28 09:00:08 | 只看该作者
全局:
LeetCodeOJ 发表于 2017-4-26 17:34
这道题真的出来了

你见过这个题?方便讲一下么?看了这么多帖子还是不很懂
回复

使用道具 举报

🔗
aunom 2018-3-13 16:13:55 | 只看该作者
全局:
XY 轴都离散化处理
然后X轴先排序
然后在X轴进行扫描线,在Y轴,对每一个新增的矩形,add(y_top, 1), add(y_bottom, -1),求[y_low, y_max] 最值。对每一个减少矩形的操作,add(y_top, -1), add(y_bottom, 1)。

总计时间复杂度 O(nlgn)
回复

使用道具 举报

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

本版积分规则

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