Palantir onsite被虐记

LZ能不能说下第四题，没读懂题呢？感觉像 merge interval / insert interval 变种？

shawlin 发表于 2015-3-25 04:56
LZ能不能说下第四题，没读懂题呢？感觉像 merge interval / insert interval 变种？

就是[1,7]、[2,8]、[0, 3]这个三个区间，[2，3]重合的次数最多。

第四个interval start就+1，interval end就-1，然后对所有端点排序就行了

shawlin 发表于 2015-3-25 04:55
能否说一下第三题的思路呢？

思路在之前的帖子里哈。

Hi，我似乎找到一个讨论贴：

https://www.ocf.berkeley.edu/~ww ... play;num=1247162214

我的方法有局限性，如果两个数字之差太大，就会有问题，等于是要hash。帖子里TenaliRaman的方法不会有问题，因为他只是不断的找a+b = 2b里的b。

我整理一下思路：

这题本意上是要求我们找到任意的indices，要求i0<i1<ik。
如果不局限于i0<i1...<ik，那也可以用TenaliRaman的方法，但是用我的方法就不对了。我的方法本质上等同于miletus的方法。

因此，我们在不局限于i0<i1...<ik，可以用TenaliRaman的dynamic programming方法达到O(n^2)的复杂度，并且没有存储空间的限制。

这里还有一篇Jeff的分析：

http://web.engr.illinois.edu/~jeffe/pubs/pdf/arith.pdf

就是说这题有两种形式，一种是在序列里找等差数列——不可以打乱顺序，一种是在集合里找等差数列——可以打乱顺序。两者都是不连续的。

hash的方法。也就是我的方法，前面那位同学也是hash的方法。也就是说用dp[i][j]，代表第i位的时候，相差为j的数的最长个数。

但是hash的限制就是两个数可能相差太大，数字可能很多。所以这题其实可以不用hash。在jeff的论文里详细阐明了这个思想。等差数列a_i+a_j=2b一定是个固定数字，那么我们从这个性质出发，可以找最长的序列。首先排序，每次假设a_i=b，如果a_(i) - a_(k)> a_(j) - a_(i)，那么需要将index j增大；反过来将index k减小。如果是=，那么正好找到一组对称，dp[k][i] = dp[i][j] + 1，其中dp[k][i]，代表这个等差数列的前两个数字分别为index k和index i。总的来说这种解法还是非常巧妙的，里面有一些细节。

具体的证明可以仔细参考jeff的论文。

补充内容 (2015-3-25 10:22):
公式被吞了。
dp[k][i] = dp[i][j] + 1，其中dp[k][i]，代表这个等差数列的前两个数字分别为index k和index i。

补充内容 (2015-3-25 10:23):
貌似打不出来二维的……
dp[k] [i] = dp[i] [j] + 1，其中dp[k] [i]，代表这个等差数列的前两个数字分别为index k和index i。

补充内容 (2015-3-25 10:23):
醉了
dp[k, i] = dp [i, j] + 1，其中dp[k, i] ，代表这个等差数列的前两个数字分别为index k和index i。

GTmac 发表于 2015-3-25 09:49
第四个interval start就+1，interval end就-1，然后对所有端点排序就行了

拍完序选个中位数是不是就行了?

GTmac 发表于 2015-3-24 20:49
第四个interval start就+1，interval end就-1，然后对所有端点排序就行了

没理解啊，能不能细说下？

shawlin 发表于 2015-3-25 10:39
没理解啊，能不能细说下？

我的理解：

给出n个区间，求被共享最多的子区间。

按照lz的例子：

[1,7]、[2,8]、[0, 3]

   1 2 3 4 5 6 7 8 9
      2 3 4 5 6 7 8
0  1 2 3

重叠最多的就是[2, 3]。

其实第二小问浮点数和第一小问本质上是一样的，考的都是离散化的思想。因为实际上如果区间的端点值太大（[a, b]，a = 0, b = IntegerMax），直接数数的方法一样没法做。

除了离散化以外，如果要求复杂度较低。还需要建一颗线段树（带lazy tag，每次更新时将对应区间的值+1，其实可以理解为将多个点的值+1），这样每次插入的复杂度是logn。每次查询也是logn。

补充内容 (2015-3-25 21:08):
代码估计有点长，如果需要的话我给你个链接呗。

robinho364 发表于 2015-3-24 21:19
思路在之前的帖子里哈。

谢谢啦，看懂了，很tricky的DP, 等差序列的性质还给中学老师啦 哈哈

robinho364 发表于 2015-3-25 08:04
我的理解：

给出n个区间，求被共享最多的子区间。

建一个interval search tree? 再次感谢，求个代码链接
我的思路是 每一个interval 对应一个字符 比如
[0, 3] : A  [1, 7] : B, [2, 8] : C
给interval排序
然后用leetcode  merge interval的思路， merge的结果为
[0, 1] : A
[1, 2] : AB
[2, 3] : ABC
[3, 7] : BC
[7, 8] : B
选出一个对应最长字符串的interval？就是[2,3] 不知道行不行哈，欢迎讨论

shawlin 发表于 2015-3-25 23:52
建一个interval search tree? 再次感谢，求个代码链接
我的思路是 每一个interval 对应一个字符 比如
[ ...

http://ideone.com/kqntG3

您好。

我没有刷过leetcode，所以这种题一般都是惯性思维了。

能不能给个链接呢？看起来很精妙的样子。