Linkedin Interview - Sum of NestedInteger

Given a nested list of integers, returns the sum of all integers in the list weighted by their depth 

For example, given the list {{1,1},2,{1,1}} the function should return 10 (four 1's at depth 2, one 2 at depth 1) 

Given the list {1,{4,{6}}} the function should return 27 (one 1 at depth 1, one 4 at depth 2, one 6 at depth2) 

 

/** 
* This is the interface that represents nested lists. 
* You should not implement it, or speculate about its implementation. 
*/ 
public interface NestedInteger 
{ 
//Returns true if this NestedInteger holds a single integer, rather than a nested list 
public boolean isInteger(); 

//Returns the single integer that the NestedInteger holds, if it holds a single integer 
//Returns null if this NestedInteger holds a nested list 
public Integer getInteger(); 

//Returns the nested list that this NestedInteger holds, if it holds a nested list 
//Returns null if this NestedInteger holds a single integer 
public List<NestedInteger> getList(); 
}

 

Solution:

public int sumOfNestedInteger(NestedInteger nest) {
	if(nest.isInteger()) {
		return nest.getInteger();
	}
	return sumList(nest.getList(), 1);
}

private int sumList(List<NestedInteger> list, int depth) {
	int sum = 0;
	for(NestedInteger item: list) {
		if(item.isInteger()) {
			sum += item.getInteger()*depth;
		} else {
			sum += sumList(item.getList(), depth+1);
		}
	}
	return sum;
}

 

Follow Up:

followup说改成return the sum of all integers in the list weighted by their “reversed depth”.

也就是说{{1,1},2,{1,1}}的结果是(1+1+1+1)*1+2*2=8

 

思路：

需要两个变量计数，sum 与 prev

例子 {{2,2,{3}},1,{2,2}}

一共三层

第一层 prev = 1 sum=1

第二层 prev =prev+2+2+2+2  最后prev =9， sum = 10

第三层 prev =prev +3 prev = 12        sum =22

理论结果   3+2*2*4+1*3 =22

public int sumOfReversedWeight(NestedInteger ni) {
	if(ni.isInteger()) {
		return ni.getInteger();
	}
	int prev = 0, sum = 0;
	List<NestedInteger> cur = ni.getList();
	List<NestedInteger> next = new ArrayList<>();
	while(!cur.isEmpty()) {
		for(NestedInteger item:cur) {
			if(item.isInteger()) {
				prev += item.getInteger();
			} else {
				next.addAll(item.getList());
			}
			sum += prev;
			cur = next;
			next = new ArrayList<>();
		}
	}
	return sum;
}

 

Reference:

http://www.careercup.com/question?id=5139875124740096

http://www.mitbbs.com/article_t1/JobHunting/32850869_0_1.html