Twitter 店面

上来直接一道题：

给一组没有排序的interval [min, max

您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

[-5, 10], [1, 5]

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那道题一样。

楼主， 我决定Twitter现在有种不缺人的感觉，你这电面题比我当年那个可是要难不少。

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

pyemma 发表于 2015-11-1 12:23
感觉就是用DP吧，先把Array按照左端点sort一遍，然后从最后往前撸，dp存储以i开始的最长嵌套距离。时间复杂 ...

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

请问是网投的吗？

这不就是merge interval原题吗

liyanjia92 发表于 2015-11-1 06:52
这不就是merge interval原题吗

感觉不太一样啊。 这个是完全嵌套，不是overlap

楼主[-101, 90], [1, 5], [-5, 10] 这个是不是也是最长的？

hyliu0000 发表于 2015-11-1 11:03
楼主[-101, 90], [1, 5], [-5, 10] 这个是不是也是最长的？

是的，会有多个解，我就给了一个解

kakka 发表于 2015-11-1 06:21
请问是网投的吗？

是网投的

楼主，“最长序列” 是什么意思？是指value range最大的嵌套还是指序列的个数最多？

CrossTheWall 发表于 2015-11-1 12:09
楼主，“最长序列” 是什么意思？是指value range最大的嵌套还是指序列的个数最多？

嵌套深度最深

感觉就是用DP吧，先把Array按照左端点sort一遍，然后从最后往前撸，dp[i]存储以i开始的最长嵌套距离。时间复杂度O(N^2).