楼主: wisdompeak2
跳转到指定楼层
上一主题 下一主题
收起左侧

发个十月初的狗家面经

🔗
htfy96 2019-1-3 16:05:55 | 只看该作者
全局:
最后一题复杂度是O(N^4logN)?交点个数是O(N^2),遍历交点对就是O(N^4),然后检查的时候在intervals中检查是否存在一条线段是O(logn)?

其实感觉更优解是扫描线?

枚举两个X值,维护出覆盖这个X范围的所有水平线段(sort by Y),同时已知X1, X2两边的垂直线段列表(sort by Y),然后就可以在Y轴上跑扫描线了: X1轴上的垂直interval进入/离开事件; X2轴上的垂直interval进入/离开事件; 水平线段的Y进入/离开事件:维护一个<=当前Y,且和左右两边Y=curY的垂直线段都相接的水平线段Y哈希表,每次加入的时候就+= find(curY + deltaX) + find(curY - deltaX),最后/=2。这个应该是O(N^3)的?
回复

使用道具 举报

🔗
 楼主| wisdompeak2 2019-1-3 16:16:46 | 只看该作者
全局:
htfy96 发表于 2019-1-3 16:05
最后一题复杂度是O(N^4logN)?交点个数是O(N^2),遍历交点对就是O(N^4),然后检查的时候在intervals中检查 ...

假设有M条线,求出所有的交点的时间O(M^2)。
假设得到N个交点,遍历所有的交点对的时间O(N^2)。
M和N二者并没有直接的关系。
我的前三步都是预处理,其实不影响整体的时间复杂度。(当然,第三步用的确实是扫描线法)
所以,真正的时间复杂度大概是O(N^2*4logK), K是平均每个X/Y刻度对应的interval的个数。
回复

使用道具 举报

🔗
htfy96 2019-1-3 16:20:37 | 只看该作者
全局:
wisdompeak2 发表于 2019-1-3 16:16
假设有M条线,求出所有的交点的时间O(M^2)。
假设得到N个交点,遍历所有的交点对的时间O(N^2)。
M和N二 ...

worst case (网格) N就是O(M^2)吧
回复

使用道具 举报

🔗
get_bits 2019-1-4 01:26:26 | 只看该作者
全局:
Mark一下 谢谢楼主!
回复

使用道具 举报

全局:
我有点好奇第二轮的第二题。我第一反应是O(logn),但是试着证了一下觉得不好证。然后搜了一下发现居然是1982年的一篇PaperThe average height of binary trees and other simple trees,而且结论居然是O(sqrt(n))。

是我理解错你题目的意思了么?

P.S. 如果说是BST的average height的话,我知道算法导论上有证明average heights是O(logn),但是第一这个证明也不容易(要先定义exponential heights这一条感觉就不容易想到,除非见过证明),第二这不等价于任意N个节点组成的二叉树高度的期望,因为分布不一样。
回复

使用道具 举报

🔗
 楼主| wisdompeak2 2019-1-4 10:25:12 | 只看该作者
全局:
tsl665 发表于 2019-1-4 10:09
我有点好奇第二轮的第二题。我第一反应是O(logn),但是试着证了一下觉得不好证。然后搜了一下发现居然是198 ...

不需要证明或计算,写出递归关系,让计算机去跑就行了。
回复

使用道具 举报

全局:
wisdompeak2 发表于 2019-1-4 10:25
不需要证明或计算,写出递归关系,让计算机去跑就行了。

噗,是这个意思。。你说没写代码我以为是证明题。。

另外最后一题感觉可以用线段树做
回复

使用道具 举报

🔗
 楼主| wisdompeak2 2019-1-4 10:32:53 | 只看该作者
全局:
htfy96 发表于 2019-1-3 16:20
worst case (网格) N就是O(M^2)吧

两种方法时间复杂度在一般情况下,其实不太好直接比较。
不过你的想法挺有意思,是可行的,效率应该也很高。
回复

使用道具 举报

🔗
Scala688 2019-1-4 10:36:51 | 只看该作者
本楼:
全局:
恭喜楼主
回复

使用道具 举报

🔗
sunifonly 2019-1-4 10:51:43 | 只看该作者
全局:
请问 第三轮里提到的“字符串转换,超高频面经”是哪一道呢?谢谢!
回复

使用道具 举报

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

本版积分规则

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