Depth Sum or Nested List Weight Sum ( Linked In Interview question)

Problem: Given the nested list of integer, calculate the depth sum.

Sample Input: [[1,1], 2, [1,1]] Output: 10
Explanation: 1* 2 + 1 * 2 + 2 * 1+ 1 * 2+ 1 * 2  = 10. ( Number in the red color are the level in the nested list. )

Sample Input: [1 [4 [6]]] Output: 27
Explanation: 1 * 1 + 4 * 2 + 6 * 3 = 27( Number in the red color are the level in the nested list. )

Solution:

There are two ways to solve this problem. Either iterative or recursive.

1. Iterative: You need a data structure to keep track of nested list. This can be Queue. At each level, if you see a list, add it in a queue and keep on traversing till queue is empty.
2. Recursive: Easy way to solve it compared to iterative. At each level, you need to check if it is a list then increment the current level and make a recursive call. Return the sum once you hit the number.

Simplification of the depth tracking in Recursive approach:
So, in above approach, we are going to each list value and also keep track of depth and do a sum. Another way to approach is to, capture sums at each depth by maintaining an array. This array index represents the depth of nested list.

For example:
Input data :  [ [ 1,5 ], 3, [ 8, [ 9 ] ] ] Resulting array will be : [3, 14, 9] . At level one we have only one element, which is 3. At level 2 we have 1, 5, 8 = 14 and at level 3 we have 9.
Now, it easy to calculate the sum : 3 * 1 + 14 * 2 + 9 * 3 = 58

One tricky variation is to consider depth in decreasing order.
If you take above approach then its easy to solve. Once you have a result array you can calculate the sum in reverse order. i.e. 3 * 3 + 14 * 2 + 9 * 1 = 46

Refer to method caclulateDepthSumRecursiveV1 for updated version.

Code:

Complexity: O(n)

Github url: DepthSum.java