b*n
2 楼
我用binary search找last non-overlap.处理100,000的时候非常慢.
bestCost(x) = max(bestCost(last non-overlap) + x's cost, bestCost(x-1))
bestCost(x) = max(bestCost(last non-overlap) + x's cost, bestCost(x-1))
B*t
3 楼
先按stop time对record排序， 然后从0到n-1依次找出包含的当前record的最大
score，用binary search找，同时update maxScore。 O(nlogn)
不用什么优化，169.209 ms on its longest test case
【在 b*****n 的大作中提到】
: 我在实现gattaca时,Binary search化的时间很多.有什么方法可以优化?
score，用binary search找，同时update maxScore。 O(nlogn)
不用什么优化，169.209 ms on its longest test case
【在 b*****n 的大作中提到】
: 我在实现gattaca时,Binary search化的时间很多.有什么方法可以优化?
p*7
4 楼
我看到那么长的题就头疼
b*n
5 楼
能PM一下这个source code 吗?
我就是这个需要很长时间.
我就是这个需要很长时间.
h*6
6 楼
这个方法好，我把我的帖子删掉了。
O(nlogn)的复杂度，对于100,000级别的输入来说，应该能在1秒钟之内完成啊。
【在 B*****t 的大作中提到】
: 先按stop time对record排序， 然后从0到n-1依次找出包含的当前record的最大
: score，用binary search找，同时update maxScore。 O(nlogn)
: 不用什么优化，169.209 ms on its longest test case
O(nlogn)的复杂度，对于100,000级别的输入来说，应该能在1秒钟之内完成啊。
【在 B*****t 的大作中提到】
: 先按stop time对record排序， 然后从0到n-1依次找出包含的当前record的最大
: score，用binary search找，同时update maxScore。 O(nlogn)
: 不用什么优化，169.209 ms on its longest test case
p*7
7 楼
这题用dp做，复杂度是多少？ 感觉配上其他数据结构可以优化到N，具体怎么算我还没
想清楚
【在 h**6 的大作中提到】
: 这个方法好，我把我的帖子删掉了。
: O(nlogn)的复杂度，对于100,000级别的输入来说，应该能在1秒钟之内完成啊。
想清楚
【在 h**6 的大作中提到】
: 这个方法好，我把我的帖子删掉了。
: O(nlogn)的复杂度，对于100,000级别的输入来说，应该能在1秒钟之内完成啊。
p*7
8 楼
比如用一个hashtable存 ，关键字是stop
我们在建立一个value的表格，Value【i】表示最大从0到i的Value，i范围是0-99
遍历Valuetable
就查一次hashtable的stop，看i是否是stop，
如果是就获得start和score，
Value【i】 = max(score+Value[i-(stop-start+1)],Value[i-1]);
如果不是Value【i】=Value【i-1】；
复杂度就是N
我们在建立一个value的表格，Value【i】表示最大从0到i的Value，i范围是0-99
遍历Valuetable
就查一次hashtable的stop，看i是否是stop，
如果是就获得start和score，
Value【i】 = max(score+Value[i-(stop-start+1)],Value[i-1]);
如果不是Value【i】=Value【i-1】；
复杂度就是N
b*n
9 楼
需要NLogN时间找Value[i-(stop-start+1)]
p*7
10 楼
这是个数组，获得数组元素还需要时间？
【在 b*****n 的大作中提到】
: 需要NLogN时间找Value[i-(stop-start+1)]
【在 b*****n 的大作中提到】
: 需要NLogN时间找Value[i-(stop-start+1)]
b*n
11 楼
我说得不是很精确.对每一个元素,找前面的不重叠的元素需要nLogN时间.另外, 这道题还需要重新排序,也需要NLogN时间.
【在 p********7 的大作中提到】
: 这是个数组，获得数组元素还需要时间？
【在 p********7 的大作中提到】
: 这是个数组，获得数组元素还需要时间？
p*7
12 楼
问题是用hashtable就不用啊，你看我之前写的那个算法，hashtable，查找的时候用
stop这个关键词，insert的时候把start，stop，value一起作为一个数据结构存了
题还需要重新排序,也需要NLogN时间.
【在 b*****n 的大作中提到】
: 我说得不是很精确.对每一个元素,找前面的不重叠的元素需要nLogN时间.另外, 这道题还需要重新排序,也需要NLogN时间.
stop这个关键词，insert的时候把start，stop，value一起作为一个数据结构存了
题还需要重新排序,也需要NLogN时间.
【在 b*****n 的大作中提到】
: 我说得不是很精确.对每一个元素,找前面的不重叠的元素需要nLogN时间.另外, 这道题还需要重新排序,也需要NLogN时间.
b*n
13 楼
没太理解
1 2 3 4
123456789012345678901234567890123456789012345
AGCTAGCTACGTACGATCGACGATCGATCGATGCATCATGCATCG
E0 |--------| Weight: 11
E1 |----| Weight: 5
E2 |-----------------| Weight: 13
E3 |----| Weight: 5
E4 |----| Weight: 5
E0 10 -> 1 11
E1 19 -> 14 5
E2 36 -> 18 13
E3 31 -> 2
【在 p********7 的大作中提到】
: 问题是用hashtable就不用啊，你看我之前写的那个算法，hashtable，查找的时候用
: stop这个关键词，insert的时候把start，stop，value一起作为一个数据结构存了
:
: 题还需要重新排序,也需要NLogN时间.
1 2 3 4
123456789012345678901234567890123456789012345
AGCTAGCTACGTACGATCGACGATCGATCGATGCATCATGCATCG
E0 |--------| Weight: 11
E1 |----| Weight: 5
E2 |-----------------| Weight: 13
E3 |----| Weight: 5
E4 |----| Weight: 5
E0 10 -> 1 11
E1 19 -> 14 5
E2 36 -> 18 13
E3 31 -> 2
【在 p********7 的大作中提到】
: 问题是用hashtable就不用啊，你看我之前写的那个算法，hashtable，查找的时候用
: stop这个关键词，insert的时候把start，stop，value一起作为一个数据结构存了
:
: 题还需要重新排序,也需要NLogN时间.
h*6
14 楼
你们两位的n不一样，一个是个数，一个是值域。
p*7
15 楼
我的算法不需要binary search，0-99遍历一次出结构，你说的N是8吧？
我说的N是100.
【在 b*****n 的大作中提到】
: 没太理解
: 1 2 3 4
: 123456789012345678901234567890123456789012345
: AGCTAGCTACGTACGATCGACGATCGATCGATGCATCATGCATCG
: E0 |--------| Weight: 11
: E1 |----| Weight: 5
: E2 |-----------------| Weight: 13
: E3 |----| Weight: 5
: E4 |----| Weight: 5
: E0 10 -> 1 11
我说的N是100.
【在 b*****n 的大作中提到】
: 没太理解
: 1 2 3 4
: 123456789012345678901234567890123456789012345
: AGCTAGCTACGTACGATCGACGATCGATCGATGCATCATGCATCG
: E0 |--------| Weight: 11
: E1 |----| Weight: 5
: E2 |-----------------| Weight: 13
: E3 |----| Weight: 5
: E4 |----| Weight: 5
: E0 10 -> 1 11
b*n
16 楼
明白了.
【在 p********7 的大作中提到】
: 我的算法不需要binary search，0-99遍历一次出结构，你说的N是8吧？
: 我说的N是100.
【在 p********7 的大作中提到】
: 我的算法不需要binary search，0-99遍历一次出结构，你说的N是8吧？
: 我说的N是100.
t*j
17 楼
这道题题目是什么？麻烦楼主讲讲！
【在 b*****n 的大作中提到】
: 我在实现gattaca时,Binary search化的时间很多.有什么方法可以优化?
【在 b*****n 的大作中提到】
: 我在实现gattaca时,Binary search化的时间很多.有什么方法可以优化?
y*e
18 楼
碰巧今天在做这个题目。说下我对这个题目的理解。
问题的输入是一个DNA（可以认为是一个字符串）。这个DNA上有一系列基因，每一个基
因有起始点，结束点，以及权重值。要求在这个DNA串里面，找出不重叠的所有基因，使
得它们的权重值总和最大。
举个例子：
DNA（长度是45）：AGCTAGCTACGTACGATCGACGATCGATCGATGCATCATGCATCG
5个基因（起点，终点，权重）：
E0： 1 10 11
E1： 14 19 5
E2： 18 36 13
E3： 26 31 5
E4： 35 40 5
E0没有与任何其他基因相交。E2与E1，E3，E4相交。E1，E3，E4并不互相重叠。依题意，
符合条件的基因组合是E0，E1，E3，E4，权重总和是26，是最大的可能组合。
题目的链接在这里：http://www.facebook.com/careers/puzzles.php?puzzle_id=15
值得注意的是，DNA的具体值并不重要，只需要它的长度就可以了。
我最开始用Dynamic Program
【在 t*****j 的大作中提到】
: 这道题题目是什么？麻烦楼主讲讲！
问题的输入是一个DNA（可以认为是一个字符串）。这个DNA上有一系列基因，每一个基
因有起始点，结束点，以及权重值。要求在这个DNA串里面，找出不重叠的所有基因，使
得它们的权重值总和最大。
举个例子：
DNA（长度是45）：AGCTAGCTACGTACGATCGACGATCGATCGATGCATCATGCATCG
5个基因（起点，终点，权重）：
E0： 1 10 11
E1： 14 19 5
E2： 18 36 13
E3： 26 31 5
E4： 35 40 5
E0没有与任何其他基因相交。E2与E1，E3，E4相交。E1，E3，E4并不互相重叠。依题意，
符合条件的基因组合是E0，E1，E3，E4，权重总和是26，是最大的可能组合。
题目的链接在这里：http://www.facebook.com/careers/puzzles.php?puzzle_id=15
值得注意的是，DNA的具体值并不重要，只需要它的长度就可以了。
我最开始用Dynamic Program
【在 t*****j 的大作中提到】
: 这道题题目是什么？麻烦楼主讲讲！
相关阅读
FB电面求分析 (转载)[合集] bloomberd fsd 面试（又死在behavior question上了）报一个MS SDE2的offer[合集] 急求帮助：Layoff了，身份出问题了 H１---->F2报一个Google Offer[合集] H1B转F-1[合集] 牛人们帮我想想怎么办，公司要做国内背景调查storage management system的码农有前途么？amazon 电面之后没回应？OPT做independent contractor，算是self employed，不算unemplo4.1号提交h1b的xdjm们，都收到receipt notice了吗Amazon在多伦多的分部怎么样？面试问题Research Scientist/Engineer—full time or intern Open Posit (转载)O签证很难申请吗北京天线工作[合集] 请教个工作身份的问题。该申cpt，opt还是H1？顺便问加拿大renew长期发展比较Mobile Developer vs Web Developer vs BackEnd Developer请教OPT加急的问题L : recruiter dissappear after first contact?