* 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, and one 6 at depth 3)
*/
public int depthSum (List<NestedInteger> input)
{ // ur implementation here}
**
* This is the interface that represents nested lists.
* You should not implement it, or speculate about its implementation.
*/
public interface NestedInteger
{
/** @return true if this NestedInteger holds a single integer, rather than a nested list */
boolean isInteger();
/** @return the single integer that this NestedInteger holds, if it holds a single integer
* Return null if this NestedInteger holds a nested list */
Integer getInteger();
/** @return the nested list that this NestedInteger holds, if it holds a nested list
* Return null if this NestedInteger holds a single integer */
List<NestedInteger> getList();
}
A Linkedin interview question. The original problem can be found on Careercup.
Just use recursion. Return the integer * level if the NestedInteger is a single integer, otherwise recursively check all the lists in the NestedInteger.
Apparently the warning that I "should not implement it, or speculate about its implementation" is correct. Yet I am still curious...
public class SumofNestedIntegers { public int depthSum(Listinput) { if (input == null) return 0; return getSum(input, 1); } private int getSum(List input, int depth) { int sum = 0; for (NestedInteger nested : input) { if (nested.isInteger()) { sum += nested.getInteger() * depth; } else { sum += getSum(nested.getList(), depth++); } } return sum; } }
Hi Shirley,
ReplyDeleteYour blog is very informative. I came across same question but the depth is in reverse order. Could you please give hint how to approach this.
I still not clear from below example: 1 how 2 --> has depth 2 and {1,1} has depth 1 .
What might be the depth and sum for below example ?
{{1,1}, {4, {6}}, 5, {1,1} }
/**
* Given a nested list of integers, returns the sum of all integers in the list weighted by their reversed depth.
* For example, given the list {{1,1},2,{1,1}} the deepest level is 2. Thus the function should return 8 (four 1's with weight 1, one 2 with weight 2)
* Given the list {1,{4,{6}}} the function should return 17 (one 1 with weight 3, one 4 with weight 2, and one 6 with weight 1)
*/
The input is a list of NestedInteger. The first element is {1, 1}, which is another list of NestedInteger, and the depth of the list will increase. The second element is also a list of NestedInteger. If we look into the second element, it contains one NestedInteger which is a single integer, and another NestedInteger which is another list of integer, this will increase the depth by one.
DeleteSo overall we have:
1 * 2 + 1 * 2 (2 is the depth) + 4 * 2 + 6 * 3 + 5 * 1 + 1 * 2 + 1 * 2 = 39
Hope it helps.
Hi Shirley,
ReplyDeleteThanks for the reply. The question is particularly about depth in reverse order. I couldn't able to finish the test over telephonic because I am not clear from the interviewer example how he calculated depth in reverse order for the given example. I feel there is ambiguity in the depth given by the interviewer or I am confused I don't know.
I totally agree from your explanation, even I think the same for increasing depth.
If possible, please let me know how to calculate reverse depth in recursive.
Thanks a lot.
Well, as you said, because it is reversed order. So in your case, {1, 1} will be 2, {6} will be 1, 5 will be 3 and {1, 1} will be 2. Well, I don't have a good solution on top of my mind. But an easy way to do is to write a struct to track the number and the depth every time we call the recursion, after we know the total depth. We then calculate the sum by maxdepth - depth + 1.
DeleteHope it helps.
Hi Shirley,
ReplyDeleteas per the given example:
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, and one 6 at depth 3)
the above code fails to calculate the correct depth could you please help with the same.
Thanks a ton.
What do you mean by "fails to calculate"? Taking your example: getSum({{1, 1}, 2, {1, 1}}, 1). {1, 1} is not an integer, so call getSum({1, 1}, 2), in which each element in {1, 1} is an integer and we will get sum 4 (because depth is 2). Then we traverse to 2, which is an element, so sum = 4 + 1 * 2 = 6. Then {1, 1} is another list which leads to sum = 6 + 4 = 10.
DeleteThis comment has been removed by the author.
ReplyDelete