one interview question, very difficult, smart people can do - 未名空间MITBBS历史存档

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

Redian新闻

>未名空间

>JobHunting - 待字闺中

one interview question, very difficult, smart people can do

one interview question, very difficult, smart people can do# JobHunting - 待字闺中

g*g2011-08-29 07:08

1 楼

TRIANGLE PUZZLE
By starting at the top of the triangle and moving to adjacent numbers on the
row below, the maximum total from top to bottom is 27..
5
9 6
4 6 8
0 7 1 5
I.e. 5 + 9 + 6 + 7 = 27.
Write a program in a language of your choice to find the maximum total from
top to bottom in triangle.txt, a text file containing a triangle with 100
rows.
download traiangle.txt in http://www.yodle.com/downloads/puzzles/triangle.txt
who can fix this problem? It is very difficult. Please post your answer

s*n2011-08-29 07:08

2 楼

np-complete
have to use greedy approach.

the
from

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

: TRIANGLE PUZZLE
: By starting at the top of the triangle and moving to adjacent numbers on the
: row below, the maximum total from top to bottom is 27..
: 5
: 9 6
: 4 6 8
: 0 7 1 5
: I.e. 5 + 9 + 6 + 7 = 27.
: Write a program in a language of your choice to find the maximum total from
: top to bottom in triangle.txt, a text file containing a triangle with 100

f*t2011-08-29 07:08

3 楼

应该是个普通DP题，有什么难的？

s*y2011-08-29 07:08

4 楼

的确不难，很久前这里讨论过了
1维数组DP足以，那时候我也写过，可惜code在家里，
http://www.mitbbs.com/article_t/JobHunting/31873315.html

g*g2011-08-29 07:08

5 楼

这题难度在于,谁能给个正确的结果!

s*y2011-08-29 07:08

6 楼

写了个简单的，解你这个例子的，
#include
#include
#include
#include
#include
#include
using namespace std;
int matrix[4][4] = {{5,0,0,0},
{9,6,0,0},
{4,6,8,0},
{0,7,1,5}};
int getMax()
{
vector dp_table(4, 0);
for (int i = 0; i < 4; i++)
dp_table[i] = matrix[3][i];
for (int j = 2; j>= 0; j--) {
for (int i = 0; i <= j; i++)
dp_table[i] = max(matrix[j][i] + dp_table[i],
matrix[j][i] + dp_table[i+1]);
}
return dp_table[0];
}
int main()
{
int test = getMax();
return test;
}

g*g2011-08-29 07:08

7 楼

http://www.yodle.com/downloads/puzzles/triangle.txt
请用这个TXT FILE测试, 我只要结果

r*y2011-08-29 07:08

8 楼

DP starting from bottom ?

the
from

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

g*g2011-08-29 07:08

9 楼

No. from top

s*y2011-08-29 07:08

10 楼

你可以举个反例bottom up出来的结果，但是跟top down不一样吗？

g*g2011-08-29 07:08

11 楼

shei neng gei ge da an a

d*s2011-08-29 07:08

12 楼

[
9235, 9096, 7039, 7546, 9427, 9642, 9601, 9607, 7679, 8718, 8177, 9443, 9558
, 9965, 9445, 9828, 9967, 9463, 9326, 8754, 9607, 9870, 9636, 9905, 9402,
9080, 9777, 9292, 9782, 9281, 9963, 9398, 9583, 9729, 9032, 9710, 9095, 9997
, 9989, 9764, 9970, 9991, 9836, 9843, 9801, 9958, 9912, 9698, 9772, 9987,
9860, 9483, 9944, 9988, 9833, 9671, 9901, 9692, 9950, 9911, 9750, 9921, 9955
, 9935, 9933, 9950, 9733, 9959, 9721, 9688, 9979, 9898, 9978, 9838, 9864,
9882, 9831, 9893, 9868, 9883, 9962, 9996, 9995, 9944, 9897, 9881, 9943, 9801
, 9994, 9963, 9913, 9755, 9917, 9819, 9892, 9850, 9983, 9922, 9787,
9755 ]
------------------------------------------
#!/usr/bin/env python3
if __name__ == "__main__":
fin = open('triangle.txt','r')
aList = []
for sLine in fin:
llen = len(sLine.split())
for ii in range(0,llen):
aList.append(int(sLine.split()[ii]))
lenmax = llen
bList = []
for nn in range(2,lenmax+2):
pref = int((nn-1)*(nn-2)/2)
post = int(nn*(nn-1)/2)
bList.append( max( aList[pref:post] ) )
print(bList,len(bList))

r*g2011-08-29 07:08

13 楼

这个题top-down足够了啊，dp都不用，直接recursion就行了，关键是你给的数组太大
了，估计没人愿意一个个去读。
关键就是，从上到下面，每一层维护一个vector，其值是从这层这个数到最上面的路径
最大和。从上面每层过渡到紧挨着的下层，只需要对下层每个数check一下自己和自己
左右(上层的)的路径和的最大值，这样一层一层下去。根本和dp无关。
这个问题关键是，假设最后的路径是A1A2...An-1An，那么A1A2...An-1就是对应着只有
n-1层情况的最大值，否则的话，固定An-1An，上面还可以更大。
所以这个题连dp都不用。

B*12011-08-29 07:08

14 楼

so you are using greedy?

R*i2011-08-29 07:08

15 楼

我的方法是从底部开始往上移动做加法，上一层的每个元素只有两个分支，取和大的一
个替代就可以了。
跟从上往下的结果是一样的。
就是一遍历！

【在 B*******1 的大作中提到】

: so you are using greedy?

g*g2011-08-29 07:08

16 楼

回复12楼的，很多朋友给了算法，但是没给答案，那我也不一一研究了，只有一个朋友
给了答案，那我回复这个人的，是12楼的，你错在你没看清列子，不是选每一行的最
大数值，而是选上一行的最大数那个，然后下一行，相对应的2个数里面挑个最大的，
你看列子里面，第三行选了，6而不是8，千万别认为很简单，大家仔细算算

g*g2011-08-29 07:08

17 楼

who can give me a right answer?

y*82011-08-29 07:08

18 楼

Project Euler Problem 18 & 67
work bottom-up, greedy
从倒数第二行开始。每个数字和下一行的两个数字相加。选较大的值存。然后再上一行
5
9 6
4 6 8
0 7 1 5
倒数第二行的4和下一行它能reach的两个值0和7相加。取较大的4+7=11。
倒数第二行的6和下一行它能reach的两个值7和1相加。取较大的6+7=13。
三角形变为
5
9 6
11 13 13
再变为
5
22 19
再变为
27
最大值
ps OP这态度实在傲慢。

d*d2011-08-29 07:08

19 楼

732506
dp

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

: http://www.yodle.com/downloads/puzzles/triangle.txt
: 请用这个TXT FILE测试, 我只要结果

g*g2011-08-29 07:08

20 楼

顶楼上的，你答对了，能告诉我怎么解的嘛

s*x2011-08-29 07:08

21 楼

自己回去看书吧，这是个再普通不过的DP问题，好多人都说了。

g*g2011-08-29 07:08

22 楼

close this post. floor 18, 19 is right, perfect!!!!!
The requirement is from top to bottom, although from bottom to top is also
fine.
Thanks for everyone answer my question and giving me a way.
Thanks a lot for everyone.

g*g2011-08-29 07:08

23 楼

Yes. I finally understand . And who can tell me what's the DP means?

e*i2011-08-29 07:08

24 楼

Is this a DP problem?
I don't see an optimal substructure, because mp(1...n) != mp(1...n-1)+mp(n-1
...n). (mp = maximal path)
Slightly change the original example and you will know:
5
9 6
4 6 8
0 2 1 5
mp(1...3) = (5,9,6) = 20
using mp(1...3), the mp(1...4) = 20 + max(2,1) = 22.
However, mp(1...4) = (5,6,8,5) = 24 is the right answer.
Bottom up greedy search as in post 18 is right.

j*x2011-08-29 07:08

25 楼

The key difference characteristic of a DP solution is that, in DP,
subproblems may share common sub-subproblems, which is called "overlapping
structure" in literature.
Here, it is clear that to find the longest path, you will have some
overlapped subproblem, since paths may have common nodes.

-1

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

: Is this a DP problem?
: I don't see an optimal substructure, because mp(1...n) != mp(1...n-1)+mp(n-1
: ...n). (mp = maximal path)
: Slightly change the original example and you will know:
: 5
: 9 6
: 4 6 8
: 0 2 1 5
: mp(1...3) = (5,9,6) = 20
: using mp(1...3), the mp(1...4) = 20 + max(2,1) = 22.

r*t2011-08-29 07:08

26 楼

aren't you computer science majored? DP(dynamic programming) is a chapter in
Algorithm course.

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

: Yes. I finally understand . And who can tell me what's the DP means?

k*n2011-08-29 07:08

27 楼

肯定不是。这种题一般公司都不好意思出出来的吧。。。怎么搞到very difficult了。
。。

in

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

: aren't you computer science majored? DP(dynamic programming) is a chapter in
: Algorithm course.