美国华人网FuninUSA|唐人社区|北美华人论坛:找好货,找礼品卡,找折扣,找工作,找内推,找项目,找股票

 找回密码
 立即注册
  • TNT确定《末日孤舰》第四季首播日期
  • 《权力的游戏》倒数第二季发布夜王动态海报
  • NBC取消《芝加哥正义》,全家桶第四子止步第一季
  • 2000年前首台天文计算机复原:精密度惊人
  • 科学家声称收到外星来电:宇宙中已走60亿光年
  • 蛟龙号从地球最深处带回“深海居民”:如外星怪物
  • 4分钟科普围棋规则:瞬间懂了
  • 大学生7楼钓外卖 宿管阿姨手书警告看哭
  • 飞机头突然断掉:其实 金属也会累
  • 谷歌自主处理器TPU太猛:AlphaGo只用一颗便完虐人类
  • 被美国收养的子女不能为亲属办绿卡
  • 多点开花 AMD快hold不住它的洪荒之力了
  • 6个月高位:强劲数据、强硬言论助力欧元
  • 黄金十字:逆势扭转,贵金属是要翻身了啊!
  • 化敌为友,诺基亚“牵手”苹果探索健康业务
  • 美元大跌——成也特朗普,败也特朗普
  • 小瞧高通! 你可就错了
  • 焦点:特朗普"2018预算案"周二首秀
  • IBM:这个蓝色巨人正在老去?
  • 警告:小心债券市场带来寒意
Logo1-800-PetMeds Free Shipping $49Take $10 Off Your First Order w/code: SAVE10 - 234 x 60
ASICS AmericaPagoda Piercing Banner 234x60Sierra Trading Post
搜索
查看: 3037|回复: 9

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

[复制链接]

20

主题

40

帖子

78

积分

新手上路

Rank: 1

积分
78
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
--
【思科/IBM/EMC/Juniper采购群】592532555
回复 百度谷歌雅虎搜狗搜搜有道360奇虎

举报

27

主题

101

帖子

163

积分

注册会员

Rank: 2

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


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

29

主题

102

帖子

158

积分

注册会员

Rank: 2

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


segment tree的空间cost未必能太好

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



--

24

主题

92

帖子

144

积分

新手上路

Rank: 1

积分
144
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?

26

主题

109

帖子

161

积分

注册会员

Rank: 2

积分
161
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



--

21

主题

110

帖子

160

积分

注册会员

Rank: 2

积分
160
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?

28

主题

104

帖子

160

积分

注册会员

Rank: 2

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


interval tree?
--

24

主题

88

帖子

140

积分

注册会员

Rank: 2

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


还是用merge intervals
--

24

主题

111

帖子

162

积分

注册会员

Rank: 2

积分
162
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?



--

30

主题

1131

帖子

2257

积分

金牌会员

Rank: 6Rank: 6

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

本版积分规则

美国华人网|唐人社区|什么值得买FunInUSA.net发布的内推面经 -这道linkedin题是不是应该用segment tree?- 唐人社区|北美华人论坛帖子由网友提供或转载于网络,若发布的内推面经 -这道linkedin题是不是应该用segment tree?- 唐人社区|北美华人论坛侵犯了您的权益,请联系我们.
Sasa.com

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

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

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

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