一亩三分地论坛

 找回密码
 获取更多干货,去instant注册!

扫码关注一亩三分地公众号
查看: 1332|回复: 16
收起左侧

Twitter 店面

[复制链接] |试试Instant~ |关注本帖
jun2015 发表于 2015-11-1 04:43:29 | 显示全部楼层 |阅读模式

2015(10-12月) 码农类 博士 全职@Twitter - 网上海投 - 技术电面 |Passfresh grad应届毕业生

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

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

x

上来直接一道题:
. from: 1point3acres.com/bbs 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
给一组没有排序的interval [min, max], 让求其中最长的嵌套interval序列

举例:
输入
[-100, 100], [-101, 90], [1, 5], [-5, 10]

应该返回: [-100, 100], [-5, 10], [1, 5]



评分

2

查看全部评分

kakka 发表于 2015-11-1 06:21:40 | 显示全部楼层
请问是网投的吗?
回复 支持 反对

使用道具 举报

liyanjia92 发表于 2015-11-1 06:52:50 | 显示全部楼层
这不就是merge interval原题吗
回复 支持 反对

使用道具 举报

hyliu0000 发表于 2015-11-1 11:00:33 | 显示全部楼层
liyanjia92 发表于 2015-11-1 06:52
这不就是merge interval原题吗
. 1point 3acres 璁哄潧
感觉不太一样啊。 这个是完全嵌套,不是overlap
回复 支持 反对

使用道具 举报

hyliu0000 发表于 2015-11-1 11:03:02 | 显示全部楼层
楼主[-101, 90], [1, 5], [-5, 10] 这个是不是也是最长的?
回复 支持 反对

使用道具 举报

 楼主| jun2015 发表于 2015-11-1 12:06:14 | 显示全部楼层
hyliu0000 发表于 2015-11-1 11:03
楼主[-101, 90], [1, 5], [-5, 10] 这个是不是也是最长的?

是的,会有多个解,我就给了一个解
回复 支持 反对

使用道具 举报

 楼主| jun2015 发表于 2015-11-1 12:08:53 | 显示全部楼层
kakka 发表于 2015-11-1 06:21
请问是网投的吗?

是网投的
回复 支持 反对

使用道具 举报

CrossTheWall 发表于 2015-11-1 12:09:41 | 显示全部楼层
楼主,“最长序列” 是什么意思?是指value range最大的嵌套还是指序列的个数最多?
回复 支持 反对

使用道具 举报

 楼主| jun2015 发表于 2015-11-1 12:10:41 | 显示全部楼层
CrossTheWall 发表于 2015-11-1 12:09. more info on 1point3acres.com
楼主,“最长序列” 是什么意思?是指value range最大的嵌套还是指序列的个数最多?

嵌套深度最深
回复 支持 反对

使用道具 举报

pyemma 发表于 2015-11-1 12:23:52 | 显示全部楼层
感觉就是用DP吧,先把Array按照左端点sort一遍,然后从最后往前撸,dp[i]存储以i开始的最长嵌套距离。时间复杂度O(N^2).
回复 支持 反对

使用道具 举报

CrossTheWall 发表于 2015-11-1 12:56:31 | 显示全部楼层
pyemma 发表于 2015-11-1 12:23.鐣欏璁哄潧-涓浜-涓夊垎鍦
感觉就是用DP吧,先把Array按照左端点sort一遍,然后从最后往前撸,dp存储以i开始的最长嵌套距离。时间复杂 ...

这个题要把序列找出来,所以我觉得用DP反倒不如用类似深搜的方式来解决更好,因为搜索的过程中可以不断地动态剪枝
回复 支持 反对

使用道具 举报

CrossTheWall 发表于 2015-11-1 13:22:41 | 显示全部楼层
楼主, 我决定Twitter现在有种不缺人的感觉,你这电面题比我当年那个可是要难不少。

这题我的idea是:1. 根据左端排序 2. 对排好的序列,建立一个size相等的vector结构, 找到每个interval的孩子序列,并且对孩子也记录父亲信息,然后合并这个序列(一个孩子可能同时也是另一个孩子的孩子) 3. 对处理后的这个vector每个没有父亲的元素进行DFS。
回复 支持 反对

使用道具 举报

soysenioritasue 发表于 2015-11-2 08:58:39 | 显示全部楼层
“ 让求其中最长的嵌套interval序列”是什么意思啊
回复 支持 反对

使用道具 举报

soysenioritasue 发表于 2015-11-2 09:00:09 | 显示全部楼层

“嵌套深度最深”到底是什么意思啊,能不能再据个例子
回复 支持 反对

使用道具 举报

tktrung 发表于 2015-11-3 09:21:30 | 显示全部楼层
这题idea是不是像toposort,比如[-101, 90], [1, 5], [-5, 10] id 为 1,2,3,4
然后 1-》3 表示 1 嵌套 3,1-》4 表示1嵌套4等
然后就找最长路径 1-》3-》4 或 2-》3-》4
回复 支持 反对

使用道具 举报

returning 发表于 2015-12-7 07:43:47 | 显示全部楼层
tktrung 发表于 2015-11-3 09:21
这题idea是不是像toposort,比如[-101, 90], [1, 5], [-5, 10] id 为 1,2,3,4
然后 1-》3 表示 1 嵌套 ...

这道题我会像lintcode的Longest Increasing Continuous subsequence II那样解,可能还有更好办法,不过这个解法很直观。先是n^2的时间遍历构建一个map<int, set<int>>,其中key为1,value为一个set,表示id为1的interval包含了id为xx的interval,其中xx是value set的一个元素。然后,按照dp的办法更新一个array,array的每个元素就是从id为i的interval出发能够找到的最长subsequence。注意后面的寻找subsequenece的过程是O(N)的,原因和lintcode那道题一样。
回复 支持 反对

使用道具 举报

CrossTheWall 发表于 2015-12-7 12:24:43 | 显示全部楼层
tktrung 发表于 2015-11-3 09:21
这题idea是不是像toposort,比如[-101, 90], [1, 5], [-5, 10] id 为 1,2,3,4. From 1point 3acres bbs
然后 1-》3 表示 1 嵌套 ...

但是这样的话你要考虑建立嵌套的拓扑结构所需的复杂度
回复 支持 反对

使用道具 举报

本版积分规则

请点这里访问我们的新网站:一亩三分地Instant.

Instant搜索更强大,不扣积分,内容组织的更好更整洁!目前仍在beta版本,努力完善中!反馈请点这里

关闭

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

手机版|小黑屋|一亩三分地论坛声明 ( 沪ICP备11015994号 )

custom counter

GMT+8, 2016-12-9 10:30

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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