《行尸走肉》更新了这么多季仍然火爆的原因 - 未名空间MITBBS历史存档

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

Redian新闻

>未名空间

>TVChinese - 中文电视

《行尸走肉》更新了这么多季仍然火爆的原因

《行尸走肉》更新了这么多季仍然火爆的原因# TVChinese - 中文电视

c*82018-11-06 08:11

1 楼

根据 US News 2014 排名
http://grad-schools.usnews.rankingsandreviews.com/best-graduate-schools/top-science-schools/computer-science-rankings
注：大陆背景指在中国大陆接受本科教育
++++++++++++++++++++++++++++
#1 Carnegie Mellon University
- Yiming Yang
- Eric P. Xing
- Jian Ma

#1 Massachusetts Institute of Technology
#1 Stanford University

#1 University of California - Berkeley
- Dawn Song
#5 University of Illinois - Urbana-Champaign
- Jiawei Han
- Chengxiang Zhai
- Tao Xie
- Jian Peng
#6 Cornell University
- Elaine Shi
#6 University of Washington
- Xi Wang
#8 Princeton University
- Kai Li
#9 Georgia Institute of Technology
- Ling Liu
- Hongyuan Zha
- Wenke Lee
- Jun Xu
- Jimeng Sun
- Le Song
#9 University of Texas - Austin
- Qixing Huang
#11 California Institute of Technology
- Yizhao Hou
#11 University of Wisconsin - Madison
- Jin-Yi Cai
- Jerry Zhu
#13 University of California - Los Angeles
- Jason Cong
- Lixia Zhang
- Song-Chun Zhu
- Songwu Lu
- Wei Wang
- Yizhou Sun
#13 University of Michigan - Ann Arbor
- Yaoyun Shi
- Mingyan Liu
- Jia Deng
- Lingjia Tang
- Qiaozhu Mei
- Jieping Ye
- Yuanfang Guan
#15 Columbia University
- Junfeng Yang
- Changxi Zheng
- Xi Chen
#15 University of California - San Diego
- Yuanyuan Zhou

#15 University of Maryland - College Park
#18 Harvard University
- Yiling Chen
#19 University of Pennsylvania
#20 Brown University
#20 Purdue University - West Lafayette
- Dongyan Xu
- Xiangyu Zhang
- Zhiyuan Li
- Ninghui Li
- Luo Si
- He Wang
#20 Rice University
- Lin Zhong
#20 University of Southern California
- Shang-Hua Teng
- Ting Chen
- Fei Sha
- Yan Liu
- Chao Wang
- Haipeng Luo

#20 Yale University
- Zhong Shao
- Yang Yang
- Minlan Yu

R*i2018-11-06 08:11

2 楼

说他们问题变态不是盖的，第一轮就两道
1. N node的binary tree一共能有几种不同的tree structure，写code，数学公式
2. 给int[] in, 生成int[] out, out[i]= product of every element of in except
in[i]，不能用除号, O(n) time required
虽然都是常见题，但我都没见过。两道题都在提示下摸爬滚打的弄出来了。
P号称面试难度比G,F还大。随便查了查，SE基本都是stanford毕业的。面我的
人也算大牛，在stackoverflow上all time reputation排名前50的，也只是普通SE。我这种小
虾米就算能过这轮后面肯定也要挂。

p*r2018-11-06 08:11

3 楼

我不记得我打过水痘疫苗了没，反正是没出过水痘，能不能就说出过水痘了，这样是不
是就不用打了？
我看几个人都说，水痘疫苗自己说出过了，就算过了，医生不会验血检查的。。。

s*s2018-11-06 08:11

4 楼

XDJM 新年快乐，愿大家心想事成，早日拿绿卡
为什么是据说呢？我熬不住问HR， HR 打电话问律师，只是简单的一句话，批了。
具体什么时候批的我也不知道，虽然我出了 PP 的费用。感觉在律师眼里， PERM/
140 没我叉事一样。TNND。我提了要复印件的事，暂时还没有回复。
我是 10/21 PERM 批的， 12/4 交的 I-140, NSC, 我只知道我的钱是 12/6 扣掉的。
当初我自己愿意出 PP 的费用，一是考虑到公司是否会在新年裁员，另外也是 TNND
的怕煎熬。虽然 $1225 对我来说也是一大笔费用。
穷人，没有包子，抱歉

e*s2018-11-06 08:11

5 楼

首先，作为the walking dead的小粉丝，支持我看了五季的原因有很多，上面也大多
说到了，比如将人类伦理放在极端情况下考量： Rick杀死Shane，Lori和Shane通奸，
Carrol杀死病人，Carrol杀死丽兹，Rick杀死或放过各种可杀可不杀的人，救或不救各
种可救可不救的人...可以明显的看到，故事开始Rick的道德标准基本上是正常社会中
的道德标准(特别是他还有警察的身份)。不过随着故事进行，对他的刺激越来越多，
Rick的道德标准也越来越下滑，但也没有到达完全无道德的地步。基本上来说，随着一
次次艰难的选择，Rick心里的标准也越来越明晰，在两难情境中也越来越少犹豫。灾难
中对人类伦理的想象自然是十分吸引人的，但在我看来，更吸引人的莫过于对人类社会
结构的想象。
在僵尸潮爆发的初期，美国政府没有出现任何戏份，估计很快就弃疗了。无怪，北美大
平原上，的确没有什么可以阻挡僵尸大军的进攻。况且，所有人身上都附带病毒，所以
理论上需要所有的正常(非正常)死亡都处于监控之下才可能防御。而现代的政府所依赖
的如电视，网络，无线电等种种控制手段，在灾难中都极易受到打击。这种形式天然决
定了幸存者们不可能组成特别大的团体，不但部落行不通，城邦之类的自治城镇也不可
能，至于美国各级政府的巨大上层建筑，自然也只有崩溃。
下面就分别说说剧中出现的几个小团体
Rick一行人——自由人的联合
典型的家族小团体，以Rick，Lori，Shane三个好基(pin)友(tou)为中心，吸纳其他几
个小家庭组成。至于决策形式，可以说是典型的民主集中制，XD，前期Shane来集中，
后期Rick来集中，在Rick杀掉Shane之后，短暂的变为Rick的独裁制，后来在监狱被总
督攻陷后，基本上又回到原样。Rick的团体从某种意义上说是自由主义的，团结众人的
可以说是一种相同的道德观，而离开则是自由的，Rick从未试图阻止成员离开。这也是
为什么这个团队是主角团队，从某种意义上，这个团队最能体现美国的建国精神。团队
根据相同的道德观吸收新成员(Rick的三个问题)，也根据价值观来淘汰成员(火拼Shane
，放逐Carrol...)这样灵活的组成方式，使得团队得以几度分裂又几度重聚，分裂使得
团队避免了火拼，重聚又一再证明了角色们在某些价值观上达成了统一，使得这个团体
具备了特殊的凝聚力。在监狱被总督攻陷之前，在各方面都像是一个颇为自由的小社会
，吸纳并养活了大量的人口，为成群的儿童提供教育。而且可以看出，Rick等元老组成
委员会完成大事的决策，但并非事无巨细，并且他们并没有谋求更高级的待遇(阶级并
没有产生)。而劳动的分配基本上是能者多劳，并未出现任何强制劳动的情况。总的来
说，监狱后期实现了剧中人类所创造的最佳政治模式。
Governor总督的小镇——负责制政府
假想一下，如果作为一个总督小镇生活的幸存者，不开上帝视角，那Governor的统治可
以说是非常完美的。镇上有相对富足的生活(可以开party)，虽然这些资源来自于巧取
豪夺外部的幸存者，但Governor一直保守着秘密，并未让镇中的幸存者知晓。不错，这
是一个以邻为壑的政权，并且数次依赖仇外的情绪达成团结。但不得不说总督在这个失
序的世界中恢复了政府，可能还称得上是负责制政府。不论总督对Rick等外面的幸存者
如何壕无人性地杀掠，显而易见的是，他保护镇子里的人口，并非为了利用他们的劳动
而进一步提高自己和跟班们的生活水平，而是实实在在为了镇子里的人有更安稳的生活
。从这一点上，他的政府是负责制的，而不是专制的。不谈实现的手段，Governor前期
所维护的镇子，甚至是比监狱更加美好的存在。如果非要说缺点，虽然剧中没有表现，
但可以想见，总督的镇子中，加入和脱离可能并不是完全自由的，虽然可能有一定程度
的自主，但一定面临着相当大的阻力(甚至报复)。
Joe的法制团伙——法律
在《The Walking Dead》第四季中，Daryl与Beth走散之后，遇到并加入了Joe的团伙。
Joe的团伙可以说在崩坏的世界中部分地恢复了法律。法律的内容非常简单：1.最先说
claim的人占有资源。不论是什么资源(食品、床...)都适用这条规则，甚至Daryl射死
的猎物也这样被别人强占；2.说谎的人可以被大家随意处罚。说是随意处罚，但基本上
是活活打死。这两个规定可谓是简单明了，概念非常明确以至于可以视为两个法律条文
。而“法律”不禁止的事情，在这个小团体里都是合法的，人与人之前也互不干扰，各
过各的。在一定程度上，这种规定非常适合Joe和Daryl这样个体战斗能力非常强，又不
愿意甘居人下的大老爷们儿。使得若干强力的男人有可能结成一个互惠的生活团体而不
至于火拼，简单而高效。唯一的缺陷，虽然这是一个有法制的小团体，但还称不上法治
。法治要求有独立自主、客观公正的执法机关，但这个团体中，Joe一人可以说对于第
二条“说谎”的法律具有解释权。这使得Joe一定程度上称为统治者，最后甚至想利用
这条法律杀掉Daryl。
女警Dawn的合作社——经济秩序
以女警察Dawn为首的几个前警察带领一些幸存者驻守在亚特拉大的一家医院，他们阻塞
了楼梯，只留一个出入口，使得这一地方基本上不可能被僵尸攻陷。可以说，他们的基
地具有剧中最好的防御条件(虽然没有什么物产)。医院的运作带有强烈的经济算计：每
个人消耗的资源都被记下，由其劳动进行补偿。可以视为创造了一种信用货币。在这种
交换机制甚至有一定市场性，能提供稀缺服务的医生过着相对富足的生活，在能源稀缺
的情况下还可以听音响；而拖地搞清洁的Noah则生活的比较悲催，地位也比较低下。由
经济利益的计算出发，医院的人会在外面抓捕(并致伤)幸存者，然后通过救治他们并强
迫他们提供服务加以补偿。如果幸存者受伤过重，需要消耗太多的药品，医院则会放弃
救治。同样像Noah一样的叛逃者会被尽全力捉捕回来。可以说，在Dawn等人眼里，幸存
者代表着劳动力，其背后有且只有经济价值。医院的另一个特点就是突出的阶级性。
Dawn和其他几个男女警察穿着警服，负责外出搜索资源，其他人身着病号服，在内部完
成一些劳动。男警察时常欺凌弱小，如推搡老人，强迫妇女提供性服务，Dawn对此基本
上也视而不见，并且认为只有这样才能维护自己的领导。总的来说，医院是剧中出现的
最复杂最高级的社会结构，至于好坏，则仁者见仁了。Beth和Carrol是绝不会愿意生活
在一个阶级社会的，而Noah在出逃体验了一圈之后，最后还是选择留下，这也直接导致
了Beth的死亡。
食人族Gary——完全的失序
食人族可以说是Rick一行人的反面，在各个路口设下标牌吸引幸存者们前往终点站，然
后抢劫、杀人、腌制，敲骨吸髓的猎杀幸存者。有趣的是，这帮人一开始真的是在终点
站做慈善的，但之后被一伙不知感恩的坏人绑架关押作为性奴，终于逆袭之后干上了坏
人们的生意。食人一族可以说代表了秩序崩溃的极端情况，这伙人把自己和其他幸存者
视为两个物种，并可以做到毫无顾忌、好无底线的利用他人。这已经超出人与人的关系
了，更像是人与家畜的关系。从这个角度上来说，食人族说得上是代表了霍布斯的“自
然状态”：人人对人人的战争，只不过食人族内部出于策略、血缘的关系，免于相互之
间的战争。

s*r2018-11-06 08:11

6 楼

都是牛人啊。

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

: 根据 US News 2014 排名
: http://grad-schools.usnews.rankingsandreviews.com/best-graduate-schools/top-science-schools/computer-science-rankings
: 注：大陆背景指在中国大陆接受本科教育
: ++++++++++++++++++++++++++++
: #1 Carnegie Mellon University
: - Yiming Yang
: - Eric P. Xing
: - Jian Ma
:
: #1 Massachusetts Institute of Technology

r*e2018-11-06 08:11

7 楼

P？猜不出来

except
我这种小

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

: 说他们问题变态不是盖的，第一轮就两道
: 1. N node的binary tree一共能有几种不同的tree structure，写code，数学公式
: 2. 给int[] in, 生成int[] out, out[i]= product of every element of in except
: in[i]，不能用除号, O(n) time required
: 虽然都是常见题，但我都没见过。两道题都在提示下摸爬滚打的弄出来了。
: P号称面试难度比G,F还大。随便查了查，SE基本都是stanford毕业的。面我的
: 人也算大牛，在stackoverflow上all time reputation排名前50的，也只是普通SE。我这种小
: 虾米就算能过这轮后面肯定也要挂。

R*d2018-11-06 08:11

8 楼

要看医生了吧，如果医生很严的话，最好到国内开个证明，随便一个医院都行，有公章
就可以了

【在 p******r 的大作中提到】

: 我不记得我打过水痘疫苗了没，反正是没出过水痘，能不能就说出过水痘了，这样是不
: 是就不用打了？
: 我看几个人都说，水痘疫苗自己说出过了，就算过了，医生不会验血检查的。。。

m*t2018-11-06 08:11

9 楼

cong!

z*t2018-11-06 08:11

10 楼

这个统计的不全啊

i*92018-11-06 08:11

11 楼

第二题不很变态，常规题

d*g2018-11-06 08:11

12 楼

cong!
顺便问一句，批准的140公司有没有可能撤销，如果撤销了，那个PD以后还能用吗？

C*l2018-11-06 08:11

13 楼

估计一下：70%有买买提ID，40%来这个版，10%披着马甲偶尔发言。

g*e2018-11-06 08:11

14 楼

1. f(n) = sum(f(i) + f(n-1-i)) i=0..n-1 DP做吧
第二题也用dp就行了保存P[0, i]和P[i, n]的值
out[i] = P[0, i-1] x P[i+1, n]
没见过这两题，不知道对不对

except
我这种小

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

g*n2018-11-06 08:11

15 楼

可以revoke。但只要这个revoke不是基于140里面的弄虚作假（显然没有雇主会承认弄
虚作假），不影响keep PD

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

: cong!
: 顺便问一句，批准的140公司有没有可能撤销，如果撤销了，那个PD以后还能用吗？

w*d2018-11-06 08:11

16 楼

这个列表里面很多人的primary appointment 根本不在CS系。有些人根本就是ECE系，
生物医学信息系，或者其它系科的。
应该只列primary appointment在CS系的。因为很多学校的joint appointment给的太容
易太烂（不过也是，反正不付工资，做个人情而已。）

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

r*e2018-11-06 08:11

17 楼

第二题就是pre-processing生成两个partial product array
不符合最优子结构的性质，应该不能叫DP

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

: 1. f(n) = sum(f(i) + f(n-1-i)) i=0..n-1 DP做吧
: 第二题也用dp就行了保存P[0, i]和P[i, n]的值
: out[i] = P[0, i-1] x P[i+1, n]
: 没见过这两题，不知道对不对
:
: except
: 我这种小

d*g2018-11-06 08:11

18 楼

那为什么版上这么多人担心换工作以后，公司会取消140，从而因此失去PD？

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

: 可以revoke。但只要这个revoke不是基于140里面的弄虚作假（显然没有雇主会承认弄
: 虚作假），不影响keep PD

c*82018-11-06 08:11

19 楼

大于 0% joint appointment 就应该算吧
[在 walkaround (settle) 的大作中提到：]
:这个列表里面很多人的primary appointment 根本不在CS系。有些人根本就是ECE系，
:生物医学信息系，或者其它系科的。
:应该只列primary appointment在CS系的。因为很多学校的joint appointment给的太
容易太烂（不过也是，反正不付工资，做个人情而已。）

k*72018-11-06 08:11

20 楼

同问哪里是P？

w*h2018-11-06 08:11

21 楼

Cong

c*82018-11-06 08:11

22 楼

请补充

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

: 这个统计的不全啊

t*n2018-11-06 08:11

23 楼

Paypal?

【在 k*****7 的大作中提到】

: 同问哪里是P？

s*g2018-11-06 08:11

24 楼

Lili Qiu在交大念过一年，不知道算不算。。。

t*e2018-11-06 08:11

25 楼

This one?
http://www.palantir.com/

L*s2018-11-06 08:11

26 楼

谁搞一个ECE的？

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

c*02018-11-06 08:11

27 楼

第一个题貌似是那个Catalan number
第二题两个指针扫一遍就行了
具体参考1337code

C*l2018-11-06 08:11

28 楼

买买提有两啊，哈哈。

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

: 谁搞一个ECE的？

r*u2018-11-06 08:11

29 楼

Palantir很富啊

【在 t*********e 的大作中提到】

: This one?
: http://www.palantir.com/

L*s2018-11-06 08:11

30 楼

有俩啥？

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

: 买买提有两啊，哈哈。

s*i2018-11-06 08:11

31 楼

五角大楼都用他家软件，牛x了

【在 r***u 的大作中提到】

: Palantir很富啊

L*s2018-11-06 08:11

32 楼

王超是刚跳的吧？

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

g*i2018-11-06 08:11

33 楼

第1题： N！种不同Trees, 因为从第一个其添加节点时，可选的位子数分别1， 2，。
。。N。

except
我这种小

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

c*82018-11-06 08:11

34 楼

好几个都是在过去一年里跳的

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

: 王超是刚跳的吧？

f*w2018-11-06 08:11

35 楼

第二题没看懂

s*82018-11-06 08:11

36 楼

Yiming Yang本科哪里？她从来不说。

R*i2018-11-06 08:11

37 楼

不是n!, 我开始以为也是，被面试的人指出错了。还是要用DP做。

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

: 第1题： N！种不同Trees, 因为从第一个其添加节点时，可选的位子数分别1， 2，。
: 。。N。
:
: except
: 我这种小

L*s2018-11-06 08:11

38 楼

人主页的CV上写着呢：太原工学院。1977年毕业。应该是工农兵学员。

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

: Yiming Yang本科哪里？她从来不说。

R*i2018-11-06 08:11

39 楼

1. close, but not quite
2. wrong

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

L*s2018-11-06 08:11

40 楼

好像过去一年大家跳的好多。

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

: 好几个都是在过去一年里跳的

g*s2018-11-06 08:11

41 楼

不能用除号，自己实现个除法行不？

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

: 1. close, but not quite
: 2. wrong

d*a2018-11-06 08:11

42 楼

Kai Li和Wei Zhao也是工农兵学员。那一批人非常厉害，本科在哪里毕业，对他们来说
已经不重要了。

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

: 人主页的CV上写着呢：太原工学院。1977年毕业。应该是工农兵学员。

g*e2018-11-06 08:11

43 楼

指点一下哪错了，至少我运行了几个例子倒没错
/**
* c[i] = A[0]*A[1]*..*A[i]
* d[i] = A[n]*A[n-1]*..*A[i]
*
* and c[0] = a[0], d[n]=a[n];
*
* then B[i] = c[i-1] * d[i+1]
*
* @return b
*/
public static final int[] multiply(int[] a) {
if (a.length==1)
return a;

int n = a.length-1;
int[] b = new int[n+1];
int[] c = new int[n+1];
int[] d = new int[n+1];

c[0] = a[0];
d[n] = a[n];

for (int i=1;i<=n;i++) {
c[i] = c[i-1] * a[i];
d[n-i] = d[n-i+1] * a[n-i];
}

b[0] = d[1];
b[n] = c[n-1];
for (int i=1; i<=n-1; i++) {
b[i] = c[i-1] * d[i+1];
}
return b;
}

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

: 1. close, but not quite
: 2. wrong

C*l2018-11-06 08:11

44 楼

MIT EE有两个大陆出身AP嘛。

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

: 有俩啥？

g*s2018-11-06 08:11

45 楼

没错。直方图也可以用类似的方法来做，比用栈要清楚一些。

指点一下哪错了，至少我运行了几个例子倒没错/** * c[i] = A[0]*A[1]*..*A[i]
★ Sent from iPhone App: iReader Mitbbs 6.8 - iPhone Lite

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

: 指点一下哪错了，至少我运行了几个例子倒没错
: /**
: * c[i] = A[0]*A[1]*..*A[i]
: * d[i] = A[n]*A[n-1]*..*A[i]
: *
: * and c[0] = a[0], d[n]=a[n];
: *
: * then B[i] = c[i-1] * d[i+1]
: *
: * @return b

s*g2018-11-06 08:11

46 楼

Lixia Zhang应该也是

【在 d***a 的大作中提到】

: Kai Li和Wei Zhao也是工农兵学员。那一批人非常厉害，本科在哪里毕业，对他们来说
: 已经不重要了。

g*e2018-11-06 08:11

47 楼

1题typo，应该是
f(n) = sum( f(i) * f(n-1-i) ) i=0..n-1
结果跟catalam number一样
public static final int binaryTreeNum (int n) {
if (n<0) return 0;
if (n==0 || n==1) return 1;

int[] f = new int[n+1];
f[0] = 1;
f[1] = 1;
for (int i=2; i<=n; i++) {
for (int j=0; jf[i] += f[j] * f[i-j-1];
}
}

return f[n];
}

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

: 1. close, but not quite
: 2. wrong

s*g2018-11-06 08:11

48 楼

Associate跳槽成Assistant，图啥。。。。

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

: 王超是刚跳的吧？

g*e2018-11-06 08:11

49 楼

用栈的方法我看了很久以后才自己写对了一个，太绕了

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

: 没错。直方图也可以用类似的方法来做，比用栈要清楚一些。
:
: 指点一下哪错了，至少我运行了几个例子倒没错/** * c[i] = A[0]*A[1]*..*A[i]
: ★ Sent from iPhone App: iReader Mitbbs 6.8 - iPhone Lite

s*g2018-11-06 08:11

50 楼

里面很多是ECE或者Bioinfo的，挂靠在CS
Yizhao Hou是数学的，都算是CS？

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

g*s2018-11-06 08:11

51 楼

那个怎么做？

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

p*g2018-11-06 08:11

52 楼

一个也不认识和没听说过

R*i2018-11-06 08:11

53 楼

这个是对的

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

: 1题typo，应该是
: f(n) = sum( f(i) * f(n-1-i) ) i=0..n-1
: 结果跟catalam number一样
: public static final int binaryTreeNum (int n) {
: if (n<0) return 0;
: if (n==0 || n==1) return 1;
:
: int[] f = new int[n+1];
: f[0] = 1;
: f[1] = 1;

p*g2018-11-06 08:11

54 楼

李凯是李菲菲她爸吧
这都多大岁数了

g*s2018-11-06 08:11

55 楼

http://www.mitbbs.com/article_t1/JobHunting/31816659_0_2.html
32楼

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

: 那个怎么做？

c*82018-11-06 08:11

56 楼

CS本身就是一个不断发展的领域，
只要在CS底下有non-zero percent appointment应该都算吧
Yizhao Hou是计算数学，确实也可以不包括。
但是Caltech比较特别，都属于 Computing & Mathematical Sciences

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

: 里面很多是ECE或者Bioinfo的，挂靠在CS
: Yizhao Hou是数学的，都算是CS？

g*e2018-11-06 08:11

57 楼

这个比用stack简洁多了，学习了

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

: http://www.mitbbs.com/article_t1/JobHunting/31816659_0_2.html
: 32楼

d*a2018-11-06 08:11

58 楼

我读书的时候，计算机系的老教授很多是数学专业出身的。他们读书那个年代，国内还
没有计算机系，也没有计算机专业的毕业生。

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

: CS本身就是一个不断发展的领域，
: 只要在CS底下有non-zero percent appointment应该都算吧
: Yizhao Hou是计算数学，确实也可以不包括。
: 但是Caltech比较特别，都属于 Computing & Mathematical Sciences

B*M2018-11-06 08:11

59 楼

你们咋都这么聪明呢！
我老嫉妒死了都，
你们都看了什么书才看到这样的？

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

c*82018-11-06 08:11

60 楼

是的

【在 d***a 的大作中提到】

: 我读书的时候，计算机系的老教授很多是数学专业出身的。他们读书那个年代，国内还
: 没有计算机系，也没有计算机专业的毕业生。

g*s2018-11-06 08:11

61 楼

原来你以前也没仔细看啊。：）

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

: 这个比用stack简洁多了，学习了

c*82018-11-06 08:11

62 楼

确实不多见

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

: Associate跳槽成Assistant，图啥。。。。

g*i2018-11-06 08:11

63 楼

problem 1 should be changed to that how many tree stuctures of full binary
tree with N node. is correct?

except
我这种小

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

c*82018-11-06 08:11

64 楼

不是

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

: 李凯是李菲菲她爸吧
: 这都多大岁数了

k*72018-11-06 08:11

65 楼

我面过这家，两轮挂掉。。。
第二题pre-processing，用空间换时间。
第一题f(n) = sum( f(i) * f(n-1-i) )怎么构造的？试了试确实正确。求大虾解释下
吧

s*e2018-11-06 08:11

66 楼

我听说过正教授跳成助理的。

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

: Associate跳槽成Assistant，图啥。。。。

g*i2018-11-06 08:11

67 楼

比较好的第推公式是：f(n) =(2*(2n-1)/(n+1))*f(n-1)
f(0) = 1;

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

p*g2018-11-06 08:11

68 楼

从田纳西的正教授跳到MIT的助理，99%的ID都会去吧

【在 s**********e 的大作中提到】

: 我听说过正教授跳成助理的。

g*e2018-11-06 08:11

69 楼

选一个当root，剩下n-1个点组成左子树或者右子树，或者两边都有，如果左子树有i个
节点，那么右子树就剩n-1-i个，所以结果应该是
f(n) = sum( f(i) * f(n-i-1) ) for i=0..n-1
另外有人也提到了，n个点的binary tree的个数是 catalan number
http://en.wikipedia.org/wiki/Catalan_number

【在 k*****7 的大作中提到】

: 我面过这家，两轮挂掉。。。
: 第二题pre-processing，用空间换时间。
: 第一题f(n) = sum( f(i) * f(n-1-i) )怎么构造的？试了试确实正确。求大虾解释下
: 吧

c*82018-11-06 08:11

70 楼

几乎不可能有这样的事情发生吧

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

: 从田纳西的正教授跳到MIT的助理，99%的ID都会去吧

i*e2018-11-06 08:11

71 楼

1 求all b(x), b(x)=在x右边第一比ax小的位置 [b(x)=n+1 if all are larger than
ax] O(n) using DP.
这个如何写递归保证O（n) ？

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

: http://www.mitbbs.com/article_t1/JobHunting/31816659_0_2.html
: 32楼

p*g2018-11-06 08:11

72 楼

所以，除了每日下厨作川菜回锅肉+看两眼八卦电视节目+教孩子识字，还能干什么呢？
反正也就这样了

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

: 几乎不可能有这样的事情发生吧

i*e2018-11-06 08:11

73 楼

这个不对吧。 a[i] < a[i+1] 同时 a[i] 可能小于b[i+1]了。

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

: 选一个当root，剩下n-1个点组成左子树或者右子树，或者两边都有，如果左子树有i个
: 节点，那么右子树就剩n-1-i个，所以结果应该是
: f(n) = sum( f(i) * f(n-i-1) ) for i=0..n-1
: 另外有人也提到了，n个点的binary tree的个数是 catalan number
: http://en.wikipedia.org/wiki/Catalan_number

s*e2018-11-06 08:11

74 楼

Birkhoff 干过这事儿。
他是普林斯顿的FP，然后跳到哈佛去当AP了。

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

: 几乎不可能有这样的事情发生吧

i*e2018-11-06 08:11

75 楼

而且那个帖子说的是应该存位置，存值没有什么用了..

c*82018-11-06 08:11

76 楼

这个听过。100年前的事情了。

【在 s**********e 的大作中提到】

: Birkhoff 干过这事儿。
: 他是普林斯顿的FP，然后跳到哈佛去当AP了。

i*e2018-11-06 08:11

77 楼

我知道你的意思，你的算法是先算b[i+1] 然后算b[i] 对吧？如果a[i] > a[i+1],
那么b[i] = i+1, 这个没错了，但是如果a[i] < a[i+1]的话，我们不能直接得出b[i
] = b[i+1]; 因为b[i+1]那个位置的数只是比a[i+1]小，而这个数可能比a[i]要大，
这样的话我们算b[i]的时候就跟b[i+1]的值没有任何很直接的关系了 , 不知道你的算
法是不是这样的？请指出如果我错了的话

s*e2018-11-06 08:11

78 楼

呵呵，是的。
那会儿估计普林还很烂吧。现在普林和哈佛的数学差距应该不会这么大。

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

: 这个听过。100年前的事情了。

g*e2018-11-06 08:11

79 楼

你说的对，我开始想的太简单了，脑袋不清楚。
不过DP还是可以做的。下面虽然有两重循环，但是数组a最多只会被访问两次，所以依
然是O(n)。
等grass和其它大牛来指正
int[] a = {0, 2, 4, 6, 9, 7, 5, 3, 1};
//int[] a = {1, 3, 5, 4, 1};
int n = a.length;
int[] b = new int[n];
b[n-1] = n;
for (int i=n-2; i>=0; i--) {
if (a[i]>a[i+1])
b[i] = i+1;
else {
int tmp = i+1;
while (b[tmp]= a[i])
tmp = b[tmp];
if(tmp==n)
b[i] = n;
else
b[i] = b[tmp];
}
}

[i
，

【在 i***e 的大作中提到】

: 我知道你的意思，你的算法是先算b[i+1] 然后算b[i] 对吧？如果a[i] > a[i+1],
: 那么b[i] = i+1, 这个没错了，但是如果a[i] < a[i+1]的话，我们不能直接得出b[i
: ] = b[i+1]; 因为b[i+1]那个位置的数只是比a[i+1]小，而这个数可能比a[i]要大，
: 这样的话我们算b[i]的时候就跟b[i+1]的值没有任何很直接的关系了 , 不知道你的算
: 法是不是这样的？请指出如果我错了的话

p*g2018-11-06 08:11

80 楼

哈哈哈，虎肉你太可爱了，笑死我了，哈哈哈

【在 s**********e 的大作中提到】

: 呵呵，是的。
: 那会儿估计普林还很烂吧。现在普林和哈佛的数学差距应该不会这么大。

o*d2018-11-06 08:11

81 楼

哈哈前几天刚写过第2题
先从左到右一遍再从右到左一遍
大致就是
out[0]=1;
out[1]=in[0]；
out[2]=out[1]*in[1]=in[0]*in[1];
out[3]=out[2]*in[2]=in[0]*in[1]*in[2];
...
out[n-1]=out[n-2]*in[n-2]=in[0]*in[1]*in[2]*...*in[n-2];
然后反过来把后半段再乘上就是 (后半段可以用一个temp变量来存,所以也只是O(1)空间)
out[n-1]=out[n-1]*1;
out[n-2]=out[n-1]*(in[n-1]);
out[n-3]=out[n-2]*(in[n-1]*in[n-2]);
out[n-4]=out[n-3]*(in[n-1]*in[n-2]*in[n-3]);
...

except
我这种小

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

h*a2018-11-06 08:11

82 楼

好像现在EE一共有五个大陆出身的faculty

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

: MIT EE有两个大陆出身AP嘛。

i*e2018-11-06 08:11

83 楼

感觉你这个是O(n2)的了，一个简单的例子就是从中位数的之后的元素都是降序的，
这样你的那个while loop 只能每次走一步了，所以每次循环就是linear time 了，
前面的元素如何有n/4个元素进入你这个loop 的话就是O(n2)的time了

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

: 你说的对，我开始想的太简单了，脑袋不清楚。
: 不过DP还是可以做的。下面虽然有两重循环，但是数组a最多只会被访问两次，所以依
: 然是O(n)。
: 等grass和其它大牛来指正
: int[] a = {0, 2, 4, 6, 9, 7, 5, 3, 1};
: //int[] a = {1, 3, 5, 4, 1};
: int n = a.length;
: int[] b = new int[n];
: b[n-1] = n;
: for (int i=n-2; i>=0; i--) {

j*22018-11-06 08:11

84 楼

南加大排名这么高呀，应该还有qianxue hai

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

g*e2018-11-06 08:11

85 楼

我已经给了个例子了，while loop最坏的情况只有第一次进入的时候每次走一步，以后
再进
while的时候，就不可能每次走一步了，因为上一个数对应的index已经跳跃了

以依

【在 i***e 的大作中提到】

:
: 感觉你这个是O(n2)的了，一个简单的例子就是从中位数的之后的元素都是降序的，
: 这样你的那个while loop 只能每次走一步了，所以每次循环就是linear time 了，
: 前面的元素如何有n/4个元素进入你这个loop 的话就是O(n2)的time了

L*s2018-11-06 08:11

86 楼

学海是CE的，不是CS的。
确实很能灌水，师出名门，又是学二代，不是一般屌丝能比的。

【在 j*******2 的大作中提到】

: 南加大排名这么高呀，应该还有qianxue hai

g*s2018-11-06 08:11

87 楼

这是对的。很经典的一个DP问题。
很多人一看2重循环就以为是N*N. 其实不是。这题计算很简单，最大2×N。

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

s*g2018-11-06 08:11

88 楼

爸妈要到啥程度算是学二代
一般教授算不算
还是一定要学海的爸那样的

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

: 学海是CE的，不是CS的。
: 确实很能灌水，师出名门，又是学二代，不是一般屌丝能比的。

g*e2018-11-06 08:11

89 楼

激动啊，得到大牛肯定
不过你前面提到的"c(x)=在x左边最后一个比ax小的位置 c(x)=0 if all are larger
than ax"，我觉得这种情况c(x)=-1
这样后面算最大面积的时候 (b(x)-c(x)-1)*a(x)才正确
比如a={2,3}, b={2,2}, c={-1,0} 最大面积4
贴个完整的代码
public class LargestHistogramRectangleDP {
public static int largestHistogram(int[] a) {
int maxArea = 0;

int n = a.length;
int[] b = new int[n];
int[] c = new int[n];

b[n-1] = n;
for (int i=n-2; i>=0; i--) {
if (a[i]>a[i+1])
b[i] = i+1;
else {
int tmp = i+1;
//keep checking b[i] until find some t such
that a[t]//although there are two loops, each element
in array a will
//be accessed at most two times.
while (b[tmp]= a[i]) {
tmp = b[tmp];

}
b[i] = tmp==n ? n : b[tmp];
}
}

for (int i : b) {
System.out.print(i+" ");
}
System.out.println();

c[0] = -1;
for (int i=1; iif (a[i]>a[i-1])
c[i] = i-1;
else {
int tmp = i-1;
//keep checking c[i] until find some t such
that a[t]while (c[tmp]>=0 && a[c[tmp]]>=a[i])
tmp = c[tmp];
c[i] = tmp==-1 ? -1 : c[tmp];

}
}

for (int i : c) {
System.out.print(i+" ");
}
System.out.println();

int s = 0, e = 0;
for (int i=0; iint tmp = (b[i] - c[i] -1) * a[i];
if (tmp>maxArea) {
maxArea = tmp;
s = c[i] + 1;
e = b[i] - 1;
}
}
System.out.println("max histogram rectangle area is " +
maxArea + ", index starts at " + s + " and ends at " +e);

return maxArea;
}

public static void main(String[] args) {
//int[] a = {1, 3, 5, 4, 1};
int[] a = {0, 2, 4, 6, 9, 7, 5, 3, 1};
//int[] a = {4, 4, 10, 5, 7, 8, -1};
//int [] a = {7, 11, 10, 5, 5,1};

largestHistogram(a);

}
}

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

: 这是对的。很经典的一个DP问题。
: 很多人一看2重循环就以为是N*N. 其实不是。这题计算很简单，最大2×N。

L*s2018-11-06 08:11

90 楼

好歹是个官或者院士之类的吧。

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

: 爸妈要到啥程度算是学二代
: 一般教授算不算
: 还是一定要学海的爸那样的

g*s2018-11-06 08:11

91 楼

我那给点是基于下标1..n
所以才有
[b(x)=n+1 if all are larger than ax]
和
[c(x)=0 if all are larger than ax]
具体实现要用下标0..n-1的话，要做改动。
最近你练得很勤快啊。祝好运！

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

: 激动啊，得到大牛肯定
: 不过你前面提到的"c(x)=在x左边最后一个比ax小的位置 c(x)=0 if all are larger
: than ax"，我觉得这种情况c(x)=-1
: 这样后面算最大面积的时候 (b(x)-c(x)-1)*a(x)才正确
: 比如a={2,3}, b={2,2}, c={-1,0} 最大面积4
: 贴个完整的代码
: public class LargestHistogramRectangleDP {
: public static int largestHistogram(int[] a) {
: int maxArea = 0;
:

j*22018-11-06 08:11

92 楼

平台很高，一般人比不了，前途无量，回头应该可以直接弄个大千回国再拉个队伍了。

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

: 学海是CE的，不是CS的。
: 确实很能灌水，师出名门，又是学二代，不是一般屌丝能比的。

k*72018-11-06 08:11

93 楼

明白了！多谢前辈！

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

c*82018-11-06 08:11

94 楼

这个bar很高

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

: 好歹是个官或者院士之类的吧。

m*q2018-11-06 08:11

95 楼

刚刚看了1337code上的解答，挺精巧的，没看之前
只想到了从头和尾各扫描一遍。
1337code上的链接
http://www.ihas1337code.com/2010/04/multiplication-of-numbers.h

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

: 第一个题貌似是那个Catalan number
: 第二题两个指针扫一遍就行了
: 具体参考1337code

h*d2018-11-06 08:11

96 楼

补充两个知道的人，Lizhong Zheng MIT的eecs professor, Xinyu Zhang University
of Wisconsin-Madison 的ece

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

p*u2018-11-06 08:11

97 楼

请问这个2N怎么来的？如 2 3 4 1 0，至少a[3]这个元素就被access了3次。

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

: 这是对的。很经典的一个DP问题。
: 很多人一看2重循环就以为是N*N. 其实不是。这题计算很简单，最大2×N。

s*e2018-11-06 08:11

98 楼

郑是EE的。

University

【在 h******d 的大作中提到】

: 补充两个知道的人，Lizhong Zheng MIT的eecs professor, Xinyu Zhang University
: of Wisconsin-Madison 的ece

b*82018-11-06 08:11

99 楼

第一个Catalan树，手头推导结果有两种方法。一种先搞递归式，再用组合数学的生成函数，很难记住临时写出。第二种是转换为等价的（）配对计数问题，所有组合数减去不合法的配对，数据结构书上有，也很复杂，但是可以记住。
如果是写程序算，用第一种递归比较好。

C*l2018-11-06 08:11

100 楼

买买提EE目前有三

University

【在 h******d 的大作中提到】

: 补充两个知道的人，Lizhong Zheng MIT的eecs professor, Xinyu Zhang University
: of Wisconsin-Madison 的ece