logo
Redian新闻
>未名空间
>Stock
>
谢国忠：走向滞胀 (转载)
avatar
谢国忠：走向滞胀 (转载)# Stock
l*7
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啊！！！！！
avatar
N*n
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。
在泡沫之下，资源被用于制造更多泡沫。这些资
avatar
A*c
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
avatar
N*n
4 楼
If only Hu & Wen could be half as intelligent as Xie.
avatar
f*e
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
avatar
g*u
6 楼
Strongly disagree.
BTW, intelligence is so over-rated.

【在 N********n 的大作中提到】
: If only Hu & Wen could be half as intelligent as Xie.
avatar
d*n
7 楼
Bless
HR还不错，说送了HC
我面完后HR只说一周内出消息
avatar
P*r
8 楼
Google 题目还是难啊。
第四个的第一题是用dp算 V[i][j] (i->j continues subsequence sum),然后比较
range吗？
avatar
d*k
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);
}
avatar
A*o
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 成功:)
avatar
c*p
11 楼
mark
avatar
j*r
12 楼
bless楼主拿到大offer!
avatar
c*e
13 楼
bless
avatar
z*s
14 楼
bless，顺便问一句，怎么你面的全是算法题？和面的组有关系吗？
avatar
j*6
15 楼
bless
下下周面 (蛋疼的thanksgiving 下周面不了) 同求bless
lz 是 new grad 吗？ 好像new grad 都是算法题？
你每一轮多长时间？ 我是 9:45 - 2:00 也能是四轮吗？ 还是三轮？
avatar
k*6
16 楼
第四轮的那个一个array of int，以及一个range (low, high)，什么解法比较好呢？
我想先把array sort了再两头2 pointers往中间走，选出within range 的subsequence
, 靠谱吗？
avatar
d*k
17 楼
第四轮的两道题求澄清：
1. array里面是否可能出现负数？
2. Harry potter是否只能向右或向下走？
祝楼主好运
avatar
m*m
18 楼
bless
avatar
t*y
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
: , 靠谱吗？
avatar
l*y
20 楼
blessing!!
avatar
z*s
21 楼
好心人给说一下吧。。。现在就算法还行，TC有1700。但其他设计，OO什么的都基本上
就没认真学，现在也忘光了，不知道有没有面试只考算法的？

【在 z****s 的大作中提到】
: bless，顺便问一句，怎么你面的全是算法题？和面的组有关系吗？
avatar
l*7
22 楼
我是new grad general招的，面的时候没有具体组，面我的人也来自不同的组

【在 z****s 的大作中提到】
: bless，顺便问一句，怎么你面的全是算法题？和面的组有关系吗？
avatar
l*7
23 楼
面试官说不能sort，因为要输出range，如果sort了那index就乱掉了
最好的方法是用一个prefix sum array吧

subsequence

【在 k*********6 的大作中提到】
: 第四轮的那个一个array of int，以及一个range (low, high)，什么解法比较好呢？
: 我想先把array sort了再两头2 pointers往中间走，选出within range 的subsequence
: , 靠谱吗？
avatar
l*7
24 楼
1.可以出现负数
2.只能往右或者往下走

【在 d*k 的大作中提到】
: 第四轮的两道题求澄清：
: 1. array里面是否可能出现负数？
: 2. Harry potter是否只能向右或向下走？
: 祝楼主好运
avatar
d*e
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
avatar
z*s
26 楼
谢啦，我是算法还行，其他设计，OO什么的就一塌糊涂了，如果只面算法和coding就太
好了。bless~

【在 l********7 的大作中提到】
: 我是new grad general招的，面的时候没有具体组，面我的人也来自不同的组
avatar
P*r
27 楼
赞一个，简单明了。
原则上也算一维dp吧。

【在 d********e 的大作中提到】
: 不明白valid string为啥要dp
: 直接用两个数记录前一个位置上，相同两个字母结尾的为a,不同字母结尾的为b
: 这样迭代一下
: a = a +b;
: b = 2*a+b;
: 初始值为长度为2，所以a=3,b=6，不就可以了吗
:
: of
: ,3
avatar
H*a
28 楼
valid string是否是每增加一位，多出来的个数为3*3（末两位相同的情况*可以添加的
char的种类）+6*2（末两位不同的情况*可以添加的char的种类）
avatar
w*7
29 楼
did anyone solve the harry potter question? please post your thoughts.
avatar
b*6
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.
avatar
w*7
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)
avatar
g*e
32 楼

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

【在 d********e 的大作中提到】
: 不明白valid string为啥要dp
: 直接用两个数记录前一个位置上，相同两个字母结尾的为a,不同字母结尾的为b
: 这样迭代一下
: a = a +b;
: b = 2*a+b;
: 初始值为长度为2，所以a=3,b=6，不就可以了吗
:
: of
: ,3
avatar
l*n
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)
avatar
w*7
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
avatar
z*5
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
avatar
l*n
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
avatar
w*7
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
avatar
l*n
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.
avatar
w*7
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
avatar
l*n
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.
avatar
l*n
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.
avatar
w*7
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++) {
avatar
l*b
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++) {
avatar
l*n
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分别代表啥？
avatar
l*b
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。
avatar
G*m
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。
avatar
m*s
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
avatar
j*6
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];
}
}
avatar
w*s
49 楼
能举例子展开讲讲? 没看明白

【在 d********e 的大作中提到】
: 不明白valid string为啥要dp
: 直接用两个数记录前一个位置上，相同两个字母结尾的为a,不同字母结尾的为b
: 这样迭代一下
: a = a +b;
: b = 2*a+b;
: 初始值为长度为2，所以a=3,b=6，不就可以了吗
:
: of
: ,3
avatar
l*n
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
: 的解是不一样的
:
avatar
p*e
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.
avatar
p*e
52 楼
Subarray sum那道题，我觉得如果O(n^2)可以的话，有至少2种解法，prefix sum
array，或是一个2D DP, 其实本质都一样。
有没有大牛说说优于O(n^2)的解法？
avatar
l*u
53 楼
bless
avatar
S*e
54 楼
谢谢分享！祝你好运！
avatar
r*o
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']
avatar
P*9
56 楼
多谢！祝拿到0ffer！
avatar
w*s
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
avatar
p*y
58 楼
没看懂，能否详细讲讲？

【在 w*******s 的大作中提到】
: Harry Potter是二分搜索答案，对于每个答案，用DP判断是否可行。
: 一开始随便找一条路设初始值。
:
: ,
: pathmin
: pathmin
avatar
w*s
59 楼
给定初始strength，用DP算出能否到达右下角，DP的状态是到达每一个点的strength的
最大值，此算法输入是strength，输出是yes or no。
随便找一条路就能得到一个可以走到右下角的strength（S），在0 - S范围里二分搜索
，反复调用DP算法，找到最小的返回yes的strength就可以了。

【在 p*********y 的大作中提到】
: 没看懂，能否详细讲讲？
avatar
e*r
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
avatar
m*n
61 楼
把prefix sum sort 一下，找到大的减小的在规定范围内，就是线性问题了。
当然要检查大的是更多的数的和。这样是O(nlogn)。

【在 p*****e 的大作中提到】
: Subarray sum那道题，我觉得如果O(n^2)可以的话，有至少2种解法，prefix sum
: array，或是一个2D DP, 其实本质都一样。
: 有没有大牛说说优于O(n^2)的解法？
avatar
g*g
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是否只能向右或向下走？
: 祝楼主好运
avatar
A*c
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
avatar
A*c
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
avatar
A*c
65 楼
“才能保证你能够找到一条路走到右下角”
这不是说了找到一条路就行吗，没说要求任意一条路，对吧。

【在 e********r 的大作中提到】
: 最后一个题意不明，如果是“保证”，是不是应该求负得最多的那条路？
:
: of
: ,3
avatar
n*s
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])
avatar
l*6
67 楼
Re

【在 w*******s 的大作中提到】
: 给定初始strength，用DP算出能否到达右下角，DP的状态是到达每一个点的strength的
: 最大值，此算法输入是strength，输出是yes or no。
: 随便找一条路就能得到一个可以走到右下角的strength（S），在0 - S范围里二分搜索
: ，反复调用DP算法，找到最小的返回yes的strength就可以了。
avatar
A*c
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
avatar
i*t
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]
avatar
j*u
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
avatar
n*5
71 楼
谁能讲讲一个电面题咋做呢？谢了哈。递归？？
avatar
l*a
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
avatar
b*d
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。
一直到右下结束。
相关阅读
怎么样，雨夜哥哥的一周定律还算灵吧今天a股收红澳，买糕的我擦，牛牛就頂了半天太子党炒美股是不是轻轻松松挣几个亿今天跑了一点苹果我问今天抄底的朋友, 以后还敢这么干吗? 她说 (转载)我的计划天上井， 地上井， 你的荷包要捂紧留给MM的时间太少今晚a股还要跌沪指先崩了，又宽幅震荡狗剩的2100还算数么？今晚为A股敲响最后的丧钟为什么 fidelity 403b 限制交易？会不会是这样的？大盘红了，可是很多捞的中钙还深绿呢花街不把捞底的散户全灭了，不肯拉盘啊从昨天到今天抄底的，基本都水下了屌美元竟然和美股同步了！
logo
联系我们隐私协议©2024 redian.news
Redian新闻
Redian.news刊载任何文章，不代表同意其说法或描述，仅为提供更多信息，也不构成任何建议。文章信息的合法性及真实性由其作者负责，与Redian.news及其运营公司无关。欢迎投稿，如发现稿件侵权，或作者不愿在本网发表文章，请版权拥有者通知本网处理。