美国华人网FuninUSA_唐人社区_北美华人论坛:找礼品卡,找折扣,找报价,找工作,找内推,找项目,找股票

 找回密码
 立即注册

点击进入授权页面

只需一步,快速开始

  • 男子吃感冒药开车追尾 交警:处罚参考毒驾
  • 日媒:30年来骤降四成 长颈鹿被列为“易危”物种
  • 韩国总统弹劾日:成则致朴槿惠停职 败则致政局陷混乱
  • 16岁少女发狠节食减肥 一个月暴瘦18斤后贫血而死
  • 你不懂的吃素学问:原来吃素有这么多种
  • 英国22岁女子骑瘦马 一周骑2次压伤马脊椎
  • 战斗民族的日常!零下53度学生照常上课
  • 这组魔性图:单身狗看完瞬间受到一万点暴击
  • 走进价值1000亿英镑的保险库:英国王子都服了
  • 韩演员朴信惠做慈善 支持大邱传统市场灾后重建
  • 11月美国大选後房贷利率飙升的现象不但未消失,而且持续攀高-美国房产信息
  • 美国总统特朗普上任後,美国在全球经济发展上将转向保护主义-美国房产信息
  • 12月市场基调是如何转变的
  • Rusty Braziel预测石油价格下跌
  • Cramer Remix:特朗普管理下的股票风险
  • 历史新高后,交易商把目光转向欧洲
Logo1-800-PetMeds Free Shipping $49Take $10 Off Your First Order w/code: SAVE10 - 234 x 60
ASICS AmericaPagoda Piercing Banner 234x60Sierra Trading Post
搜索
查看: 3016|回复: 9

内推面经 -这道linkedin题是不是应该用segment tree?- 唐人社区|北美华人论坛

[复制链接]
TA在交友中心
0 0 40
  @ME:   

19

主题

35

帖子

73

积分

新手上路

Rank: 1

积分
73
QQ
发表于 2016-11-5 03:10:17 | 显示全部楼层 |阅读模式
分享到:
{$content}

唐人社区-北美华人论坛-内推面经版-这道linkedin题是不是应该用segment tree?


  JobHunting
标 题: 这道linkedin题是不是应该用segment tree?


Decide whether a target is covered by a list of intervals
--

新浪微博官方账号】美国省钱快报FunInUSA : 每日滚动更新美国市场折扣资讯微商进货首选资讯渠道。
回复 百度谷歌雅虎搜狗搜搜有道360奇虎

举报

TA在交友中心
0 0 57
  @ME:   

24

主题

91

帖子

144

积分

注册会员

Rank: 2

积分
144
QQ
发表于 2016-11-5 03:59:12 | 显示全部楼层
JobHunting
标  题: 这道linkedin题是不是应该用segment tree?


Decide whether a target is covered by a list of intervals
--
TA在交友中心
0 0 50
  @ME:   

25

主题

89

帖子

139

积分

注册会员

Rank: 2

积分
139
QQ
发表于 2016-11-5 04:39:29 | 显示全部楼层
JobHunting
标  题: Re: 这道linkedin题是不是应该用segment tree?


segment tree的空间cost未必能太好

【 在 JavaDev (码神) 的大作中提到: 】
: 可以先merge,再看merged之后的区间没有包含给定的target区间,这样得花o(nlogn)
: 时间。
: 不过segment tree往往能给出最好的解法



--
TA在交友中心
0 0 45
  @ME:   

20

主题

79

帖子

121

积分

新手上路

Rank: 1

积分
121
QQ
发表于 2016-11-5 06:39:21 | 显示全部楼层
JobHunting
标  题: Re: 这道linkedin题是不是应该用segment tree?


Traveling intervals doesn't work?

【 在 JavaDev (码神) 的大作中提到: 】
:  Decide whether a target is covered by a list of intervals



--
Look. If you had one shot or one opportunity to seize everything you ever wanted in one moment.
Would you capture it or just let it slip?
TA在交友中心
0 0 51
  @ME:   

25

主题

95

帖子

141

积分

注册会员

Rank: 2

积分
141
QQ
发表于 2016-11-5 06:46:18 | 显示全部楼层
JobHunting
标  题: Re: 这道linkedin题是不是应该用segment tree?


leetcode常见题型的话
能用segment tree的题基本都有其他替代品
光说tree就有神马BIT tree啊啥的

但segment tree的确可以灵活解决不少问题
未必能提供面试时的最优solution
但能解决问题 complexity也不差


【 在 coldknight (冷骑士) 的大作中提到: 】
: 哦,target是个区间啊
: sort and merge. Then use binary search check. 其实time complexity 是一样的,
: space complexity还更好 O(n)。我总觉得segment tree 没什么用。有没有哪道题需要
: 用segment tree?
: A segment tree for a set I of n intervals uses O(n log n) storage and can
be
:  built in O(n log n) time



--
TA在交友中心
0 0 47
  @ME:   

19

主题

98

帖子

140

积分

注册会员

Rank: 2

积分
140
QQ
发表于 2016-11-5 06:58:53 | 显示全部楼层
JobHunting
标  题: Re: 这道linkedin题是不是应该用segment tree?


哦,target是个区间啊

sort and merge. Then use binary search check. 其实time complexity 是一样的,
space complexity还更好 O(n)。我总觉得segment tree 没什么用。有没有哪道题需要
用segment tree?

A segment tree for a set I of n intervals uses O(n log n) storage and can be
built in O(n log n) time



【 在 JavaDev (码神) 的大作中提到: 】
: 可以先merge,再看merged之后的区间没有包含给定的target区间,这样得花o(nlogn)
: 时间。
: 不过segment tree往往能给出最好的解法


--
Look. If you had one shot or one opportunity to seize everything you ever wanted in one moment.
Would you capture it or just let it slip?
TA在交友中心
0 0 42
  @ME:   

21

主题

90

帖子

123

积分

注册会员

Rank: 2

积分
123
QQ
发表于 2016-11-5 07:10:31 | 显示全部楼层
JobHunting
标  题: Re: 这道linkedin题是不是应该用segment tree?


interval tree?
--
TA在交友中心
0 0 52
  @ME:   

23

主题

82

帖子

130

积分

注册会员

Rank: 2

积分
130
QQ
发表于 2016-11-5 07:15:42 | 显示全部楼层
JobHunting
标  题: Re: 这道linkedin题是不是应该用segment tree?


还是用merge intervals
--
TA在交友中心
0 0 49
  @ME:   

23

主题

97

帖子

141

积分

注册会员

Rank: 2

积分
141
QQ
发表于 2016-11-5 07:33:50 | 显示全部楼层
JobHunting
标  题: Re: 这道linkedin题是不是应该用segment tree?


可以先merge,再看merged之后的区间没有包含给定的target区间,这样得花o(nlogn)
时间。
不过segment tree往往能给出最好的解法

【 在 coldknight (冷骑士) 的大作中提到: 】
: Traveling intervals doesn't work?



--
TA在交友中心
0 0 1007
  @ME:   

27

主题

1013

帖子

2020

积分

金牌会员

Rank: 6Rank: 6

积分
2020
QQ
发表于 2016-11-28 21:19:51 | 显示全部楼层
OMG!介是啥东东!!!
您需要登录后才可以回帖 登录 | 立即注册  

本版积分规则

玩美生活FunInUSA.net 华人娱乐论坛发布的内推面经 -这道linkedin题是不是应该用segment tree?- 唐人社区|北美华人论坛帖子由网友提供或转载于网络,若发布的内推面经 -这道linkedin题是不是应该用segment tree?- 唐人社区|北美华人论坛侵犯了您的权益,请联系我们.
1&1 Hosting

Copyright ©2011 FunInUSA.com All Right Reserved.  Powered by Discuz! X3.0 小黑屋

本站信息均由会员发表,不代表美国华人网FunInUSA立场,如侵犯了您的权利请发帖投诉  技术支持: 美国华人网FunInUSA

安全联盟认证 安全联盟认证

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