郁闷死了，macbook pro刚买了一周就出新款了 - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>Apple - 家有苹果

郁闷死了，macbook pro刚买了一周就出新款了

郁闷死了，macbook pro刚买了一周就出新款了# Apple - 家有苹果

R*n2011-10-24 07:10

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

B*Z2011-10-24 07:10

2 楼

以及迅速转型为装备砸人，实在是让我想起另外一位李察。震撼。刘
话说烟雨这个次级位面+时间不等的设置，很容易出bug啊，不过估计没人仔细算就是

C*82011-10-24 07:10

3 楼

从macmall订的，本想Return and rebuy，结果说要收15%的restocking fee
想想还是算了吧，亏了180G硬盘

r*o2011-10-24 07:10

4 楼

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

b*92011-10-24 07:10

5 楼

不错了，起码烟男人品不错。看最近的更新速度，明显是想让读者在结束时爽一把
。有几个网文作者愿意这么干的？

n*c2011-10-24 07:10

6 楼

苹果这么坏呢，就一周还不能free upgrade。

g*y2011-10-24 07:10

7 楼

这题是挺难的. 以前没见过的话，要对binary search相当敏感才行

B*Z2011-10-24 07:10

8 楼

越看越像，特别是带一堆人装备碾压+法师碾压法罗土著的时候，完全就是兽血沸腾换
了个马甲

S*g2011-10-24 07:10

9 楼

同情
不只硬盘吧，大部分还升级了显卡和CPU。。。。

【在 C******8 的大作中提到】

: 从macmall订的，本想Return and rebuy，结果说要收15%的restocking fee
: 想想还是算了吧，亏了180G硬盘

c*n2011-10-24 07:10

10 楼

我就算以前见过，而且深刻理解过，也很难一下就回忆起来啊。。。。哎。。。

【在 g*******y 的大作中提到】

: 这题是挺难的. 以前没见过的话，要对binary search相当敏感才行

s*32011-10-24 07:10

11 楼

让你们买的时候不做research rumor9月份就出来了

g*y2011-10-24 07:10

12 楼

这个就是他朋友的方法吧

c*e2011-10-24 07:10

13 楼

你要在apple店买肯定可以return rebuy

m*f2011-10-24 07:10

14 楼

嗯，LCS就是O(n^2)，我想错了

【在 g*******y 的大作中提到】

: 这个就是他朋友的方法吧

x*u2011-10-24 07:10

15 楼

It's MacMall's problem. If you bought from Apple directly, there's no
restocking fee for returns.

【在 n****c 的大作中提到】

: 苹果这么坏呢，就一周还不能free upgrade。

m*f2011-10-24 07:10

16 楼

什么叫做"（这道题要倒过来找，稍微绕一点点）"?
另外这道题其实就是CLRS例题，看来要好好做做了

array。

【在 R********n 的大作中提到】

r*a2011-10-24 07:10

17 楼

他应该是买了13in的

【在 S**********g 的大作中提到】

: 同情
: 不只硬盘吧，大部分还升级了显卡和CPU。。。。

H*M2011-10-24 07:10

18 楼

CLRS上是O(nlgn) ?
我怎么记得DP的啊,O(n^2)

【在 m*****f 的大作中提到】

: 什么叫做"（这道题要倒过来找，稍微绕一点点）"?
: 另外这道题其实就是CLRS例题，看来要好好做做了
:
: array。

c*n2011-10-24 07:10

19 楼

co觉得

【在 H*M 的大作中提到】

: CLRS上是O(nlgn) ?
: 我怎么记得DP的啊,O(n^2)

m*f2011-10-24 07:10

20 楼

是课后一道*号的思考题

【在 H*M 的大作中提到】

: CLRS上是O(nlgn) ?
: 我怎么记得DP的啊,O(n^2)

c*n2011-10-24 07:10

21 楼

co觉得

【在 H*M 的大作中提到】

: CLRS上是O(nlgn) ?
: 我怎么记得DP的啊,O(n^2)

H*L2011-10-24 07:10

22 楼

n^2的话就不用sort再lcs了吧，有现成的dp

【在 g*******y 的大作中提到】

: 这个就是他朋友的方法吧

g*y2011-10-24 07:10

23 楼

对，n个state，算每个state用n次操作
LCS比较经典嘛，把新问题转化为经典问题也是个常见的思路了~

【在 H*****L 的大作中提到】

: n^2的话就不用sort再lcs了吧，有现成的dp

z*y2011-10-24 07:10

24 楼

用DP结合二叉搜索树可以实现
把已经扫描的元素存到二叉树里，二叉树的元素是
这样在update到每个数组元素时候的LCS的时间就是logn，总的时间就是nlogn

g*y2011-10-24 07:10

25 楼

这个题是一个关于动态规划二分的一个优化技术的一个经典的例子。
不过这个题甚至不需要建这样一个树，maintain一个sorted的数组来binary search就行了。

度>

【在 z*******y 的大作中提到】

: 用DP结合二叉搜索树可以实现
: 把已经扫描的元素存到二叉树里，二叉树的元素是
: 这样在update到每个数组元素时候的LCS的时间就是logn，总的时间就是nlogn

k*e2011-10-24 07:10

26 楼

请查看 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*y2011-10-24 07:10

27 楼

不错～你真牛，这样的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*72011-10-24 07:10

28 楼

我想到一个办法，结合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*52011-10-24 07:10

29 楼

fibonacci array + DP

array。

【在 R********n 的大作中提到】

r*o2011-10-24 07:10

30 楼

能不能说详细一点?

【在 f*********5 的大作中提到】

: fibonacci array + DP
:
: array。

r*e2011-10-24 07:10

31 楼

这个wiki上有解法。
http://en.wikipedia.org/wiki/Longest_increasing_subsequence

array。

【在 R********n 的大作中提到】