问一道L烂大街的题题意还是有点不懂顺便报FG面经 - 未名空间MITBBS历史存档

问一道L烂大街的题题意还是有点不懂顺便报FG面经# JobHunting - 待字闺中

c*h2015-03-06 08:03

1 楼

问一道L家烂大街的题 nestedint reversed weighted sum
Compute the reverse depth sum of a nested list meaning the reverse depth of
each node (ie, 1 for leafs, 2 for parents of leafs, 3 for parents of parents
of leafs, etc.) times the value of that node.
这个例子应该怎么算?
{{1,2}, 1, {2, {2,1}}} = ?
{1,2}的weight应该是1 还是2?按照定义它应该是leaf吧所以应该是
(1+2)*1 + 1 * 3 + (2*2 + (2+1) * 1) = 13?
对说好的FG面经
F考了个BST里面找successor 就一题各种变有parent 没parent 用stack不用stack
G家考了俩第一个是给了两个有重复元素的list 求差集第二题是LC min stack变种
维护最小次小元素

y*e2015-03-06 08:03

2 楼

关注！

r*j2015-03-06 08:03

3 楼

{1,2}的weight应该是2

of
parents

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

: 问一道L家烂大街的题 nestedint reversed weighted sum
: Compute the reverse depth sum of a nested list meaning the reverse depth of
: each node (ie, 1 for leafs, 2 for parents of leafs, 3 for parents of parents
: of leafs, etc.) times the value of that node.
: 这个例子应该怎么算?
: {{1,2}, 1, {2, {2,1}}} = ?
: {1,2}的weight应该是1 还是2?按照定义它应该是leaf吧所以应该是
: (1+2)*1 + 1 * 3 + (2*2 + (2+1) * 1) = 13?
: 对说好的FG面经
: F考了个BST里面找successor 就一题各种变有parent 没parent 用stack不用stack

c*h2015-03-06 08:03

4 楼

那请问“(ie, 1 for leafs, 2 for parents of leafs, 3 for parents of parents
of leafs, etc.) ”应该怎么理解呢 {1,2}不是leaf么?

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

: {1,2}的weight应该是2
:
: of
: parents

z*b2015-03-06 08:03

5 楼

这题首先需要过一遍list找出最大的深度先？谁能给个简洁的代码？

of
parents

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

: 问一道L家烂大街的题 nestedint reversed weighted sum
: Compute the reverse depth sum of a nested list meaning the reverse depth of
: each node (ie, 1 for leafs, 2 for parents of leafs, 3 for parents of parents
: of leafs, etc.) times the value of that node.
: 这个例子应该怎么算?
: {{1,2}, 1, {2, {2,1}}} = ?
: {1,2}的weight应该是1 还是2?按照定义它应该是leaf吧所以应该是
: (1+2)*1 + 1 * 3 + (2*2 + (2+1) * 1) = 13?
: 对说好的FG面经
: F考了个BST里面找successor 就一题各种变有parent 没parent 用stack不用stack

C*t2015-03-06 08:03

6 楼

def revSum(a):
d = height(a)
level, sum = 1, [0]
helper(a, d, level, sum)
return sum[0]
def height(a):
d = 1
for ele in a:
if type(ele) == list:
d = max(d, 1+height(ele))
return d
def helper(a, d, level, sum):
for i in range(len(a)):
if type(a[i]) != list:
sum[0] += a[i]*(d-level+1)
else:
helper(a[i], d, level+1, sum)

x*92015-03-06 08:03

7 楼

nested_list = [[1,2], 1, [2, [2,1]]]
def revSum(nlist):
(depth, res) = dfs(nlist)
return res
def dfs(nlist):
nlist_sum = 0
s = 0
max_lv = 1
for item in nlist:
if isinstance(item, list):
(depth, res) = dfs(item)
nlist_sum += res
max_lv = max(max_lv, depth + 1)
else:
s += item
nlist_sum += s * max_lv
return (max_lv, nlist_sum)
print revSum(nested_list)
(已加入肯德基豪华午餐

c*h2015-03-06 08:03

8 楼

问一道L家烂大街的题 nestedint reversed weighted sum
Compute the reverse depth sum of a nested list meaning the reverse depth of
each node (ie, 1 for leafs, 2 for parents of leafs, 3 for parents of parents
of leafs, etc.) times the value of that node.
这个例子应该怎么算?
{{1,2}, 1, {2, {2,1}}} = ?
{1,2}的weight应该是1 还是2?按照定义它应该是leaf吧所以应该是
(1+2)*1 + 1 * 3 + (2*2 + (2+1) * 1) = 13?
对说好的FG面经
F考了个BST里面找successor 就一题各种变有parent 没parent 用stack不用stack
G家考了俩第一个是给了两个有重复元素的list 求差集第二题是LC min stack变种
维护最小次小元素

y*e2015-03-06 08:03

9 楼

关注！

r*j2015-03-06 08:03

10 楼

{1,2}的weight应该是2

of
parents

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

: 问一道L家烂大街的题 nestedint reversed weighted sum
: Compute the reverse depth sum of a nested list meaning the reverse depth of
: each node (ie, 1 for leafs, 2 for parents of leafs, 3 for parents of parents
: of leafs, etc.) times the value of that node.
: 这个例子应该怎么算?
: {{1,2}, 1, {2, {2,1}}} = ?
: {1,2}的weight应该是1 还是2?按照定义它应该是leaf吧所以应该是
: (1+2)*1 + 1 * 3 + (2*2 + (2+1) * 1) = 13?
: 对说好的FG面经
: F考了个BST里面找successor 就一题各种变有parent 没parent 用stack不用stack

c*h2015-03-06 08:03

11 楼

那请问“(ie, 1 for leafs, 2 for parents of leafs, 3 for parents of parents
of leafs, etc.) ”应该怎么理解呢 {1,2}不是leaf么?

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

: {1,2}的weight应该是2
:
: of
: parents

z*b2015-03-06 08:03

12 楼

这题首先需要过一遍list找出最大的深度先？谁能给个简洁的代码？

of
parents

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

: 问一道L家烂大街的题 nestedint reversed weighted sum
: Compute the reverse depth sum of a nested list meaning the reverse depth of
: each node (ie, 1 for leafs, 2 for parents of leafs, 3 for parents of parents
: of leafs, etc.) times the value of that node.
: 这个例子应该怎么算?
: {{1,2}, 1, {2, {2,1}}} = ?
: {1,2}的weight应该是1 还是2?按照定义它应该是leaf吧所以应该是
: (1+2)*1 + 1 * 3 + (2*2 + (2+1) * 1) = 13?
: 对说好的FG面经
: F考了个BST里面找successor 就一题各种变有parent 没parent 用stack不用stack

C*t2015-03-06 08:03

13 楼

def revSum(a):
d = height(a)
level, sum = 1, [0]
helper(a, d, level, sum)
return sum[0]
def height(a):
d = 1
for ele in a:
if type(ele) == list:
d = max(d, 1+height(ele))
return d
def helper(a, d, level, sum):
for i in range(len(a)):
if type(a[i]) != list:
sum[0] += a[i]*(d-level+1)
else:
helper(a[i], d, level+1, sum)

x*92015-03-06 08:03

14 楼

nested_list = [[1,2], 1, [2, [2,1]]]
def revSum(nlist):
(depth, res) = dfs(nlist)
return res
def dfs(nlist):
nlist_sum = 0
s = 0
max_lv = 1
for item in nlist:
if isinstance(item, list):
(depth, res) = dfs(item)
nlist_sum += res
max_lv = max(max_lv, depth + 1)
else:
s += item
nlist_sum += s * max_lv
return (max_lv, nlist_sum)
print revSum(nested_list)
(已加入肯德基豪华午餐

y*e2015-03-06 08:03

15 楼

我看似乎得这么做，下面那个python的代码也是这么写的，如果有更简单的One pass的
办法，还请大神们指教

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

: 这题首先需要过一遍list找出最大的深度先？谁能给个简洁的代码？
:
: of
: parents

x*92015-03-06 08:03

16 楼

nested list 就是一个递归的结构
很难one pass
当然，从理论上说，DFS也是一个one pass，每一个元素都被且只被遍历了一次。。。
如果不用递归的话，可以用stack模拟

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

: 我看似乎得这么做，下面那个python的代码也是这么写的，如果有更简单的One pass的
: 办法，还请大神们指教

y*e2015-03-06 08:03

17 楼

不好意思我当时没看到你这个solution，我说的是你前面那个python，他是先遍历了一
遍求了一个depth, 然后又遍历的list求sum。你的答案的确是one pass,谢谢分享！

【在 x*******9 的大作中提到】

:
: nested list 就是一个递归的结构
: 很难one pass
: 当然，从理论上说，DFS也是一个one pass，每一个元素都被且只被遍历了一次。。。
: 如果不用递归的话，可以用stack模拟

x*92015-03-06 08:03

18 楼

:)
Good luck for job hunting

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

: 不好意思我当时没看到你这个solution，我说的是你前面那个python，他是先遍历了一
: 遍求了一个depth, 然后又遍历的list求sum。你的答案的确是one pass,谢谢分享！

c*h2015-03-06 08:03

19 楼

就是说 {1,2} 的weight 是1了对吧因为nlist_sum没有乘max_lv
我觉得是对的
2L说{1,2} weight是2不知道为啥

nested_list = [[1,2], 1, [2, [2,1]]]
def revSum(nlist):
(depth, res) = dfs(nlist)
return res
def dfs(nlist):
nlist_sum = 0
s = 0
max_lv = 1
for item in nlist:
if isinstance(item, list):
(depth, res) = dfs(item)
nlist_sum += res
max_lv = max(max_lv, depth + 1)
else:
s += item
nlist_sum += s * max_lv
return (max_lv, nlist_sum)
print revSum(nested_list)

【在 x*******9 的大作中提到】

: nested_list = [[1,2], 1, [2, [2,1]]]
: def revSum(nlist):
: (depth, res) = dfs(nlist)
: return res
: def dfs(nlist):
: nlist_sum = 0
: s = 0
: max_lv = 1
: for item in nlist:
: if isinstance(item, list):