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其实错了（这道题要倒过来找，稍微绕一点点）。
|
