R********n 发帖数: 3601 | 1 【 以下文字转载自 SanFrancisco 讨论区 】
发信人: soldiercrab (老军医专治装B文学小青年), 信区: SanFrancisco
标 题: 一朋友被Google的电面干掉了
发信站: BBS 未名空间站 (Sat Dec 5 15:03:55 2009, 美东)
栽在一道编程题上:Find a longest increasing subsequence in an integer array。
问问题的人要求朋友拿出O(nlog(n))的算法,但朋友只给出了O(n^2)的dynamic
programming的方法。其实我觉得给出dynamic programming算法足够进入下一轮了。那
个O(nlog(n))的算法好歹也值当年一篇paper,而且貌似不是那么直观。电面就想出来
不容易。不过多半是我段位不够,还不够Google的要求。或者朋友的dynamic
programming其实错了(这道题要倒过来找,稍微绕一点点)。 |
r****o 发帖数: 1950 | 2 O(nlogn)的解法哪儿有?
这个好像有点难度。
array。
【在 R********n 的大作中提到】 : 【 以下文字转载自 SanFrancisco 讨论区 】 : 发信人: soldiercrab (老军医专治装B文学小青年), 信区: SanFrancisco : 标 题: 一朋友被Google的电面干掉了 : 发信站: BBS 未名空间站 (Sat Dec 5 15:03:55 2009, 美东) : 栽在一道编程题上:Find a longest increasing subsequence in an integer array。 : 问问题的人要求朋友拿出O(nlog(n))的算法,但朋友只给出了O(n^2)的dynamic : programming的方法。其实我觉得给出dynamic programming算法足够进入下一轮了。那 : 个O(nlog(n))的算法好歹也值当年一篇paper,而且貌似不是那么直观。电面就想出来 : 不容易。不过多半是我段位不够,还不够Google的要求。或者朋友的dynamic : programming其实错了(这道题要倒过来找,稍微绕一点点)。
|
g*******y 发帖数: 1930 | 3 这题是挺难的. 以前没见过的话,要对binary search相当敏感才行 |
c*********n 发帖数: 1057 | 4 我就算以前见过,而且深刻理解过,也很难一下就回忆起来啊。。。。哎。。。
【在 g*******y 的大作中提到】 : 这题是挺难的. 以前没见过的话,要对binary search相当敏感才行
|
g*******y 发帖数: 1930 | |
m*****f 发帖数: 1243 | 6 嗯,LCS就是O(n^2), 我想错了
【在 g*******y 的大作中提到】 : 这个就是他朋友的方法吧
|
m*****f 发帖数: 1243 | 7 什么叫做"(这道题要倒过来找,稍微绕一点点)"?
另外这道题其实就是CLRS例题, 看来要好好做做了
array。
【在 R********n 的大作中提到】 : 【 以下文字转载自 SanFrancisco 讨论区 】 : 发信人: soldiercrab (老军医专治装B文学小青年), 信区: SanFrancisco : 标 题: 一朋友被Google的电面干掉了 : 发信站: BBS 未名空间站 (Sat Dec 5 15:03:55 2009, 美东) : 栽在一道编程题上:Find a longest increasing subsequence in an integer array。 : 问问题的人要求朋友拿出O(nlog(n))的算法,但朋友只给出了O(n^2)的dynamic : programming的方法。其实我觉得给出dynamic programming算法足够进入下一轮了。那 : 个O(nlog(n))的算法好歹也值当年一篇paper,而且貌似不是那么直观。电面就想出来 : 不容易。不过多半是我段位不够,还不够Google的要求。或者朋友的dynamic : programming其实错了(这道题要倒过来找,稍微绕一点点)。
|
H*M 发帖数: 1268 | 8 CLRS上是O(nlgn) ?
我怎么记得DP的啊,O(n^2)
【在 m*****f 的大作中提到】 : 什么叫做"(这道题要倒过来找,稍微绕一点点)"? : 另外这道题其实就是CLRS例题, 看来要好好做做了 : : array。
|
c*********n 发帖数: 1057 | 9 co觉得
【在 H*M 的大作中提到】 : CLRS上是O(nlgn) ? : 我怎么记得DP的啊,O(n^2)
|
m*****f 发帖数: 1243 | 10 是课后一道*号的思考题
【在 H*M 的大作中提到】 : CLRS上是O(nlgn) ? : 我怎么记得DP的啊,O(n^2)
|
|
|
c*********n 发帖数: 1057 | 11 co觉得
【在 H*M 的大作中提到】 : CLRS上是O(nlgn) ? : 我怎么记得DP的啊,O(n^2)
|
H*****L 发帖数: 5705 | 12 n^2的话就不用sort再lcs了吧,有现成的dp
【在 g*******y 的大作中提到】 : 这个就是他朋友的方法吧
|
g*******y 发帖数: 1930 | 13 对,n个state,算每个state用n次操作
LCS比较经典嘛,把新问题转化为经典问题也是个常见的思路了~
【在 H*****L 的大作中提到】 : n^2的话就不用sort再lcs了吧,有现成的dp
|
z*******y 发帖数: 578 | 14 用DP结合二叉搜索树可以实现
把已经扫描的元素存到二叉树里,二叉树的元素是<数组元素,到这个元素的LCS的长度>
这样在update到每个数组元素时候的LCS的时间就是logn,总的时间就是nlogn |
g*******y 发帖数: 1930 | 15 这个题是一个关于动态规划二分的一个优化技术的一个经典的例子。
不过这个题甚至不需要建这样一个树,maintain一个sorted的数组来binary search就行了。
度>
【在 z*******y 的大作中提到】 : 用DP结合二叉搜索树可以实现 : 把已经扫描的元素存到二叉树里,二叉树的元素是<数组元素,到这个元素的LCS的长度> : 这样在update到每个数组元素时候的LCS的时间就是logn,总的时间就是nlogn
|
k***e 发帖数: 556 | 16 请查看 patience sort。
利用一个combinatorial性质,
note that we call a decreasing sequence as d-sequence, then
1. every array can be written as a set of disjoint d-sequences
2. min # of the set of desequences that consist of a[1:n] == max increasing
subsequence of a[1:n]
one relation as min-cut max-flow
it is not easy to forget it :)
必杀吧 哈哈
就行了。
【在 g*******y 的大作中提到】 : 这个题是一个关于动态规划二分的一个优化技术的一个经典的例子。 : 不过这个题甚至不需要建这样一个树,maintain一个sorted的数组来binary search就行了。 : : 度>
|
g*******y 发帖数: 1930 | 17 不错~你真牛,这样的sort都懂啊~
increasing
【在 k***e 的大作中提到】 : 请查看 patience sort。 : 利用一个combinatorial性质, : note that we call a decreasing sequence as d-sequence, then : 1. every array can be written as a set of disjoint d-sequences : 2. min # of the set of desequences that consist of a[1:n] == max increasing : subsequence of a[1:n] : one relation as min-cut max-flow : it is not easy to forget it :) : 必杀吧 哈哈 :
|
p********7 发帖数: 549 | 18 我想到一个办法,结合DP
分配一个array[n]
在用DP第一次遍历的时候用一个数据结构记录当前最长增加数列的长度和endpoint,遍
历完之后就得到最长的了。
比如:
1 2 5 6 3 4 3 4 9 13 14 15 16 17
array 0 1 2 3 0 1 0 1 2 3 4 5 6 7
max length 0 1 2 3 3 3 3 3 3 3 4 5 6 7
end point 0 1 2 3 3 3 3 3 3 3 10 11 12 13 |
f*********5 发帖数: 1237 | 19 fibonacci array + DP
array。
【在 R********n 的大作中提到】 : 【 以下文字转载自 SanFrancisco 讨论区 】 : 发信人: soldiercrab (老军医专治装B文学小青年), 信区: SanFrancisco : 标 题: 一朋友被Google的电面干掉了 : 发信站: BBS 未名空间站 (Sat Dec 5 15:03:55 2009, 美东) : 栽在一道编程题上:Find a longest increasing subsequence in an integer array。 : 问问题的人要求朋友拿出O(nlog(n))的算法,但朋友只给出了O(n^2)的dynamic : programming的方法。其实我觉得给出dynamic programming算法足够进入下一轮了。那 : 个O(nlog(n))的算法好歹也值当年一篇paper,而且貌似不是那么直观。电面就想出来 : 不容易。不过多半是我段位不够,还不够Google的要求。或者朋友的dynamic : programming其实错了(这道题要倒过来找,稍微绕一点点)。
|
r****o 发帖数: 1950 | 20 能不能说详细一点?
【在 f*********5 的大作中提到】 : fibonacci array + DP : : array。
|
r***e 发帖数: 486 | 21 这个wiki上有解法。
http://en.wikipedia.org/wiki/Longest_increasing_subsequence
array。
【在 R********n 的大作中提到】 : 【 以下文字转载自 SanFrancisco 讨论区 】 : 发信人: soldiercrab (老军医专治装B文学小青年), 信区: SanFrancisco : 标 题: 一朋友被Google的电面干掉了 : 发信站: BBS 未名空间站 (Sat Dec 5 15:03:55 2009, 美东) : 栽在一道编程题上:Find a longest increasing subsequence in an integer array。 : 问问题的人要求朋友拿出O(nlog(n))的算法,但朋友只给出了O(n^2)的dynamic : programming的方法。其实我觉得给出dynamic programming算法足够进入下一轮了。那 : 个O(nlog(n))的算法好歹也值当年一篇paper,而且貌似不是那么直观。电面就想出来 : 不容易。不过多半是我段位不够,还不够Google的要求。或者朋友的dynamic : programming其实错了(这道题要倒过来找,稍微绕一点点)。
|