谢国忠：走向滞胀 (转载) - 未名空间MITBBS历史存档

谢国忠：走向滞胀 (转载)# Stock

l*72010-01-31 08:01

1 楼

刚面过G，从9月份电面到现在一共两个月把所有事情弄完。
电面只有一轮，出了一个之前版上出现过的题，一个string由0，1和？组成，并且？可
以被替换成0或者1，让输出所有的把？替换之后不同的string，比如1？0把？替换之后
能够生成110和100
之后过了三周才接到onsite的通知
onsite一共有4轮，中间午餐
第一轮一上来告诉我一个function的定义和它的功能，然后问了很多test的东西，我也
不懂，就瞎扯，之后让我实现这个function以及它的一个变种，类似就是一个array of
integer，以及一个int，这个int表示一个window的宽度，这个window从array的一开
始滑动到最后，找出来在滑动的过程中每次window中int的和，比如一个array是[1,2,3
,4,5]，然后window的宽度是2，那么就输出[3,5,7,9]
第二轮是给一个int N，让输出所有的长度为N的valid string的个数，valid string的
定义是由A,B,C三种字母组成，并且在这个string中任意连续的三个字母不能包括A,B,C
三个字母，比如BACCA就不是valid string，因为前三个字母B,A,C包含了这三个字母。
我用了一个三维的DP做，但是边界条件没有写好
第三轮特别简单，问了买卖stock那道题，以及在这上面又问了其它一些边边角角的东西
第四轮问了两个题，给一个array of int，以及一个range (low, high)，找出array中
所有的continuos subsequence使得这个subsequence的和在range之中。第二个问题是
grid的题，假设你是harry potter，在grid的左上角，你现在要走到右下角，grid中有
正数也有负数，遇到正数表示你的strength增加那么多，遇到负数表示strength减少那
么多，在任何时刻如果你的strength小于等于0，那么你就挂了。在一开始你有一定的
初始的strength，现在问这个初始的strength最少是多少，才能保证你能够找到一条路
走到右下角
这周hr说送到HC了，求blessing啊！！！！！

N*n2010-01-31 08:01

2 楼

【以下文字转载自 Investment 讨论区】
发信人: Warfare (German==Arschloch), 信区: Investment
标题: 谢国忠：走向滞胀 (转载)
发信站: BBS 未名空间站 (Sun Jan 31 16:43:20 2010, 美东)
发信人: tomnjerry (tom jerry), 信区: WorldNews
标题: 谢国忠：走向滞胀
发信站: BBS 未名空间站 (Sun Jan 31 16:07:21 2010, 美东)
谢国忠：走向滞胀
2010年1月26日
谢国忠
2009年，中国的外汇储备增长4530亿美元，相当于2008年GDP的10%，银行贷款
总额(9.6万亿元人民币)的32%，名义GDP的增长率则为5%。显然，是财政和金融方面的
因素推动了中国的经济增长。这反映了一个现实：全球金融危机之后呈现出了一种全新
的状态，投放到经济中的海量资金，对于GDP增长的贡献颇为可怜。
这些资金基本是通过房地产部门进入经济、发挥作用：2009年新房销售的增量，估
计高于名义GDP。
在泡沫之下，资源被用于制造更多泡沫。这些资

A*c2010-01-31 08:01

3 楼

Bless lz拿到大offer

of
,3

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

: 刚面过G，从9月份电面到现在一共两个月把所有事情弄完。
: 电面只有一轮，出了一个之前版上出现过的题，一个string由0，1和？组成，并且？可
: 以被替换成0或者1，让输出所有的把？替换之后不同的string，比如1？0把？替换之后
: 能够生成110和100
: 之后过了三周才接到onsite的通知
: onsite一共有4轮，中间午餐
: 第一轮一上来告诉我一个function的定义和它的功能，然后问了很多test的东西，我也
: 不懂，就瞎扯，之后让我实现这个function以及它的一个变种，类似就是一个array of
: integer，以及一个int，这个int表示一个window的宽度，这个window从array的一开
: 始滑动到最后，找出来在滑动的过程中每次window中int的和，比如一个array是[1,2,3

N*n2010-01-31 08:01

4 楼

If only Hu & Wen could be half as intelligent as Xie.

f*e2010-01-31 08:01

5 楼

bless 搞定Google！

of
,3

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

: 刚面过G，从9月份电面到现在一共两个月把所有事情弄完。
: 电面只有一轮，出了一个之前版上出现过的题，一个string由0，1和？组成，并且？可
: 以被替换成0或者1，让输出所有的把？替换之后不同的string，比如1？0把？替换之后
: 能够生成110和100
: 之后过了三周才接到onsite的通知
: onsite一共有4轮，中间午餐
: 第一轮一上来告诉我一个function的定义和它的功能，然后问了很多test的东西，我也
: 不懂，就瞎扯，之后让我实现这个function以及它的一个变种，类似就是一个array of
: integer，以及一个int，这个int表示一个window的宽度，这个window从array的一开
: 始滑动到最后，找出来在滑动的过程中每次window中int的和，比如一个array是[1,2,3

g*u2010-01-31 08:01

6 楼

Strongly disagree.
BTW, intelligence is so over-rated.

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

: If only Hu & Wen could be half as intelligent as Xie.

d*n2010-01-31 08:01

7 楼

Bless
HR还不错，说送了HC
我面完后HR只说一周内出消息

P*r2010-01-31 08:01

8 楼

Google 题目还是难啊。
第四个的第一题是用dp算 V[i][j] (i->j continues subsequence sum),然后比较
range吗？

d*k2010-01-31 08:01

9 楼

好久没在线练习了，写个valid string，欢迎斧正
// assume n >= 3 for simplicity
int valid_string(int n) {
int rec[2][3][3];
for (int i = 0; i < 3; ++i) {
for (int j = 0; j < 3; ++j) {
rec[2&1][i][j] = 1;
}
}
for (int i = 3; i <= n; ++i) {
for (int x = 0; x < 3; ++x) {
rec[i&1][x][x] = sum(rec[(i-1)&1][x], rec[(i-1)&1][x] + 3);
int y = (x+1) % 3;
int z = (x+2) % 3;
rec[i&1][x][y] = sum(rec[(i-1)&1][y], rec[(i-1)&1][y] + 3) - rec
[(i-1)&1][y][z];
rec[i&1][x][z] = sum(rec[(i-1)&1][z], rec[(i-1)&1][z] + 3) - rec
[(i-1)&1][z][y];
}
}
return sum(*rec[n&1], *rec[n&1] + 9);
}

A*o2010-01-31 08:01

10 楼

valid string这题蛮有意思的, 也许可以简化为二维的dp, 写个思路供大家拍砖:
dp[i][x] 表示了下标位置为i 以字符 x (x = A B C) 结尾的valid string个数
有递推式
dp[i]['A'] = (dp[i-1]['B'] - dp[i-2]['C']) + (dp[i-1]['C'] - dp[i-2]['B'])
+ dp[i-1]['A']
上式的原理不难理解,类似容斥原理吧
初始条件可以为
dp[0]['A'] = dp[0]['B'] = dp[0]['C'] = 1;
dp[1]['A'] = dp[1]['B'] = dp[1]['C'] = 3;
最终答案取 dp[n]['A'] + dp[n]['B'] + dp[n]['C']
实现上我觉得直接开 dp[N][255]数组好了,省得计算下标,面试实现比较容易
本质上可能跟楼上的牛牛解法是一样的, 不过确实没读懂....
Bless lz 成功:)

c*p2010-01-31 08:01

11 楼

mark

j*r2010-01-31 08:01

12 楼

bless楼主拿到大offer!

c*e2010-01-31 08:01

13 楼

bless

z*s2010-01-31 08:01

14 楼

bless，顺便问一句，怎么你面的全是算法题？和面的组有关系吗？

j*62010-01-31 08:01

15 楼

bless
下下周面 (蛋疼的thanksgiving 下周面不了) 同求bless
lz 是 new grad 吗？好像new grad 都是算法题？
你每一轮多长时间？我是 9:45 - 2:00 也能是四轮吗？还是三轮？

k*62010-01-31 08:01

16 楼

第四轮的那个一个array of int，以及一个range (low, high)，什么解法比较好呢？
我想先把array sort了再两头2 pointers往中间走，选出within range 的subsequence
, 靠谱吗？

d*k2010-01-31 08:01

17 楼

第四轮的两道题求澄清：
1. array里面是否可能出现负数？
2. Harry potter是否只能向右或向下走？
祝楼主好运

m*m2010-01-31 08:01

18 楼

bless

t*y2010-01-31 08:01

19 楼

同迷惑：什么叫continuous subsequence sum? 是两个index之前所有元素的和吗？
我的解法是两个pointer, 一个st 一个en,
int st = 0;
int en = -1;
int count = 0;
while(en < A.length){
// move en forward
while(count < low){
en++;
count += A[en];
}
while(count <= high){
addSequence(A,st,en);
en++;
count += A[en];
}
// move st forward
while(count > high){
count -= A[st];
st++;
}
while(count >= low){
addSequence(A,st,en);
st++;
count -= A[st];
}
}

subsequence

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

: 第四轮的那个一个array of int，以及一个range (low, high)，什么解法比较好呢？
: 我想先把array sort了再两头2 pointers往中间走，选出within range 的subsequence
: , 靠谱吗？

l*y2010-01-31 08:01

20 楼

blessing!!

z*s2010-01-31 08:01

21 楼

好心人给说一下吧。。。现在就算法还行，TC有1700。但其他设计，OO什么的都基本上
就没认真学，现在也忘光了，不知道有没有面试只考算法的？

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

: bless，顺便问一句，怎么你面的全是算法题？和面的组有关系吗？

l*72010-01-31 08:01

22 楼

我是new grad general招的，面的时候没有具体组，面我的人也来自不同的组

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

: bless，顺便问一句，怎么你面的全是算法题？和面的组有关系吗？

l*72010-01-31 08:01

23 楼

面试官说不能sort，因为要输出range，如果sort了那index就乱掉了
最好的方法是用一个prefix sum array吧

subsequence

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

: 第四轮的那个一个array of int，以及一个range (low, high)，什么解法比较好呢？
: 我想先把array sort了再两头2 pointers往中间走，选出within range 的subsequence
: , 靠谱吗？

l*72010-01-31 08:01

24 楼

1.可以出现负数
2.只能往右或者往下走

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

: 第四轮的两道题求澄清：
: 1. array里面是否可能出现负数？
: 2. Harry potter是否只能向右或向下走？
: 祝楼主好运

d*e2010-01-31 08:01

25 楼

不明白valid string为啥要dp
直接用两个数记录前一个位置上，相同两个字母结尾的为a,不同字母结尾的为b
这样迭代一下
a = a +b;
b = 2*a+b;
初始值为长度为2，所以a=3,b=6，不就可以了吗

of
,3

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

: 刚面过G，从9月份电面到现在一共两个月把所有事情弄完。
: 电面只有一轮，出了一个之前版上出现过的题，一个string由0，1和？组成，并且？可
: 以被替换成0或者1，让输出所有的把？替换之后不同的string，比如1？0把？替换之后
: 能够生成110和100
: 之后过了三周才接到onsite的通知
: onsite一共有4轮，中间午餐
: 第一轮一上来告诉我一个function的定义和它的功能，然后问了很多test的东西，我也
: 不懂，就瞎扯，之后让我实现这个function以及它的一个变种，类似就是一个array of
: integer，以及一个int，这个int表示一个window的宽度，这个window从array的一开
: 始滑动到最后，找出来在滑动的过程中每次window中int的和，比如一个array是[1,2,3

z*s2010-01-31 08:01

26 楼

谢啦，我是算法还行，其他设计，OO什么的就一塌糊涂了，如果只面算法和coding就太
好了。bless~

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

: 我是new grad general招的，面的时候没有具体组，面我的人也来自不同的组

P*r2010-01-31 08:01

27 楼

赞一个，简单明了。
原则上也算一维dp吧。

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

: 不明白valid string为啥要dp
: 直接用两个数记录前一个位置上，相同两个字母结尾的为a,不同字母结尾的为b
: 这样迭代一下
: a = a +b;
: b = 2*a+b;
: 初始值为长度为2，所以a=3,b=6，不就可以了吗
:
: of
: ,3

H*a2010-01-31 08:01

28 楼

valid string是否是每增加一位，多出来的个数为3*3（末两位相同的情况*可以添加的
char的种类）+6*2（末两位不同的情况*可以添加的char的种类）

w*72010-01-31 08:01

29 楼

did anyone solve the harry potter question? please post your thoughts.

b*62010-01-31 08:01

30 楼

n(i, j) = max(0, min(n(i+1,j), n(i,j+1)) - input(i,j))
min(n(i+1,j), n(i,j+1)) 这步一个出界的话直接取另一个。两个都出界（右下角）这
项取0。
最后返回n(0,0)

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

: did anyone solve the harry potter question? please post your thoughts.

w*72010-01-31 08:01

31 楼

it does not look right. If every value in the matrix is negative, your
answer would be 0 which is apprently not correct.
I am struggling with how we can keep track of a path with least negative
values. Greedy algorithm here is not going to give us the right answer.

【在 b*****6 的大作中提到】

: n(i, j) = max(0, min(n(i+1,j), n(i,j+1)) - input(i,j))
: min(n(i+1,j), n(i,j+1)) 这步一个出界的话直接取另一个。两个都出界（右下角）这
: 项取0。
: 最后返回n(0,0)

g*e2010-01-31 08:01

32 楼

不错
有时候题目刷多了基本的数学反而忘了

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

: 不明白valid string为啥要dp
: 直接用两个数记录前一个位置上，相同两个字母结尾的为a,不同字母结尾的为b
: 这样迭代一下
: a = a +b;
: b = 2*a+b;
: 初始值为长度为2，所以a=3,b=6，不就可以了吗
:
: of
: ,3

l*n2010-01-31 08:01

33 楼

应该是
n(i,j) = input(i, j) + max(n(i-1, j), n(i, j-1)), -infinite if out of range
每个位置表示到当前位置的最多剩余。
给出n matrix之后从右下角开始找，每次都选bigger predecessor，一直走到左上角。
过程当中的最小值就是初始时要持有的strength。
比如
00 -3 -6 -1
-5 -2 -5 -9
-4 -1 -4 -1
-1 -2 -6 -1
要得到的是
00 -3 -9 -10
-5 -5 -10 -19
-9 -6 -10 -11
-10 -8 -14 -12
走法就是-12>>-11>>-10>>-6>>-5>>-3>>00

【在 b*****6 的大作中提到】

: n(i, j) = max(0, min(n(i+1,j), n(i,j+1)) - input(i,j))
: min(n(i+1,j), n(i,j+1)) 这步一个出界的话直接取另一个。两个都出界（右下角）这
: 项取0。
: 最后返回n(0,0)

w*72010-01-31 08:01

34 楼

what you proposed is a greedy algorithm - at every step, you choose a better
move, but overall, the path may not be the best. The best path is the one
has least amount of negative value through the whole path.

range

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

: 应该是
: n(i,j) = input(i, j) + max(n(i-1, j), n(i, j-1)), -infinite if out of range
: 每个位置表示到当前位置的最多剩余。
: 给出n matrix之后从右下角开始找，每次都选bigger predecessor，一直走到左上角。
: 过程当中的最小值就是初始时要持有的strength。
: 比如
: 00 -3 -6 -1
: -5 -2 -5 -9
: -4 -1 -4 -1
: -1 -2 -6 -1

z*52010-01-31 08:01

35 楼

能不能先从index 0开始，把后面的element一个个加起来，sum在range内就记录，不然
就继续，直加到array结尾。然后从index 1开始，重复以上步骤。总共时间是O(n^2)，
貌似和prefix sum array一样，而且不用额外space啊。或者说prefix sum array能做
出优于O(n^2)的解法？
不过既然是找出所有subarray，感觉遍历一遍所有subarray还是必要的，这样下限是不
是就只能是O(n^2)了？

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

: 面试官说不能sort，因为要输出range，如果sort了那index就乱掉了
: 最好的方法是用一个prefix sum array吧
:
: subsequence

l*n2010-01-31 08:01

36 楼

确实，greedy思路走岔了，不过在考虑greedy accu怎么着路径的时候发现必须要有两
个matrix来dp，一个是accu，一个是pathmin。
accu(i, j)=pathmin(i-1, j)>pathmin(i, j-1)?
accu(i-1, j)+input(i, j):
accu(i, j-1)+input(i, j);
pathmin(i， j)=pathmin(i-1, j)>pathmin(i, j-1)?
min(pathmin(i-1, j), accu(i, j)):
min(pathmin(i, j-1), accu(i, j));

better

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

: what you proposed is a greedy algorithm - at every step, you choose a better
: move, but overall, the path may not be the best. The best path is the one
: has least amount of negative value through the whole path.
:
: range

w*72010-01-31 08:01

37 楼

Every path has a min and it is path dependent. I doubt you can dp the path
min as you proposed.
The brutal force solution:
1. In an m x n matrix, we know how many unique path exits. Easy
2. Iterate each path, find its path min, pm. Easy.
3. Find min of all pm[0, ... N], minpm. Easy.
4. If minpm is less than zero, abs(minpm) is the answer, otherwise, zero is
the answer.
The real challenge is: how can we do it faster?? Localized optimization (
greedy) is not a solution.

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

: 确实，greedy思路走岔了，不过在考虑greedy accu怎么着路径的时候发现必须要有两
: 个matrix来dp，一个是accu，一个是pathmin。
: accu(i, j)=pathmin(i-1, j)>pathmin(i, j-1)?
: accu(i-1, j)+input(i, j):
: accu(i, j-1)+input(i, j);
: pathmin(i， j)=pathmin(i-1, j)>pathmin(i, j-1)?
: min(pathmin(i-1, j), accu(i, j)):
: min(pathmin(i, j-1), accu(i, j));
:
: better

l*n2010-01-31 08:01

38 楼

这样来分析吧。假设我们用brutal force方法解了问题，那么我们能够知道走到最右下
角时符合题设的路径中的最低strength。能对最右下角做，也就能对任何坐标点做。假
设现在知道了pathmin(i, j-1)和pathmin(i-1,j)，也就是当坐标的左边和上边，那为
了走到当前坐标会如何走？进当前坐标格只有两个入口，或者左或者上，显然选的是
pathmin高的那个。一旦入口选定了，当前坐标的累计值accu就决定了，然后当前坐标
格的pathmin也就决定了。
这里pathmin不是记录的某个path的最低streng，而是所有能走到当前坐标格的路径中
最优路径的最低accu值。

is

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

: Every path has a min and it is path dependent. I doubt you can dp the path
: min as you proposed.
: The brutal force solution:
: 1. In an m x n matrix, we know how many unique path exits. Easy
: 2. Iterate each path, find its path min, pm. Easy.
: 3. Find min of all pm[0, ... N], minpm. Easy.
: 4. If minpm is less than zero, abs(minpm) is the answer, otherwise, zero is
: the answer.
: The real challenge is: how can we do it faster?? Localized optimization (
: greedy) is not a solution.

w*72010-01-31 08:01

39 楼

Sorry I am not convinced even though I feel what you said have merit. Can
you post your code?
By the way, I feel this is like a directed graph. The starting point from
top left is important. For example, if you have a path such as 1->1->1->1->(
-5)->0
the required initial strength is 2. Your solution seems overlooked the
contribution of cell value to a path min, if I am not mistaken.

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

: 这样来分析吧。假设我们用brutal force方法解了问题，那么我们能够知道走到最右下
: 角时符合题设的路径中的最低strength。能对最右下角做，也就能对任何坐标点做。假
: 设现在知道了pathmin(i, j-1)和pathmin(i-1,j)，也就是当坐标的左边和上边，那为
: 了走到当前坐标会如何走？进当前坐标格只有两个入口，或者左或者上，显然选的是
: pathmin高的那个。一旦入口选定了，当前坐标的累计值accu就决定了，然后当前坐标
: 格的pathmin也就决定了。
: 这里pathmin不是记录的某个path的最低streng，而是所有能走到当前坐标格的路径中
: 最优路径的最低accu值。
:
: is

l*n2010-01-31 08:01

40 楼

我在调试，一会儿post。
你这个1>>1>>1>>1>>-5>>0的情况，对应的accu是1>>2>>3>>4>>-1>>-1，
而pathmin是1>>1>>1>>1>>-1>>-1，应该是对的。

>(

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

: Sorry I am not convinced even though I feel what you said have merit. Can
: you post your code?
: By the way, I feel this is like a directed graph. The starting point from
: top left is important. For example, if you have a path such as 1->1->1->1->(
: -5)->0
: the required initial strength is 2. Your solution seems overlooked the
: contribution of cell value to a path min, if I am not mistaken.

l*n2010-01-31 08:01

41 楼

前面的递归还少了左方和上方pathmin相等时的处理。
下面的code我还用brutal force的比较过，用http://stackoverflow.com/questions/5498130/bit-manipulationprint-the-next-smallest-and-largest-numbers-with-same-no-of-1-b的nexthi_same_count_ones生成每个路径的01表示，两者能够match上。左方和上方pathmin相等时的情况就是用brutal force发现的。
int initStr(int[][] mat) {
assert (mat != null && mat.length > 0 && mat[0].length > 0);
int m = mat.length;
int n = mat[0].length;

int[][] accu = new int[m][n]; //cumulative
int[][] pathmin = new int[m][n];
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (i == 0 && j == 0) { //boundary part 1: [0, 0]
accu[i][j] = 0;
pathmin[i][j] = 0;
continue;
}
//boundary part 2: left or up predecessor out of bound
int lefmin = j - 1 >= 0 ? pathmin[i][j - 1] : Integer.MIN_VALUE;
int upmin = i - 1 >= 0 ? pathmin[i - 1][j] : Integer.MIN_VALUE;
if (lefmin > upmin) {
accu[i][j] = accu[i][j - 1] + mat[i][j];
} else if (lefmin < upmin) {
accu[i][j] = accu[i - 1][j] + mat[i][j];
} else {
//greedy when paths to left and up have the same min
accu[i][j] = Math.max(accu[i][j - 1], accu[i - 1][j])
+ mat[i][j];
}
//update pathmin at [i, j]
pathmin[i][j] = lefmin > upmin ? Math.min(lefmin, accu[i][j])
: Math.min(upmin, accu[i][j]);
}
}

//return 0 if pathmin is always positive
return pathmin[m - 1][n - 1] <= 0 ? -pathmin[m - 1][n - 1] +1 : 0;
}

>(

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

: Sorry I am not convinced even though I feel what you said have merit. Can
: you post your code?
: By the way, I feel this is like a directed graph. The starting point from
: top left is important. For example, if you have a path such as 1->1->1->1->(
: -5)->0
: the required initial strength is 2. Your solution seems overlooked the
: contribution of cell value to a path min, if I am not mistaken.

w*72010-01-31 08:01

42 楼

Now I can comprehend your solution and I am with you 100%.
Using 2D array to dp is very easy to understand, but to use 1D array with
one extra element (m+1 or n+1) is much easy to write code as you don't need
boundary condition check.
Thanks a bunch!

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

: 前面的递归还少了左方和上方pathmin相等时的处理。
: 下面的code我还用brutal force的比较过，用http://stackoverflow.com/questions/5498130/bit-manipulationprint-the-next-smallest-and-largest-numbers-with-same-no-of-1-b的nexthi_same_count_ones生成每个路径的01表示，两者能够match上。左方和上方pathmin相等时的情况就是用brutal force发现的。
: int initStr(int[][] mat) {
: assert (mat != null && mat.length > 0 && mat[0].length > 0);
: int m = mat.length;
: int n = mat[0].length;
:
: int[][] accu = new int[m][n]; //cumulative
: int[][] pathmin = new int[m][n];
: for (int i = 0; i < m; i++) {

l*b2010-01-31 08:01

43 楼

if (lefmin > upmin) {
accu[i][j] = accu[i][j - 1] + mat[i][j];
} else if (lefmin < upmin) {
accu[i][j] = accu[i - 1][j] + mat[i][j];
}
上面两个if／else不是很明白，感觉不能推出上面两个吧。。请问你这个pathmin和
accu分别代表啥？

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

: 前面的递归还少了左方和上方pathmin相等时的处理。
: 下面的code我还用brutal force的比较过，用http://stackoverflow.com/questions/5498130/bit-manipulationprint-the-next-smallest-and-largest-numbers-with-same-no-of-1-b的nexthi_same_count_ones生成每个路径的01表示，两者能够match上。左方和上方pathmin相等时的情况就是用brutal force发现的。
: int initStr(int[][] mat) {
: assert (mat != null && mat.length > 0 && mat[0].length > 0);
: int m = mat.length;
: int n = mat[0].length;
:
: int[][] accu = new int[m][n]; //cumulative
: int[][] pathmin = new int[m][n];
: for (int i = 0; i < m; i++) {

l*n2010-01-31 08:01

44 楼

accu(accumulate)如其名字，是记录最优的path走到当前位置的累计值。
pathmin是走到当前位置的最优路径的最小accu值，假设路径上input矩阵的值是2>>5>>
-3>>-2>>4>>2的话，accu就是2>>7>>4>>2>>6>>8，而一路上pathmin的值是2>>2>>2>>2>
>2>>2。
这里ifelse的逻辑就是，进入某一个位置只能是从左边或者上边的cell，左边cell的
pathmin值比上边的pathmin要高的话，初始需要的strength就更低，所以从左边进入当
前cell。

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

: if (lefmin > upmin) {
: accu[i][j] = accu[i][j - 1] + mat[i][j];
: } else if (lefmin < upmin) {
: accu[i][j] = accu[i - 1][j] + mat[i][j];
: }
: 上面两个if／else不是很明白，感觉不能推出上面两个吧。。请问你这个pathmin和
: accu分别代表啥？

l*b2010-01-31 08:01

45 楼

虽然左边的pathmin比较高，但是上边的accu可能比较大。比如：左边的pathmin比较大
，但是accu是10，上边的accu是20，当前cell的stength是－15，这时候要选上边的吧？

>>
2>

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

: accu(accumulate)如其名字，是记录最优的path走到当前位置的累计值。
: pathmin是走到当前位置的最优路径的最小accu值，假设路径上input矩阵的值是2>>5>>
: -3>>-2>>4>>2的话，accu就是2>>7>>4>>2>>6>>8，而一路上pathmin的值是2>>2>>2>>2>
: >2>>2。
: 这里ifelse的逻辑就是，进入某一个位置只能是从左边或者上边的cell，左边cell的
: pathmin值比上边的pathmin要高的话，初始需要的strength就更低，所以从左边进入当
: 前cell。

G*m2010-01-31 08:01

46 楼

min大但是accu小不能保证superior, 应该都保留吧
0 -5 10
0 0 0
0 0 -6
和
0 -5 10
0 0 0
0 0 -4
的解是不一样的

>>
2>

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

: accu(accumulate)如其名字，是记录最优的path走到当前位置的累计值。
: pathmin是走到当前位置的最优路径的最小accu值，假设路径上input矩阵的值是2>>5>>
: -3>>-2>>4>>2的话，accu就是2>>7>>4>>2>>6>>8，而一路上pathmin的值是2>>2>>2>>2>
: >2>>2。
: 这里ifelse的逻辑就是，进入某一个位置只能是从左边或者上边的cell，左边cell的
: pathmin值比上边的pathmin要高的话，初始需要的strength就更低，所以从左边进入当
: 前cell。

m*s2010-01-31 08:01

47 楼

Bless

of
,3

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

: 刚面过G，从9月份电面到现在一共两个月把所有事情弄完。
: 电面只有一轮，出了一个之前版上出现过的题，一个string由0，1和？组成，并且？可
: 以被替换成0或者1，让输出所有的把？替换之后不同的string，比如1？0把？替换之后
: 能够生成110和100
: 之后过了三周才接到onsite的通知
: onsite一共有4轮，中间午餐
: 第一轮一上来告诉我一个function的定义和它的功能，然后问了很多test的东西，我也
: 不懂，就瞎扯，之后让我实现这个function以及它的一个变种，类似就是一个array of
: integer，以及一个int，这个int表示一个window的宽度，这个window从array的一开
: 始滑动到最后，找出来在滑动的过程中每次window中int的和，比如一个array是[1,2,3

j*62010-01-31 08:01

48 楼

求大牛讲解一下第四题 substring range 的解法
再贴一个第四题第二问哈利波特的 2D dp 解法求大神看看有什么问题
public static int smallestStrengthValue(int[][] grid){
if( grid == null || grid.length == 0 ||
grid[0] == null || grid[0].length == 0){
throw new IllegalArgumentException("State of grid is illegal!");
}

int row = grid.length;
int col = grid[0].length;
int[][] max = new int[row][col];
for(int i = 0; i < row; i++){
for(int j = 0; j < col; j++){
int left = j > 0 ? max[i][j - 1] : Integer.MIN_VALUE;
int upper = i > 0 ? max[i - 1][j] : Integer.MIN_VALUE;
if(left == Integer.MIN_VALUE && upper == Integer.MIN_VALUE){
max[i][j] = grid[i][j];
}else{
max[i][j] = grid[i][j] + Math.max(left, upper);
}
}
}

if(max[row - 1][col - 1] >= 0){
return 0;
}else{
return -max[row - 1][col - 1];
}
}

w*s2010-01-31 08:01

49 楼

能举例子展开讲讲? 没看明白

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

: 不明白valid string为啥要dp
: 直接用两个数记录前一个位置上，相同两个字母结尾的为a,不同字母结尾的为b
: 这样迭代一下
: a = a +b;
: b = 2*a+b;
: 初始值为长度为2，所以a=3,b=6，不就可以了吗
:
: of
: ,3

l*n2010-01-31 08:01

50 楼

你是对的，楼上楼也提到pathmin跟accu的冲突，我原来想的错误比较是用pathmin[i,
j-1]跟pathmin[i-1, j]，即便修正为比较"考虑了accu的"从上面和左边进入的两个假
想pathmin，也无法解决局部和全局的问题。每次比较进入[i,j]的两个假想的pathmin
，也可能会错过全局的最优，因为可能存在的情况是某个在中途不是给出最优pathmin
的路径反而能给出全局最优。
一个反例就是
6 -12 4 13
-1 -9 5 -3
-5 -11 -16 -17
-8 -13 5 -8
每次都要求进入当前位置的pathmin为最优导致选择-1 -9 5 ...的路径，其pathmin是-
1 -10 -10，但是在5的位置accu是-5，而brutal force给出的路径是-12 4 5...，在5
位置的accu是-3，而其pathmin是-12 -12 -12...。
这种局部最优策略跟全局最优的冲突，极端起来怕是每一处都需要走两条线。看来这个
harry potter的题目只能brutal force了。

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

: min大但是accu小不能保证superior, 应该都保留吧
: 0 -5 10
: 0 0 0
: 0 0 -6
: 和
: 0 -5 10
: 0 0 0
: 0 0 -4
: 的解是不一样的
:

p*e2010-01-31 08:01

51 楼

Potter那道题我的解法是这样的：
Keep一个neededStrength array，NS[N][N], NS[N-1][N-1] = 0,
NS[i][j] = min(NS[i+1][j], NS[i][j+1]) - strength[i][j]. If NS[i][j] < 0, NS
[i][j] = 0
return: NS[0][0] + 1, if NS[0][0] > 0, otherwise return 0.

p*e2010-01-31 08:01

52 楼

Subarray sum那道题，我觉得如果O(n^2)可以的话，有至少2种解法，prefix sum
array，或是一个2D DP, 其实本质都一样。
有没有大牛说说优于O(n^2)的解法？

l*u2010-01-31 08:01

53 楼

bless

S*e2010-01-31 08:01

54 楼

谢谢分享！祝你好运！

r*o2010-01-31 08:01

55 楼

大牛，这答案是不是有个小小问题？
因为以A结尾的dp[i]['A']还包括 substring（0，[i-1]）不是valid string的情况。
比如0， i-1 只包含b，c 这两个字符。所以是不是还是要3维dp？

【在 A*****o 的大作中提到】

: valid string这题蛮有意思的, 也许可以简化为二维的dp, 写个思路供大家拍砖:
: dp[i][x] 表示了下标位置为i 以字符 x (x = A B C) 结尾的valid string个数
: 有递推式
: dp[i]['A'] = (dp[i-1]['B'] - dp[i-2]['C']) + (dp[i-1]['C'] - dp[i-2]['B'])
: + dp[i-1]['A']
: 上式的原理不难理解,类似容斥原理吧
: 初始条件可以为
: dp[0]['A'] = dp[0]['B'] = dp[0]['C'] = 1;
: dp[1]['A'] = dp[1]['B'] = dp[1]['C'] = 3;
: 最终答案取 dp[n]['A'] + dp[n]['B'] + dp[n]['C']

P*92010-01-31 08:01

56 楼

多谢！祝拿到0ffer！

w*s2010-01-31 08:01

57 楼

Harry Potter是二分搜索答案，对于每个答案，用DP判断是否可行。
一开始随便找一条路设初始值。

,
pathmin
pathmin

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

: 你是对的，楼上楼也提到pathmin跟accu的冲突，我原来想的错误比较是用pathmin[i,
: j-1]跟pathmin[i-1, j]，即便修正为比较"考虑了accu的"从上面和左边进入的两个假
: 想pathmin，也无法解决局部和全局的问题。每次比较进入[i,j]的两个假想的pathmin
: ，也可能会错过全局的最优，因为可能存在的情况是某个在中途不是给出最优pathmin
: 的路径反而能给出全局最优。
: 一个反例就是
: 6 -12 4 13
: -1 -9 5 -3
: -5 -11 -16 -17
: -8 -13 5 -8

p*y2010-01-31 08:01

58 楼

没看懂，能否详细讲讲？

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

: Harry Potter是二分搜索答案，对于每个答案，用DP判断是否可行。
: 一开始随便找一条路设初始值。
:
: ,
: pathmin
: pathmin

w*s2010-01-31 08:01

59 楼

给定初始strength，用DP算出能否到达右下角，DP的状态是到达每一个点的strength的
最大值，此算法输入是strength，输出是yes or no。
随便找一条路就能得到一个可以走到右下角的strength（S），在0 - S范围里二分搜索
，反复调用DP算法，找到最小的返回yes的strength就可以了。

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

: 没看懂，能否详细讲讲？

e*r2010-01-31 08:01

60 楼

最后一个题意不明，如果是“保证”，是不是应该求负得最多的那条路？

of
,3

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

: 刚面过G，从9月份电面到现在一共两个月把所有事情弄完。
: 电面只有一轮，出了一个之前版上出现过的题，一个string由0，1和？组成，并且？可
: 以被替换成0或者1，让输出所有的把？替换之后不同的string，比如1？0把？替换之后
: 能够生成110和100
: 之后过了三周才接到onsite的通知
: onsite一共有4轮，中间午餐
: 第一轮一上来告诉我一个function的定义和它的功能，然后问了很多test的东西，我也
: 不懂，就瞎扯，之后让我实现这个function以及它的一个变种，类似就是一个array of
: integer，以及一个int，这个int表示一个window的宽度，这个window从array的一开
: 始滑动到最后，找出来在滑动的过程中每次window中int的和，比如一个array是[1,2,3

m*n2010-01-31 08:01

61 楼

把prefix sum sort 一下，找到大的减小的在规定范围内，就是线性问题了。
当然要检查大的是更多的数的和。这样是O(nlogn)。

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

: Subarray sum那道题，我觉得如果O(n^2)可以的话，有至少2种解法，prefix sum
: array，或是一个2D DP, 其实本质都一样。
: 有没有大牛说说优于O(n^2)的解法？

g*g2010-01-31 08:01

62 楼

dek问到点子了。
我觉得应该需要这个条件。
1）假设没有负数
先构建一个数组 sum
sum[i] = Sigma(A[0]+...+A[i])
求此序列
foreach(A[i])
{
lower index sum[j] >= lowerbond - sum[i]
upper index sum[k] <= upperbond - sum[i]
（j，k）为所求
}
NlogN
2）假设只能右或者下
先把（0，0）设置为0
相当于找到一条左上到又下的最大和路径，可DP
路径中abs（最小值) 就是所求
m*n + （m+n）

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

: 第四轮的两道题求澄清：
: 1. array里面是否可能出现负数？
: 2. Harry potter是否只能向右或向下走？
: 祝楼主好运

A*c2010-01-31 08:01

63 楼

大家有没有试过，第二题用dfs+剪枝可以写出很简练的代码。同时可以方便得生成合法
的字符串。

of
,3

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

: 刚面过G，从9月份电面到现在一共两个月把所有事情弄完。
: 电面只有一轮，出了一个之前版上出现过的题，一个string由0，1和？组成，并且？可
: 以被替换成0或者1，让输出所有的把？替换之后不同的string，比如1？0把？替换之后
: 能够生成110和100
: 之后过了三周才接到onsite的通知
: onsite一共有4轮，中间午餐
: 第一轮一上来告诉我一个function的定义和它的功能，然后问了很多test的东西，我也
: 不懂，就瞎扯，之后让我实现这个function以及它的一个变种，类似就是一个array of
: integer，以及一个int，这个int表示一个window的宽度，这个window从array的一开
: 始滑动到最后，找出来在滑动的过程中每次window中int的和，比如一个array是[1,2,3

A*c2010-01-31 08:01

64 楼

为什么我觉得第二题就是一个dp，从（M-1，N-1)往（0，0）规划如下
dp[i][j] = max(dp[i+1][j], dp[i][j+1]) + A[i][j];
结果就是
return dp[0][0] < 0 ? -dp[0][0] : 0;
和Leetcode里边的unique path没区别，就是方向反了而已，
Did I miss anything?

of
,3

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

: 刚面过G，从9月份电面到现在一共两个月把所有事情弄完。
: 电面只有一轮，出了一个之前版上出现过的题，一个string由0，1和？组成，并且？可
: 以被替换成0或者1，让输出所有的把？替换之后不同的string，比如1？0把？替换之后
: 能够生成110和100
: 之后过了三周才接到onsite的通知
: onsite一共有4轮，中间午餐
: 第一轮一上来告诉我一个function的定义和它的功能，然后问了很多test的东西，我也
: 不懂，就瞎扯，之后让我实现这个function以及它的一个变种，类似就是一个array of
: integer，以及一个int，这个int表示一个window的宽度，这个window从array的一开
: 始滑动到最后，找出来在滑动的过程中每次window中int的和，比如一个array是[1,2,3

A*c2010-01-31 08:01

65 楼

“才能保证你能够找到一条路走到右下角”
这不是说了找到一条路就行吗，没说要求任意一条路，对吧。

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

: 最后一个题意不明，如果是“保证”，是不是应该求负得最多的那条路？
:
: of
: ,3

n*s2010-01-31 08:01

66 楼

validation string DP (2d)
M[CurrentLength, Last2Index]
Last2Index:
0: AA
1: AB
..
8: CC
M[i+1, 0 - 9] is depends on M[i, 0 - 9]
也可以用两个数组pre, current来简化
pre=[1,1,1,1,1,1,1,1,1]
for(j = 3 to n)
cur= [0]*9
for i = 0 to 8
tmp = pre[i] +1
switch(i)
case 0 :
cur[0]+= tmp // AA -> AAA
cur[1]+= tmp // AA => AAB
cur[2]+= tmp // AA => AAC
break;
case 1:
cur[4]+=tmp //AB -> ABA
cur[3]+=tmp //AB => ABB
...
pre = cur
final_result = sumup (pre[i])

l*62010-01-31 08:01

67 楼

Re

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

: 给定初始strength，用DP算出能否到达右下角，DP的状态是到达每一个点的strength的
: 最大值，此算法输入是strength，输出是yes or no。
: 随便找一条路就能得到一个可以走到右下角的strength（S），在0 - S范围里二分搜索
: ，反复调用DP算法，找到最小的返回yes的strength就可以了。

A*c2010-01-31 08:01

68 楼

This dumb solution is blatantly wrong.
Thanks for Jc2013 and lcheng to point out.

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

: 为什么我觉得第二题就是一个dp，从（M-1，N-1)往（0，0）规划如下
: dp[i][j] = max(dp[i+1][j], dp[i][j+1]) + A[i][j];
: 结果就是
: return dp[0][0] < 0 ? -dp[0][0] : 0;
: 和Leetcode里边的unique path没区别，就是方向反了而已，
: Did I miss anything?
:
: of
: ,3

i*t2010-01-31 08:01

69 楼

第二题能不能化简为一维DP.
因为DP[i][A] == DP[i][B] == DP[i][C]
设DP[i]为以index i为结尾的变体个数
所以DP[i] = dp[i - 1] + 2(dp[i - 1] - dp[i - 2]);
最后返回3DP[N - 1]

j*u2010-01-31 08:01

70 楼

mark

of
,3

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

: 刚面过G，从9月份电面到现在一共两个月把所有事情弄完。
: 电面只有一轮，出了一个之前版上出现过的题，一个string由0，1和？组成，并且？可
: 以被替换成0或者1，让输出所有的把？替换之后不同的string，比如1？0把？替换之后
: 能够生成110和100
: 之后过了三周才接到onsite的通知
: onsite一共有4轮，中间午餐
: 第一轮一上来告诉我一个function的定义和它的功能，然后问了很多test的东西，我也
: 不懂，就瞎扯，之后让我实现这个function以及它的一个变种，类似就是一个array of
: integer，以及一个int，这个int表示一个window的宽度，这个window从array的一开
: 始滑动到最后，找出来在滑动的过程中每次window中int的和，比如一个array是[1,2,3

n*52010-01-31 08:01

71 楼

谁能讲讲一个电面题咋做呢？谢了哈。递归？？

l*a2010-01-31 08:01

72 楼

4.2. 第四轮第二个， Harry Potter那道题试写了一下伪代码
memo[m+1][n+1]
For i in [0, m]
For j in [0, n]
Memo[i][j] = 0
For i in [0, m-1]
For j in [0, n-1]
Memo[i+1][j+1] = Memo[i][j+1] + grid[i][j]
Memo[i+1][j+1] = max(Memo[i+1][j+1] ,Memo[i][j+1] + grid[i][j])
val = Memo[m][n]-grid[m-1][n-1]
If val < 0
return -val
Else
Return 0

b*d2010-01-31 08:01

73 楼

1. 那个ABC的题，如此可以么？
先算N－1，得到一个list of string，然后，算N的情况：iterate N－1的那个list，
每个string的每个位置，都拿ABC分别test一下，如果可以，就insert进去，算作一个N
的情况的解。
2. harry potter，难道不是 nxm的DP么？
构建个Nxm的矩阵，每个cell，纪录两个值：到达此处的strength 和最小需要的初始携
带strength。对个每个cell，看其两个来源cell，取各自的strength，加上cell本身的
strength，如果小于0，那么说明从这个cell来到当前cell的话，还需要再加一部分初
始携带strength，update这个初始strengh，取小的那个assign到当前cell。
一直到右下结束。