Wednesday, December 24, 2014

Sum of nested integers

/** 
* 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(List input) {
  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;
 }
}

7 comments:

  1. Hi Shirley,

    Your 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)
    */

    ReplyDelete
    Replies
    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.
      So 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.

      Delete
  2. Hi Shirley,

    Thanks 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.

    ReplyDelete
    Replies
    1. 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.
      Hope it helps.

      Delete
  3. Hi Shirley,
    as 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.

    ReplyDelete
    Replies
    1. 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.

      Delete
  4. This comment has been removed by the author.

    ReplyDelete